Wie wiederhole ich den Binärbaum?
6 Antworten
Können Sie es anstelle einer Rekursion in Iteration ändern?
Sie können einen expliziten Stapel verwenden. Pseudocode:
%Vor%Aber das ist dem rekursiven Code nicht wirklich überlegen (abgesehen von der fehlenden Basisbedingung in Ihrem Code).
Was Sie suchen, ist ein Nachfolgeralgorithmus.
So kann es definiert werden:
- Erste Regel : Der erste Knoten in der Struktur ist der Knoten ganz links in der Struktur.
-
Nächste Regel : Der Nachfolger eines Knotens ist:
- Next-R-Regel : Wenn es einen rechten Teilbaum hat, den Knoten ganz links im rechten Teilbaum.
-
Next-U-Regel : Fahren Sie andernfalls den Baum hoch
- Wenn Sie nach rechts abbiegen (d. h. dieser Knoten war ein linkes Kind), dann ist dieser Elternknoten der Nachfolger
- Wenn Sie nach links abbiegen (d. h. dieser Knoten war ein rechtes Kind), gehen Sie weiter nach oben.
- Wenn du nicht mehr aufsteigen kannst, gibt es keinen Nachfolger
Wie Sie sehen können, benötigen Sie dazu einen übergeordneten Knotenzeiger.
Beispiel:
-
Erste Regel : Der erste Knoten in der Struktur ist der Knoten ganz links in der Struktur:
(1) -
Next-U-Regel : Da
(1)keinen rechten Teilbaum hat, gehen wir zu(3). Dies ist eine Rechtskurve, also ist(3)next. -
Next-R-Regel : Da
(3)über einen rechten Teilbaum verfügt, ist der Knoten ganz links in diesem Teilbaum der nächste:(4). -
Next-U-Regel : Da
(4)keinen rechten Teilbaum hat, gehen wir zu(6). Dies ist eine Rechtskurve, daher ist(6). -
Next-R-Regel : Da
(6)über einen rechten Teilbaum verfügt, ist der Knoten ganz links in diesem Teilbaum der nächste:(7). -
Next-U-Regel : Da
(7)keinen rechten Teilbaum hat, gehen wir zu(6). Dies ist eine Linkskurve, also gehen wir weiter zu(3). Dies ist eine Linkskurve, also gehen wir weiter zu(8). Dies ist eine Rechtskurve, daher ist(8). -
Next-R-Regel : Da
(8)über einen rechten Teilbaum verfügt, ist der Knoten ganz links in diesem Teilbaum der nächste:(10). -
Next-R-Regel : Da
(10)über einen rechten Teilbaum verfügt, ist der Knoten ganz links in diesem Teilbaum der nächste:(13). -
Next-U-Regel : Da
(13)keinen rechten Teilbaum hat, gehen wir zu(14). Dies ist eine Rechtskurve, daher ist(14). -
Next-U-Regel : Da
(14)keinen rechten Teilbaum hat, gehen wir zu(10). Dies ist eine Linkskurve, also gehen wir weiter zu(8). Dies ist eine Linkskurve, also wollen wir weiter nach oben gehen, aber da(8)kein Elternteil hat, haben wir das Ende erreicht.(14)hat keinen Nachfolger.
Pseudocode
%Vor%Java-Code
Hier ist eine einfache Implementierung des obigen Algorithmus:
%Vor%Dann können Sie einen Test-Kabelbaum wie folgt haben:
%Vor%Dies druckt:
%Vor%Siehe auch
Sicher, Sie haben zwei allgemeine Algorithmen: erste Tiefensuche und weitere Suche .
Wenn die Reihenfolge der Traversierung für Sie nicht wichtig ist, wählen Sie zuerst die Breite, dann ist es einfacher, sie für die Iteration zu implementieren. Dein Algorithmus sollte ungefähr so aussehen.
%Vor%Wie bei jeder Rekursion können Sie eine zusätzliche Datenstruktur verwenden - also den Stack. Eine Skizze der Lösung :
%Vor%Ja, Sie können es anstelle einer Rekursion in Iteration ändern, aber dann wird es viel komplizierter, da Sie eine Möglichkeit haben müssen, sich zu erinnern, wo Sie vom aktuellen Knoten zurück gehen können. Im rekursiven Fall verarbeitet der Java-Aufruf-Stack das, aber in einer iterativen Lösung müssen Sie Ihren eigenen Stack erstellen oder vielleicht Zeiger in den Knoten speichern.
Ich hatte einen Baum (nicht binär) und löste ihn schließlich mit diesem sehr einfachen Algorithmus. Die anderen verwendeten Lösungen links und rechts waren in den Beispielen nicht relevant oder gar nicht implementiert.
Meine Struktur war: Knoten mit jedem Elternteil, der eine Liste von Kindern enthielt, und jedes Kind, das einen Zeiger zurück auf das Elternteil enthielt. Ziemlich häufig ...
Nach einigem Refactoring kam ich mit Kotlin zum folgenden Beispiel. Es sollte trivial sein, in die Sprache Ihrer Wahl zu konvertieren.
Hilfsfunktionen
Zuerst muss der Knoten 2 einfache Funktionen bereitstellen. Dies hängt von der Implementierung Ihrer Knotenklasse ab:
leftMost - Dies ist der erste untergeordnete Knoten. Wenn dieser Knoten untergeordnete Elemente hat, ist es das erste untergeordnete Element usw. Wenn keine untergeordneten Objekte vorhanden sind, geben Sie das zurück.
%Vor%nextSibling - Das nächste gleichgeordnete Element dieses Knotens oder NULL
%Vor%Die Iteration
Die Iteration beginnt mit dem leftMost der Wurzel.
Inspiziere dann das nächste Geschwister.
- Wenn NOT NULL ist das linksMostChild des Geschwisters
- Wenn NULL, das übergeordnete Element, und wenn das übergeordnete Element NULL ist, sind wir fertig.
Das ist es.
Hier ist eine Kotlin-Iterator-Funktion.
%Vor%Hier ist die gleiche next () -Funktion, aber ohne die Kotlin-Kurzschrift für den Umgang mit NULL-Werten, für diejenigen, die nicht zur Syntax passen.
%Vor%Tags und Links algorithm java recursion traversal binary-tree