Pre-, In- und Postorder

Eine Reihung durchläuft man mit einer Zählschleife von vorn nach hinten. Ein Baum hat kein „vorn“ und „hinten“ — man muss festlegen, wann die Wurzel an der Reihe ist.

• Traversierung:jeden Knoten eines Baums genau einmal verarbeiten, z. B. ausgeben.
• Preorder:W – L – R: erst die Wurzel, dann linker, dann rechter Teilbaum.
• Inorder:L – W – R: die Wurzel steht zwischen den beiden Teilbäumen.
• Postorder:L – R – W: die Wurzel kommt ganz zum Schluss.
• Umrundung:Man fährt den Baum links herum ab und berührt jeden Knoten dreimal: links, unten, rechts.

Starte die Umrundung mit ▶ oder ziehe den violetten Schieber auf dem Band. Das Band ist die abgewickelte Umrundung: blau = links am Knoten vorbei, grün = unten, orange = rechts. Wähle die Reihenfolge — die Ausgabe sammelt genau die Berührungen dieser Farbe.

Halte fest: Alle drei Traversierungen laufen denselben Weg um den Baum. Sie unterscheiden sich nur darin, bei welcher der drei Berührungen ein Knoten ausgegeben wird.

Die Definition des Binärbaums ist rekursiv — deshalb ist es die Traversierung auch: Teilbäume werden mit derselben Methode bearbeitet.

• Abbruch:Der leere Baum wird nicht bearbeitet — die Methode tut dann nichts.
• Rekursionsschritt:Wurzel verarbeiten und beide Teilbäume rekursiv traversieren — in der gewählten Reihenfolge.
• Nur eine Zeile wandert:Für Inorder steht die Ausgabe zwischen den beiden Aufrufen, für Postorder nach beiden.

static void preorder(BinTree<String> b) {
    if (!b.isEmpty()) {
        System.out.print(b.getItem() + " ");   // W: Wurzel verarbeiten
        preorder(b.getLeft());                 // L: linken Teilbaum
        preorder(b.getRight());                // R: rechten Teilbaum
    }
}
// Baum 1 aus dem Applet — preorder: M F B K H S W
//                          inorder:  B F H K M S W
//                          postorder: B H K F W S M

• Preorder nutzen:Baum kopieren oder mit Struktur ausgeben — die Wurzel muss zuerst da sein.
• Inorder nutzen:Im Suchbaum (ab 5.3.3) liefert sie alle Werte sortiert.
• Postorder nutzen:Rechenbaum auswerten oder Baum löschen — erst die Teilbäume, dann die Wurzel.