Die Ausgabe Pre-Order lässt sich, wie auch die anderen beiden am besten rekursiv formulieren. Bei der Strategie der Pre-Order-Ausgabe wird zunächst die Wurzel besucht und ihr Wert ausgegeben. Dann wird der linke Teilbaum mit der Strategie Pre-Order ausgegeben, danach der rechte Teilbaum, ebenfalls mit der Strategie Pre-Order.
Pre-Order =
Ausgabe aktueller Knoten
Pre-Order (linker Teilbaum)
Pre-Order (rechter Teilbaum)
Die Pre-Order-Strategie wird z.B. bei Termauswertung (Präfix-Notation) benutzt. Wie heißt nun die Liste der Zahlen, wenn der binäre Suchbaum nach Pre-Order
ausgegeben wird?
Bestätigen Sie folgendes Ergebnis:
[7,0,5,3,2,1,12,9,8,10,13,15]
In diesem Fall wird die Wurzel erst ausgegeben, wenn der linke Teilbaum mit der Strategie In-Order ausgeben ist. Nach der Ausgabe des Wertes der Wurzel, erfolgt die Ausgabe des rechten Teilbaums mit der Strategie In-Order
In-Order =
In-Order (linker Teilbaum)
Ausgabe aktuelle Knoten
In-Order (rechter Teilbaum)
Wie heißt die Liste der Zahlen, wenn der binäre Suchbaum nach der In-Order-Strategie ausgegeben wird? Bestätigen Sie auch folgendes Ergebnis:
[0,1,2,3,5,7,8,9,12,13,15]
Das Ergebnis zeigt, die In-Order-Strategie kann zum effizienten Sortieren benutzt werden. Dass die Werte sortiert ausgegeben werden,
hat nichts damit zu tun, wie der Baum aufgebaut wurde, solange wir nur um einen binären Suchbaum
verwenden.
Bei diesem Verfahren wird zunächst der linke Teilbaum mit der Strategie Post-Order ausgegeben, und daran anschließend der rechte Teilbaum mit der gleichen Strategie. Danach erfolgt erst die Ausgabe des Wertes der Wurzel.
Post-Order =
Post-Order (linker Teilbaum)
Post-Order (rechter Teilbaum)
Ausgabe aktueller Knoten
Das Post-Order-Verfahren wird z.B. benutzt bei der Eingabe von Termen bei einigen Taschenrechnern (Postfix-Notation ).
Die Ausgabe ergibt sich dann zu, was Sie auch hier wieder nachrechnen mögen:
[1,2,3,5,0,8,10,9,15,13,12,7]
© Ralph-Erich Hildebrandt, 09. Mai 2005