Binäre Bäume

In der Praxis ebenso wichtig wie Wälder und allgemeine Bäume, wenn nicht sogar wichtiger, sind Binärbäume.  Sie lassen sich algebraisch einfach spezifizieren:
ADT BTrees(T) IS
SORTS:
btree, T, boolean
OPERATIONS:
newtree: btree
node: T btree btree btree
isempty: btree boolean
root: btree T
left: btree btree
right: btree btree
RULES:
isempty(newtree) = true
isempty(node(x, l, r)) = false
root(node(x, l, r)) = x
left(node(x, l, r)) = l
right(node(x, l, r)) = r
END BTrees.
Ein Binärbaum ist kein Baum!  Die wesentlichen Unterschiede sind: Die Darstellung von Binärbäumen als Verweise auf Knoten mit einem Datenfeld und zwei Zeigern ist naheliegend: 
TYPE btree = POINTER TO brecord;
   brecord = RECORD wert: atom;
               left, right: btree;
             END;
sie liefert uns auch sofort eine Darstellung für einen Wald durch einen äquivalenten Binärbaum. Für jeden (allgemeinen) Baum des Waldes gilt: in den linken Unterbaum des zugeordneten Binärbaumes kommen die Nachkommen, in den rechten Unterbaum die jüngeren Brüder samt ihren Nachkommen.
zurück | Inhalt | Index | vor | Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36