Einen Binärbaum traversieren - Tiefensuche

Zum Abschluss wollen wir noch die Tiefensuche kennen lernen, eine Möglichkeit einen Baum zu traversieren. Traversieren heißt, jeden einzelnen Knoten (mindestens) einmal zu besuchen.

Es gibt noch unglaublich viele andere interessante Algorithmen für Bäume, daher wollen wir zumindest einen vorstellen, der nicht ganz direkt mit unserer binären Suche zusammenhängt.

Was bringt Traversieren?

Es gibt viele offensichtliche Anwendungen. Vielleicht führt unsere Hans-Wurst Schule ein, dass bei jedem Schüler jetzt zusätzlich das Geschlecht gespeichert werden soll. Am einfachsten ändern wird das, indem wir den Baum traversieren und überall die entsprechende Änderung anbringen.

Vielleicht wollen wir unserem Baum auch nur eine Liste mit allen enthaltenen Einträgen entnehmen, wozu wir auch jeden Knoten einmal besuchen müssen.

Idee

Tiefensuche besucht immer zunächst das linke Kind eines Knotens. Erst wenn es dieses linke Kind nicht gibt, wird ein rechtes Kind besucht und dann die vorherigen rechten Kindern (in denen natürlich auch wieder die linken Kinder zuerst besucht werden).

Traversieren wir beispielsweise den folgenden Baum:

Dann können wir anhand der gebogenen Kanten und deren Nummerierung den Weg der Tiefensuche verfolgen: