Traversierungsverfahren: Preorder, Inorder und Postorder
Die Ausgabe eines Binärbaumes kann auf drei verschiedene Arten geschehen. Entweder in Pre-, In- oder Postorder. Die Verfahren haben gewisse Vor- und Nachteile, aber dazu später mehr. Der Unterschied der Verfahren besteht lediglich darin, in welcher Reihenfolge die Teilbäume und der Knoten ausgegeben werden.
Bei allen Verfahren beginnt man von oben. Alle hier aufgeführten Implementierungen sind rekursive Methoden und können frei verwendet werden.
Zur Demonstration der Verfahren wird folgender Binärbaum verwendet:
Bei allen Verfahren beginnt man von oben. Alle hier aufgeführten Implementierungen sind rekursive Methoden und können frei verwendet werden.
Zur Demonstration der Verfahren wird folgender Binärbaum verwendet:
Preorder
Bei dem Preorder-Verfahren wird, wie der Name von sagt, die Wurzel zuerst ausgegeben und dann der linke und dann der rechte Teilbaum. Ein Beispiel soll dies verdeutlichen:
Die Ausgabe in Preorder lautet also: 10, 5, 3, 7, 13, 12, 20
Dieses Verfahren eignet sich besonders zum Abspeichern von Binärbaumen, denn wenn man die Elemente wieder einliest, erhält man den gleichen Baum.
Eine Implementierung in Java könnte wie folgt aussehen:
public void PreOrder(Binearbaum b) {
System.out.println(b.getRootItem().toString());
if (b.getLeftTree() != null) {
PreOrder(b.getLeftTree());
}
if (b.getRightTree() != null) {
PreOrder(b.getRightTree());
}
}
Inorder
Beim Inorder-Verfahren, wird erst der linke Teilbaum, dann die Wurzel und schließlich der rechte Teilbaum ausgegeben. Bei dem gleichen Beispielbaum erhalten wir folgende Ausgabe: 3, 5, 7, 10, 12, 13, 20
Es zeigt sich gleich der Vorteil dieses Verfahrens: Der Binärbaum wird sortiert ausgegeben. Allerdings ist dieses Verfahren nicht zum Abspeichern geeignet, da beim Einlesen eine Liste entstehen würde.
Eine Implementierung in Java könnte wie folgt aussehen:
public void InOrder(Binearbaum b) {
if (b.getLeftTree() != null) {
InOrder(b.getLeftTree());
}
System.out.println(b.getRootItem().toString());
if (b.getRightTree() != null) {
InOrder(b.getRightTree());
}
}
Postorder
Beim Postorder-Verfahren, werden erst der linke und dann der rechte Teilbaum ausgegeben und schließlich die Wurzel. Bei dem gleichen Beispielbaum erhalten wir folgende Ausgabe: 3, 7, 5, 12, 20, 13, 10
Dieses Verfahren wird in der Praxis eher weniger gebraucht, wurde hier aber zur Vollständigkeit mit aufgeführt.
Eine Implementierung in Java könnte wie folgt aussehen:
public void PostOrder(Binearbaum b) {
if (b.getLeftTree() != null) {
PostOrder(b.getLeftTree());
}
if (b.getRightTree() != null) {
PostOrder(b.getRightTree());
}
System.out.println(b.getRootItem().toString());
}
05.04.2013
