Datenstruktur & Algorithmen - Tree Traversal

Beim Durchlaufen werden alle Knoten eines Baums besucht und möglicherweise auch deren Werte gedruckt. Da alle Knoten über Kanten (Links) verbunden sind, beginnen wir immer am Wurzelknoten (Kopfknoten). Das heißt, wir können nicht zufällig auf einen Knoten in einem Baum zugreifen. Es gibt drei Möglichkeiten, wie wir einen Baum durchqueren können:

• In-Order-Traversal
• Traversal vorbestellen
• Nachbestellungsdurchquerung

Im Allgemeinen durchlaufen wir einen Baum, um ein bestimmtes Element oder einen bestimmten Schlüssel im Baum zu suchen oder zu finden oder um alle darin enthaltenen Werte zu drucken.

In-Order-Traversal

Bei dieser Traversal-Methode wird zuerst der linke Teilbaum, dann die Wurzel und später der rechte Teilbaum besucht. Wir sollten immer daran denken, dass jeder Knoten selbst einen Teilbaum darstellen kann.

Wenn ein Binärbaum durchlaufen wird in-orderDie Ausgabe erzeugt sortierte Schlüsselwerte in aufsteigender Reihenfolge.

Wir fangen an von Aund nach dem Durchlaufen der Reihenfolge bewegen wir uns zu seinem linken Teilbaum B. Bwird auch in der richtigen Reihenfolge durchlaufen. Der Vorgang wird fortgesetzt, bis alle Knoten besucht sind. Die Ausgabe der Inorder Traversal dieses Baums ist -

D → B → E → A → F → C → G

Algorithmus

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

Traversal vorbestellen

Bei dieser Traversal-Methode wird zuerst der Wurzelknoten, dann der linke Teilbaum und schließlich der rechte Teilbaum besucht.

Wir fangen an von Aund nach dem Durchlaufen der Vorbestellung besuchen wir zuerst A selbst und dann zu seinem linken Teilbaum bewegen B. Bwird auch vorbestellt durchlaufen. Der Vorgang wird fortgesetzt, bis alle Knoten besucht sind. Die Ausgabe der Vorbestellungsdurchquerung dieses Baums ist -

A → B → D → E → C → F → G

Algorithmus

Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.

Nachbestellungsdurchquerung

Bei dieser Traversal-Methode wird der Stammknoten zuletzt besucht, daher der Name. Zuerst durchlaufen wir den linken Teilbaum, dann den rechten Teilbaum und schließlich den Wurzelknoten.

Wir fangen an von ANach dem Durchlauf nach der Bestellung besuchen wir zuerst den linken Teilbaum B. Bwird auch nachbestellt durchquert. Der Vorgang wird fortgesetzt, bis alle Knoten besucht sind. Die Ausgabe der Nachbestellungsdurchquerung dieses Baums ist -

D → E → B → F → G → C → A

Algorithmus

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

Klicken Sie hier, um die C-Implementierung von Tree Traversing zu überprüfen .