Traversierungen: pre in post

Drei Tiefenreihenfolgen sind üblich. Eine beginnt beim Knoten und besucht danach linken und rechten Teilbaum. Eine andere besucht zuerst den linken Teilbaum, dann den Knoten, dann den rechten. Die dritte schliesst den Knoten erst nach beiden Teilbäumen ab.

Für einen Suchbaum liefert die links-knoten-rechts-Reihenfolge die sortierte Schlüsselfolge. Die knoten-zuerst-Reihenfolge eignet sich zum Serialisieren der Struktur.

Beispielbaum: Wurzel 2, links 1, rechts 3. Die sortierende Traversierung ergibt 1, 2, 3.

Eine geordnete Knotenserie als Programmierübung [1].

Wo gebraucht

Serialisieren vor den Kindern, sortierte Ausgabe in Suchbäumen, Ausdrucksauswertung und Freigabe nach den Kindern, Build-Systeme und Dependency-Auflösung. Die Wahl der Besuchordnung ist eine Produktentscheidung, nicht nur Übung.

Vertiefung

Tiefentraversierungen unterscheiden sich durch den Zeitpunkt, an dem der aktuelle Knoten relativ zu seinen Teilbäumen verarbeitet wird. Verarbeitung vor beiden Kindern eignet sich zum Serialisieren von Struktur, Verarbeitung zwischen den Kindern liefert bei Suchbäumen sortierte Schlüssel, Verarbeitung nach beiden Kindern unterstützt bottom-up-Auswertungen.

Alle drei Varianten besuchen jeden erreichbaren Knoten einmal und benötigen Zeit proportional zur Knotenzahl. Der zusätzliche Speicher hängt von der Höhe ab, weil höchstens ein Wurzelpfad gleichzeitig aktiv sein muss.

Eine iterative Umsetzung speichert Knoten zusammen mit dem noch auszuführenden Zustand. Nur Knoten abzulegen reicht für Varianten mit Verarbeitung nach einem Kind oft nicht aus.

Schwierigkeitsstufen

1. Besuchsfolgen für einen kleinen Baum bestimmen.
2. Verarbeitungszeitpunkt aus einem Anwendungsziel wählen.
3. Rekursive Kontrollzustände iterativ repräsentieren.

Fallstricke

Die Reihenfolge der Werte bestimmt den Baum ohne Zusatzinformation nicht immer eindeutig. Bei der iterativen Form werden Kinder oft in falscher Reihenfolge abgelegt.