Im Gegensatz zu verknüpften Listen, eindimensionalen Arrays und anderen linearen Datenstrukturen, die kanonisch in linearer Reihenfolge durchlaufen werden, können Bäume auf mehrere Arten durchlaufen werden. Sie können in der Reihenfolge „Tiefe zuerst“ oder „Breite zuerst“ durchlaufen werden. Es gibt drei gängige Möglichkeiten, sie in der Tiefe zu durchlaufen: In-Order, Pre-Order und Post-Order. Neben diesen grundlegenden Durchläufen sind verschiedene komplexere oder hybride Schemata möglich, z. B. tiefenbegrenzte Suchen wie die iterative vertiefende Tiefensuche. Letztere kann ebenso wie die Breadth-First-Suche auch zur Durchquerung unendlicher Bäume verwendet werden, siehe unten.
Datenstrukturen für die BaumdurchquerungBearbeiten
Bei der Durchquerung eines Baumes werden alle Knoten auf irgendeine Weise durchlaufen. Da es von einem gegebenen Knoten aus mehr als einen möglichen nächsten Knoten gibt (es handelt sich nicht um eine lineare Datenstruktur), müssen unter der Annahme einer sequentiellen (nicht parallelen) Berechnung einige Knoten auf irgendeine Weise für einen späteren Besuch zurückgestellt werden. Dies geschieht häufig über einen Stapel (LIFO) oder eine Warteschlange (FIFO). Da ein Baum eine selbstreferentielle (rekursiv definierte) Datenstruktur ist, kann die Traversierung durch Rekursion oder, subtiler, durch Corecursion auf sehr natürliche und klare Weise definiert werden; in diesen Fällen werden die zurückgestellten Knoten implizit im Aufrufstapel gespeichert.
Die Tiefensuche lässt sich leicht über einen Stapel implementieren, auch rekursiv (über den Aufrufstapel), während die Breitensuche leicht über eine Warteschlange implementiert wird, auch corecursiv.45-61
Depth-first-Suche eines BinärbaumsBearbeiten
- Pre-order (Knotenzugriff an Position rot ●):
F, B, A, D, C, E, G, I, H;
- In-Order (Knotenzugriff an Position grün ●):
A, B, C, D, E, F, G, H, I;
- Post-Order (Knotenzugriff an Position blau ●):
A, C, E, D, B, H, I, G, F.
Diese Suchvorgänge werden als „depth-first search“ (DFS) bezeichnet, da der Suchbaum bei jedem Kind so weit wie möglich vertieft wird, bevor zum nächsten Geschwisterkind übergegangen wird. Für einen Binärbaum sind sie als Zugriffsoperationen an jedem Knoten definiert, beginnend mit dem aktuellen Knoten, dessen Algorithmus wie folgt lautet:
Das allgemeine rekursive Muster für das Durchlaufen eines Binärbaums ist das folgende:
- Gehen Sie eine Ebene nach unten zum rekursiven Argument N. Wenn N existiert (nicht leer ist), führen Sie die folgenden drei Operationen in einer bestimmten Reihenfolge aus: L: Rekursiv den linken Teilbaum von N durchlaufen. R: Rekursives Durchlaufen des rechten Teilbaums von N. N: Zugriff (Besuch) auf den aktuellen Knoten N selbst.
- Zurückgehen, indem man eine Ebene nach oben geht und beim übergeordneten Knoten von N ankommt.
Es gibt drei Methoden (Muster), an welcher Position des Parcours (Traversal) relativ zum Knoten (in der Abbildung: rot, grün oder blau) der Besuch (Zugriff) des Knotens stattfinden soll. Die Wahl von genau einer Farbe bestimmt genau einen Besuch eines Knotens, wie unten beschrieben. Ein Zugriff bei allen drei Farben führt zu einem dreifachen Besuch desselben Knotens, was die „all-order“-Sequenzialisierung ergibt:
F-B-A-A-B-D-C-C-D-E-E-D-B-F-G-G- I-H-H-H- I- I-G-F
Pre-order, NLREdit
- Zugriff auf den Datenteil des aktuellen Knotens (in der Abbildung: Position rot).
- Durchlaufen des linken Teilbaums durch rekursiven Aufruf der Vorordnungsfunktion.
- Durchlaufen des rechten Teilbaums durch rekursiven Aufruf der Vorordnungsfunktion.
Der Pre-Order-Traversal ist ein topologisch sortierter Traversal, da ein übergeordneter Knoten verarbeitet wird, bevor einer seiner untergeordneten Knoten verarbeitet wird.
In-Order, LNREdit
- Traversieren Sie den linken Teilbaum durch rekursiven Aufruf der In-Order-Funktion.
- Zugriff auf den Datenteil des aktuellen Knotens (in der Abbildung: Position grün).
- Durchlaufen des rechten Teilbaums durch rekursiven Aufruf der In-Order-Funktion.
In einem binären Suchbaum, der so geordnet ist, dass in jedem Knoten der Schlüssel größer als alle Schlüssel in seinem linken Teilbaum und kleiner als alle Schlüssel in seinem rechten Teilbaum ist, werden beim Traversieren in-order die Schlüssel in aufsteigender sortierter Reihenfolge abgerufen.
Reverse in-order, RNLEdit
- Traversiert den rechten Teilbaum durch rekursiven Aufruf der Reverse-in-Order-Funktion.
- Zugriff auf den Datenteil des aktuellen Knotens.
- Traversiert den linken Teilbaum durch rekursiven Aufruf der Reverse-in-Order-Funktion.
In einem binären Suchbaum werden beim Traversieren in umgekehrter Reihenfolge die Schlüssel in absteigender sortierter Reihenfolge abgerufen.
Post-order, LRNEdit
- Traversieren Sie den linken Teilbaum durch rekursiven Aufruf der Post-order-Funktion.
- Traversiere den rechten Teilbaum durch rekursiven Aufruf der Post-Order-Funktion.
- Zugriff auf den Datenteil des aktuellen Knotens (in der Abbildung: Position blau).
Der Trace eines Traversals wird als Sequentialisierung des Baums bezeichnet. Der Traversaltrace ist eine Liste aller besuchten Knoten. Keine der Sequenzialisierungen nach Vor-, Zwischen- oder Nachordnung beschreibt den zugrundeliegenden Baum in eindeutiger Weise. Bei einem Baum mit eindeutigen Elementen reicht entweder pre-order oder post-order gepaart mit in-order aus, um den Baum eindeutig zu beschreiben. Pre-Order mit Post-Order hinterlässt jedoch eine gewisse Mehrdeutigkeit in der Baumstruktur.
Generic treeEdit
Um einen beliebigen Baum mit Deep-First-Suche zu durchlaufen, führen Sie die folgenden Operationen an jedem Knoten durch:
- Wenn Knoten nicht vorhanden, kehren Sie zurück.
- Zugriff (=Besuch) auf den Knoten (Vorordnungsposition).
- Für jedes i von 1 bis Anzahl_der_Kinder – 1 do:
- Rekursiv das i-te Kind durchlaufen.
- Zugriffsknoten (in-order Position).
- Rekursiv das letzte Kind durchlaufen.
- Zugriffsknoten (post-order Position).
Je nach Problemstellung können die Operationen pre-order, post-order und insbesondere eine der Operationen (number_of_children – 1) in-order ungültig sein, oder es wird nur auf ein bestimmtes Kind zugegriffen, so dass diese Operationen optional sind. Außerdem kann in der Praxis mehr als eine der Operationen pre-order, in-order und post-order erforderlich sein. Beim Einfügen in einen ternären Baum wird beispielsweise eine Vorordnungsoperation durch den Vergleich von Elementen durchgeführt. Eine Post-Order-Operation kann anschließend erforderlich sein, um den Baum wieder ins Gleichgewicht zu bringen.
Breadth-first search, or level orderEdit
Bäume können auch in Ebenenreihenfolge durchlaufen werden, wobei jeder Knoten auf einer Ebene besucht wird, bevor eine niedrigere Ebene erreicht wird. Diese Suche wird als „breadth-first search“ (BFS) bezeichnet, da der Suchbaum auf jeder Ebene so weit wie möglich erweitert wird, bevor zur nächsten Ebene übergegangen wird.
Andere ArtenBearbeiten
Es gibt auch Algorithmen zum Durchqueren von Bäumen, die weder als „depth-first search“ noch als „breadth-first search“ eingestuft werden. Ein solcher Algorithmus ist die Monte-Carlo-Baumsuche, die sich auf die Analyse der vielversprechendsten Züge konzentriert und die Erweiterung des Suchbaums auf Zufallsstichproben aus dem Suchraum stützt.