Spaziergang auf einem Baum, Eltern zuerst

Question

Was ist der beste Weg, um alle Knoten eines verknüpften Baums zu besuchen (alle Knoten haben Verweise 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-rekursiv.

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)
}

Editar : Rekursiv oder nicht?
Um technisch korrekt zu sein, und wie von AndreyT und anderen in diesem Beitrag hervorgehoben, ist dieser Ansatz eine Form von ein rekursiver Algorithmus, bei dem ein explizit verwalteter Stack anstelle des CPU-Stacks verwendet wird und die Rekursion auf der Ebene der While-Schleife stattfindet. Damit unterscheidet er sich von einer rekursiven Implementierung per se in einer Reihe von subtilen, aber bedeutsamen Aspekten:

• Nur die "Variablen" werden auf den Stack geschoben; es gibt keinen "Stackframe" und keine zugehörige Rücksprungadresse auf dem Stack, die einzige "Rücksprungadresse" ist implizit für die while-Schleife, und es gibt nur eine Instanz davon.
• Der "Stack" könnte als Liste verwendet werden, wobei der nächste "Frame" an beliebiger Stelle in der Liste stehen könnte, ohne die Logik in irgendeiner Weise zu bremsen.

Answer 2

Erste Suche in der Breite

Answer 3

Sie suchen nach einer Vorbestellungsüberquerung. Ich denke, man kann es nicht-rekursiv machen mit einer Warteschlange:. In Pseudocode:

Erstellen Sie eine leere Warteschlange und schieben Sie dann den Root-Knoten.

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

Answer 4

Wenn Sie Links zu allen Kindern und auch zum Elternteil haben, dann ist der nicht-rekursive Algorithmus ziemlich trivial. Vergessen Sie einfach, dass Sie einen Baum haben. Stellen Sie sich ein Labyrinth vor, in dem jede Eltern-Kind-Verknüpfung ein gewöhnlicher bidirektionaler Korridor von einer Abzweigung zur anderen ist. Alles, was Sie tun müssen, um das gesamte Labyrinth zu durchlaufen, ist, an jeder Kreuzung in den nächsten Korridor auf der linken Seite einzubiegen. (Alternativ kann man sich das Labyrinth auch so vorstellen, dass man mit der linken Hand immer die Wand auf der linken Seite berührt). Wenn du an der Wurzelkreuzung beginnst (und dich in eine beliebige Richtung bewegst), gehst du den ganzen Baum entlang und besuchst immer die Eltern vor den Kindern. Jeder "Korridor" wird in diesem Fall zweimal durchlaufen (in die eine und in die andere Richtung), und jede "Kreuzung" (Knotenpunkt) wird so oft besucht, wie viele "Korridore" sie verbinden.

Answer 5

Verwenden Sie eine Reihe von Knotenpunkten. Legen Sie die Wurzel in die Menge, um zu beginnen. Ziehen Sie dann in einer Schleife einen Knoten aus der Menge, besuchen Sie ihn und fügen Sie dann seine Kinder in die Menge ein. Wenn die Menge leer ist, sind Sie fertig.