C-Programmierung
Baumtraversierung
← Baumcharakteristik | ● | Traversierungsbeispiel →
Bei der Suche nach einem Element x besucht (traverisert) man die Knoten des Baums ausgehend von der Wurzel.
Es wird dabei ausgenutzt, dass der Baum impliziert sortiert ist.
- Falls x == Wert des aktuellen Knotens, so ist die Suche bereits erfolgreich beendet
- Falls x < Wert des aktuellen Knotens traversiert man nach links
- wegen Baumeigenschaften muss x in linkem Teilbaum liegen
- Sonst traversiert man nach rechts
- wegen Baumeigenschaften muss x in rechtem Teilbaum liegen
- Nach einem Blatt endet die Traversierung erfolglos
Die Menge der aufgesuchten Knoten nennt man Pfad.
Die Anzahl der aufgesuchten Knoten eines Pfades ist die Pfadlänge.