Was ist der beste Weg, um alle Knoten einer verknüpften Struktur zu besuchen (alle Knoten haben Referenzen auf Eltern und alle Kinder, Wurzelknoten haben null als Eltern), so dass kein Knoten vor einem seiner Vorfahren besucht wird? Brownie Punkte für nicht-rekursive.
Pseudocode:
%Vor% Bearbeiten : Rekursiv oder nicht?
Um technisch korrekt zu sein und wie AndreyT und andere in diesem Beitrag darauf hingewiesen haben, ist dieser Ansatz eine Form von einem rekursiven Algorithmus, bei dem ein explizit gemanagter Stack verwendet wird des CPU-Stacks und wo die Rekursion auf der Ebene der While-Schleife stattfindet. Das heißt, es unterscheidet sich von einer rekursiven Implementierung per se auf eine subtile, aber dennoch signifikante Weise:
Wenn Sie Links zu allen untergeordneten Elementen und auch zu den übergeordneten Elementen haben, ist der nicht-rekursive Algorithmus eher trivial. Vergiss einfach, dass du einen Baum hast. Stellen Sie sich vor, es ist ein Labor, in dem jede Eltern-Kind-Verbindung ein normaler bidirektionaler Korridor von einer Kreuzung zur anderen ist. Alles, was Sie tun müssen, um das ganze Labyrinth zu durchqueren, ist, an jeder Kreuzung in den nächsten Korridor auf der linken Seite zu kommen. (Alternativ können Sie sich vorstellen, dass Sie mit Ihrer linken Hand durch das Labyrinth gehen und immer die Wand auf der linken Seite berühren). Wenn Sie an der Wurzelkreuzung beginnen (und sich in eine beliebige Richtung bewegen), werden Sie den ganzen Baum durchwandern und immer die Eltern vor den Kindern besuchen. Jeder "Korridor" wird in diesem Fall zweimal (in die eine Richtung und in die andere) gereist, und jede "Kreuzung" (Knoten) wird so oft besucht, wie viele "Korridore" sich ihm anschließen.
Verwenden Sie eine Reihe von Knoten. Setze die Wurzel in das Set um zu starten. Ziehen Sie dann in einer Schleife einen Knoten aus der Menge, besuchen Sie ihn und legen Sie dann seine untergeordneten Elemente in die Menge ein. Wenn das Set leer ist, sind Sie fertig.
Wenn Sie am Stammknoten beginnen und nur die Eltern / Kinder von Knoten besuchen, die Sie bereits besucht haben, gibt es keine Möglichkeit , den Baum so zu durchlaufen, dass Sie einen Knoten vor dem Besuch seiner Vorfahren besuchen .
Jede Art von Traversierung, Tiefe zuerst (rekursiv / stackbasiert), Breite zuerst (queue-basiert), Tiefe-begrenzt oder einfach aus einer ungeordneten Menge herausziehen funktioniert.
Die "beste" Methode hängt vom Baum ab. Breite zuerst würde gut für einen sehr hohen Baum mit wenigen Zweigen funktionieren. Tiefe zuerst würde gut für Bäume mit vielen Zweigen funktionieren.
Da die Knoten tatsächlich Zeiger auf ihre Eltern haben, gibt es auch einen Konstantspeicher-Algorithmus, der aber viel langsamer ist.
Ich würde der ersten Suche nach Breite nicht zustimmen, da die Komplexität des Raums oft der Fluch dieses spezifischen Suchalgorithmus ist. Möglicherweise ist die Verwendung des iterativen Vertiefungsalgorithmus für diese Art der Verwendung eine bessere Alternative und deckt den gleichen Traversierungstyp wie die erste Breite der Suche ab. Es gibt kleine Unterschiede im Umgang mit dem Rand von der Breite-zuerst-Suche, es sollte nicht zu hart sein, um (Pseudo-) code-out, obwohl.
Referenz: Ссылка
Hier ist ein wirklich nicht-rekursiver Ansatz: kein Stapel, konstanter Platz. Dieser Python-Code setzt voraus, dass jeder Knoten eine Liste von untergeordneten Elementen enthält und dass die Knotenobjekte keine Gleichheit definieren, sodass die Funktion "index" Identitäten vergleicht:
%Vor%Ich bin mir sicher, dass es ein wenig aufpoliert werden könnte, präziser und einfacher zu lesen, aber das ist der Kern.
Erstellen Sie eine Liste der Knoten im Stammverzeichnis (Ebene 0), durchlaufen Sie nacheinander alle Knoten und suchen Sie nach direkten untergeordneten Elementen (deren übergeordneter Knoten der aktuelle Knoten ist) (Ebene 1), wenn Sie mit der Ebene fertig sind 0 gehe weiter zum Iterieren von Level 1 und so weiter, bis du keine noch nicht besuchten Knoten mehr hast.