Baum-Traversal-Methoden sind Techniken, die verwendet werden, um alle Knoten einer Baumdatenstruktur systematisch zu besuchen. Diese Methoden zu verstehen ist für verschiedene Anwendungen wie Suchen, Sortieren und Expressionsauswertung unerlässlich. Dieser Artikel vergleicht die drei primären Traversal-Methoden Vorordnung, Inordnung und Postordnung mit praktischen Berechnungen, um ihre Unterschiede zu veranschaulichen.

Vorbestellung Traversal

Die Vorbestellung der Traversal besucht zuerst den Wurzelknoten und durchquert dann rekursiv den linken Teilbaum, gefolgt vom rechten Teilbaum. Diese Methode ist nützlich, um Bäume zu kopieren oder Präfixausdrücke zu erstellen.

Zum Beispiel, angesichts des Baumes:

A
/
B
/
D E F

Die Vorreihen-Traversalsequenz ist: A, B, D, E, C, F.

Indikations-Traversal

Die Inorder Traversal besucht zuerst den linken Teilbaum, dann den Root-Knoten und schließlich den rechten Teilbaum. Diese Methode wird üblicherweise für binäre Suchbäume verwendet, um Daten in sortierter Reihenfolge abzurufen.

Mit dem gleichen Baum ist die Inorder-Traversal-Sequenz: D, B, E, A, C, F.

Postorder Traversal

Die Postorder-Traversal besucht den linken Teilbaum, dann den rechten Teilbaum und schließlich den Wurzelknoten. Dieser Ansatz ist nützlich, um Bäume zu löschen oder Postfix-Ausdrücke zu bewerten.

Für den Beispielbaum ist die Postorder-Traversalsequenz: D, E, B, F, C, A.

Praktische Berechnungen

Betrachten Sie den Baum:

1
/
2 3
/
4 5 6

Vorbestellungstraversal: 1, 2, 4, 5, 3, 6

Ordnungsüberschreitung: 4, 2, 5, 1, 3, 6

Postorder Traversal: 4, 5, 2, 6, 3, 1