28.13 Drei Ausgaben-Modi
eines Baumes |
|
Die drei
wichtigsten Ausgabestrategien demonstrieren wir an dem uns aus dem
vorangehenden Abschnitt bekannten Baum:
|
|
Pre-Order |
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 = 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?
|
In-Order |
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 Wie heißt die Liste der Zahlen, wenn der binäre Suchbaum nach der In-Order-Strategie ausgegeben wird? [0,1,2,3,5,7,8,9,10,12,13,15] Das
Ergebnis zeigt, die In-Order-Strategie kann zum effizienten
Sortieren benutzt werden. Dass die Werte sortiert ausgegeben werden, ist
übrigens unabhängig davon, wie der Baum aufgebaut wurde, solange es sich
nur um einen binären Suchbaum handelt . Man möge dazu die
In-Order-Strategie mit dem ausgewogenen Baum aus dem letzten
Abschnitt durchspielen : |
post-Order |
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.
1. Post-Order
= Das Post-Order-Verfahren wird z.B. benutzt bei der Eingabe von Termen bei einigen Taschenrechnern (Postfix-Notation ). Wie auch hier der Leser bestätigen möge, ergibt sich für die Ausgabe: [0,2,5,3,1,8,10,9,15,13,12,7] Beschäftigen wir uns nun, das Gelernte in Java zu implementieren |
zu | 28.14 Die Klassen Knoten |
zur Startseite | www.pohlig.de (C) MPohlig 2004 |