Gehen einen Baum, Eltern zuerst

Question

Was ist der beste Weg, alle Knoten einer verknüpften Struktur zu besuchen (alle Knoten haben Verweise auf Eltern und alle Kinder, Wurzelknoten haben Null als Eltern), so dass kein Knoten vor irgendwelchen besucht wird von seinen Vorfahren? Brownie Punkte für nicht-rekursive.

Answer 1

Pseudo-Code:

NodesToVisit = some stack or some list 
NodesToVisit.Push(RootNode) 

While NodesToVisit.Length > 0 
{ 
    CurNode = NodesToVisit.Pop() 
    For each Child C in CurNode 
     NodesToVisit.Push(C) 
    Visit(CurNode) (i.e. do whatever needs to be done) 
} 

bearbeiten: rekursive oder nicht?
Um technisch korrekt und wie durch AndreyT und andere in diesem Beitrag erwähnt, ist dieser Ansatz eine Form von ein rekursiver Algorithmus, wobei ein explizit verwaltet Stapel anstelle der CPU-Stack verwendet wird und wo die Rekursion findet auf der Ebene der While-Schleife statt. Das heißt, es ist von einer rekursiven Implementierung unterscheidet per se in ein paar feine, aber signifikante Möglichkeiten:

• Nur die „Variablen“ werden auf den Stapel geschoben; Es gibt keinen "Stapelrahmen" und eine zugeordnete Rücksprungadresse auf dem Stapel, die einzige "Rücksprungadresse" ist implizit in der while-Schleife, und es gibt nur eine Instanz davon.
• Der "Stapel" könnte als eine Liste verwendet werden, wobei der nächste "Rahmen" irgendwo in der Liste genommen werden könnte, ohne die Logik in irgendeiner Weise zu bremsen.

Answer 2

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) level 0 geht weiter zu iterating level 1 und so weiter, bis Sie keine noch nicht besuchten Knoten mehr haben.

Answer 3

Verwenden Sie eine Reihe von Knoten. Setzen Sie 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.

Answer 4

In Pseudo-Code:

currentList = list(root) 
nextList = list() 
while currentList.count > 0: 
    foreach node in currentList: 
     nextList.add(node.children) 
    currentList = nextList 

Answer 5

Sie suchen ein Vorordnungsdurchquerung suchen. Ich denke, Sie können es nicht rekursiv mit eine Warteschlange tun:. In Pseudocode:

Erstellen Sie eine leere Warteschlange, dann drücken Sie den Stammknoten.

while nonempty(q) 
    node = pop(q) 
    visit(node) 
    foreach child(node) 
    push(q,child) 

Answer 6

Breadth First Search

Answer 7

Wenn Sie an dem Wurzelknoten zu starten, und besuchen nur die Eltern/Kinder von Knoten, die Sie bereits besucht haben, gibt es keine Möglichkeit, den Baum so zu durchqueren, dass Sie einen Knoten besuchen, bevor seine Vorfahren zu besuchen.

Jede Art von Traversierung, Tiefe zuerst (rekursiv/stackbasiert), Breite zuerst (queuebasiert), tiefenlimitiert 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, aber es ist viel langsamer.

Answer 8

Wenn Sie Links zu allen untergeordneten Elementen und auch zum übergeordneten Element 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 gesamte Labyrinth zu durchqueren, besteht darin, bei jeder Kreuzung in den nächsten Gang links abzubiegen. (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.

Answer 9

Ich würde mit der ersten Suche der Breite nicht übereinstimmen, da Raumkomplexität häufig 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: http://en.wikipedia.org/wiki/Iterative_deepening

Answer 10

Hier ist ein wirklich nicht-rekursive Ansatz: kein Stapel, konstanter Raum. Dieser Python-Code wird davon ausgegangen, dass jeder Knoten eine Liste von Kindern enthält, und dass die Knotenobjekte definieren nicht Gleichheit, so dass die ‚Index‘ Funktion Identitäten vergleicht:

def walkTree(root, visit_func): 
    cur = root 
    nextChildIndex = 0 

    while True: 
     visit_func(cur) 

     while nextChildIndex >= len(cur.children) and cur is not root: 
      nextChildIndex = cur.parent.children.index(cur) + 1 
      cur = cur.parent 

     if nextChildIndex >= len(cur.children): 
      break 

     cur = cur.children[nextChildIndex] 
     nextChildIndex = 0 

Ich bin sicher, dass es aufpoliert werden könnte ein bisschen, übersichtlicher und einfacher zu lesen, aber das ist das Wesentliche.