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

Source: Baum.java     JavaDoc: Baum.html    

Hinweis: Um Bäume nicht nur auszulesen, sondern auch verändern zu können, müssen die (noch zu definierenden) Konstruktoren der Implementation verwendet werden.

Konzept zur Implementation eines Baumes mit Verweisen

Ein Baum besteht aus einer Menge von Knoten. Der VerweisBaum enthält daher einen Verweis auf den Wurzelknoten oder einen null-Verweis, wenn der Baum leer ist. Ein Knoten enthält neben einem Verweis auf den Inhalt jeweils einen Verweis auf den linken und rechten Sohn, sofern sie vorhanden sind.

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: Knoten.java     JavaDoc: Knoten.html     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: