Traversal: einen Baum durchlaufen
Wenn du alle Knoten in eine Reihenfolge bringen willst, gibt es 4 Standard-Methoden:
In-Order: links → self → rechts
inorder(node):
inorder(node.left)
print(node.value)
inorder(node.right)
Bei einem BST ist In-Order IMMER sortiert aufsteigend. Wenn du sagen sollst „gib alle Werte sortiert aus" — In-Order.
Beispiel auf dem Baum oben: 10, 25, 35, 50, 60, 75, 90.
Pre-Order: self → links → rechts
preorder(node):
print(node.value)
preorder(node.left)
preorder(node.right)
Wurzel zuerst, dann der ganze linke Teilbaum, dann rechts. Anwendung: Klonen eines Baums oder Speichern (Pre-Order genügt für eindeutige Rekonstruktion mit In-Order).
Beispiel: 50, 25, 10, 35, 75, 60, 90.
Post-Order: links → rechts → self
postorder(node):
postorder(node.left)
postorder(node.right)
print(node.value)
Blätter zuerst, Wurzel zuletzt. Anwendung: Speicher freigeben (Kinder vor dem Parent löschen), Berechnung mit abhängigen Werten (Auswerten von Ausdrucksbäumen).
Beispiel: 10, 35, 25, 60, 90, 75, 50.
Level-Order: Ebene für Ebene (BFS)
levelorder(root):
queue = [root]
while queue not empty:
node = queue.pop_front()
print(node.value)
queue.append(node.left)
queue.append(node.right)
Wie ein Wasserfall: Wurzel zuerst, dann Ebene 1 von links nach rechts, dann Ebene 2, etc.
Beispiel: 50, 25, 75, 10, 35, 60, 90.
Pre/In/Post sind DFS (Depth-First, mit Rekursion oder Stack). Level-Order ist BFS (Breadth-First, mit Queue).