Traversierung von Binärbäumen

Die Traversierung von Binärbäumen bezeichnet den Weg, mit dem der Binärbaum durchlaufen wird. Grundsätzlich kann man dies auf 3 verschiedene Weisen tun.

Preorder

Die Ausgabe des Preorder-Verfahrens ordnet sich wie folgt:

1. Besuche die Wurzel
2. Traversiere den linken Teilbaum
3. Traversiere den rechten Teilbaum

Inorder

• Traversiere den linken Teilbaum
• Besuche die Wurzel
• Traversiere den rechten Teilbaum

Postorder

Eine Ausgabe eines Postorder Baums baut sich folgendermaßen auf:

1. Traversiere den linken Teilbaum
2. Traversiere den rechten Teilbaum
3. Besuche die Wurzel

Zusätzlich: Level-order

Zusätzlich ist auch eine breadth-first/ Breitensuche möglich. Dieses Verfahren wird oft auch level-order genannt. Dabei wird bei der Ausgabe mit der Baumwurzel begonnen und dann die einzelnen Ebenen von links nach rechts durchlaufen.

Level-order ist kein Teil des Lehrplans und kann daher vernachlässigt werden.

Beispiel

Preorder:: 2 1 4 3 6 5 7 Inorder:: 1 2 3 4 5 6 7 Postorder:: 1 3 5 7 6 4 2