Traversierung bedeutet, alle Knoten einer Datenstruktur systematisch genau einmal zu besuchen — etwa alle Knoten eines Baums oder eines Graphen. Die Reihenfolge, in der die Knoten besucht werden, entscheidet darüber, was das Ergebnis des Durchlaufs ist.
Baum-Traversierung
Bei einem Binärbaum gibt es drei klassische Tiefen-Durchläufe. W steht für den Wurzelknoten, L für den linken und R für den rechten Teilbaum:
- Preorder (W-L-R): Erst den Knoten besuchen, dann links, dann rechts. Praktisch, um einen Baum zu kopieren oder serialisieren.
- Inorder (L-W-R): Erst links, dann der Knoten, dann rechts. Bei einem binären Suchbaum liefert Inorder die Elemente in sortierter Reihenfolge.
- Postorder (L-R-W): Erst die Kinder, dann der Knoten. Nützlich zum Löschen eines Baums oder zum Auswerten von Ausdrucksbäumen.
- Level-Order: Der Baum wird Ebene für Ebene von oben nach unten durchlaufen — das ist eine Breitensuche.
Umsetzung
Die Tiefen-Durchläufe lassen sich elegant mit Rekursion formulieren: Die Funktion besucht den Knoten und ruft sich dann selbst auf den Teilbäumen auf. Iterativ nutzt man einen Stack, der die noch zu besuchenden Knoten merkt. Die Level-Order verwendet dagegen eine Queue, weil sie zuerst die Knoten der aktuellen Ebene abarbeitet (Breitensuche, BFS).
Graphen durchlaufen
In Graphen unterscheidet man ebenfalls zwei Strategien: Die Tiefensuche (DFS) folgt einem Pfad, bis sie nicht mehr weiterkommt, und geht dann zurück; die Breitensuche (BFS) breitet sich von einem Startknoten ringförmig aus. Damit ein Graph mit Zyklen nicht endlos durchlaufen wird, markiert man besuchte Knoten in einer Besuchsliste. Die Suche nach kürzesten Wegen baut direkt auf solchen Durchläufen auf.
Anwendungen
- Sortierte Ausgabe aus einem binären Suchbaum per Inorder
- Auswertung und Optimierung von Ausdrucksbäumen in Compilern
- Freigeben von Speicher durch Postorder (erst Kinder, dann Eltern)
- Navigieren im DOM einer Webseite, das selbst eine Baumstruktur ist
- Suche und Zyklenerkennung in Netzwerken und Abhängigkeitsgraphen
Die Traversierung gehört damit zu den grundlegenden Werkzeugen der Informatik: Wer Bäume und Graphen durchlaufen kann, kann sie sortieren, suchen, kopieren und auswerten.