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

In Pseudocode:

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

Answer 2

Wenn Sie beim Wurzelknoten beginnen und nur die Eltern-/Kinderknoten besuchen, die Sie bereits besucht haben, gibt es auf keinen Fall um den Baum so zu durchlaufen, dass Sie einen Knoten besuchen, bevor Sie seine Vorgänger besuchen.

Jede Art von Traversal, Tiefe zuerst (rekursiv/Stapel-basiert), Breite zuerst (Warteschlangen-basiert), Tiefe begrenzt, oder einfach nur ziehen sie aus einer ungeordneten Menge, wird funktionieren.

Die "beste" Methode hängt vom jeweiligen Baum ab. Bei einem sehr hohen Baum mit wenigen Ästen würde die Methode "Breite zuerst" gut funktionieren. Bei Bäumen mit vielen Ästen ist die Methode "Tiefe zuerst" gut geeignet.

Da die Knoten tatsächlich Zeiger auf ihre Eltern haben, gibt es auch einen Algorithmus mit konstantem Speicherplatz, der jedoch viel langsamer ist.

Answer 3

Ich würde von der Suche in der Breite abraten, da die Raumkomplexität oft der Fluch dieses speziellen Suchalgorithmus ist. Möglicherweise ist die Verwendung des iterativen Vertiefungsalgorithmus eine bessere Alternative für diese Art von Anwendung, und er deckt dieselbe Art von Traversal ab wie die Breadth-First-Suche. Es gibt geringfügige Unterschiede im Umgang mit dem Rand von breadth-first search, es sollte aber nicht zu schwer sein, (Pseudo-)Code zu erstellen.

Referenz: http://en.wikipedia.org/wiki/Iterative_deepening

Answer 4

Hier ist ein wirklich nicht-rekursiver Ansatz: kein Stack, konstanter Platz. Dieser Python-Code geht davon aus, dass jeder Knoten eine Liste von Kindern enthält und dass die Knotenobjekte keine Gleichheit definieren, so dass die Funktion "index" 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, man könnte ihn noch ein wenig aufpolieren, prägnanter und leichter lesbar machen, aber das ist das Wesentliche.

Answer 5

Erstellen Sie eine Liste von Knoten an der Wurzel (Ebene 0), iterieren Sie über jeden Knoten der Reihe nach und suchen Sie nach direkten Kindern (deren Elternknoten der Knoten ist, von dem aus wir gerade suchen) (Ebene 1), wenn Sie mit Ebene 0 fertig sind, fahren Sie mit der Iteration auf Ebene 1 fort, und so weiter, bis Sie keine verbleibenden unbesuchten Knoten haben.