prev up next

Previous: Schlange Up: Abstrakte Datentypen Next: Suchbaum

Baum

Def.:
Ein binärer Baum ist entweder leer oder besteht aus einem Knoten, dem ein Element und zwei binäre Bäume zugeordnet sind.
Schnittstelle des ADT Baum:

empty : Baum $\rightarrow$ boolean liefert true, falls Baum leer ist
           
value : Baum $\rightarrow$ Objekt liefert Wurzelelement
           
left : Baum $\rightarrow$ Baum liefert linken Teilbaum
           
right : Baum $\rightarrow$ Baum liefert rechten Teilbaum
           
setValue : Baum $\times$ Object $\rightarrow$ Baum setzt Objekt in die Wurzel
           
setLeft : Baum $\times$ Baum $\rightarrow$ Baum pflanzt linken Teilbaum an
           
setRight : Baum $\times$ Baum $\rightarrow$ Baum pflanzt rechten Teilbaum an
           

Source: Baum.java     JavaDoc: Baum.html    

Konzept zur Implementation eines Baumes mit Verweisen

(Obacht: Aus technischen Gründen hat jedes Blatt zwei Verweise auf leere Bäume. Hierdurch vereinfachen sich gewisse Operationen auf dem später noch einzuführenden Suchbaum.)


Traversierungen

Eine Traversierung eines binären Baumes besteht aus dem systematischen Besuchen aller Knoten in einer bestimmten Reihenfolge.

Traversierungen dieses Baumes

Preorder: / + F * A B - X Y
Inorder: F + A * B / X - Y
Postorder: F A B * + X Y - /
Klammerinorder: ( ( F + ( A * B) ) / ( X - Y ) )
Source: VerweisBaum.java     JavaDoc: VerweisBaum.html     Source: Traverse.java     JavaDoc: Traverse.html     Source: TiefenSuche.java     JavaDoc: TiefenSuche.html     Source: BreitenSuche.java     JavaDoc: BreitenSuche.html     Source: TraverseTest.java     JavaDoc: TraverseTest.html     Applet: Source: PostfixBaumBau.java     JavaDoc: PostfixBaumBau.html     Applet: Source: PreorderTraverse.java     JavaDoc: PreorderTraverse.html     Applet: Source: PostfixPreorderTest.java     JavaDoc: PostfixPreorderTest.html     Applet:


prev up next
Previous: Schlange Up: Abstrakte Datentypen Next: Suchbaum