Python - Tree-traversal Frage

Ich habe eine harte Zeit mit tree traversal, und so vermeiden Sie es wie die Pest... normalerweise.

Habe ich eine Klasse, die eine Art-von (leicht vereinfachte version hier, aber funktionell identisch) wie:

class Branch(object):
    def __init__(self, title, parent=None):
        self.title = title
        self.parent = parent

Ich habe ein Wörterbuch, eine Reihe von Branch Instanzen, die Titel der einzelnen wie die Tasten:

tree = {'Foo Branch': foo, 'Sub-Foo Branch': sub_foo, 'Bar Branch': bar}

Nun, ich weiß, dass es komplexe algorithmen für die Herstellung traversal-Effizienz (z.B. MPTT, et al), insbesondere für den Einsatz mit Datenbank-getriebene Projekte, bei denen Effizienz die meisten Fragen. Ich bin nicht mit der Datenbank überhaupt, nur einfache in-memory-Objekte.

Angesichts der title einer Branch, die ich brauche, um eine list alle Nachfahren dieses Zweiges (Kinder, Kinder, Kinder, so-an) von tree so:

  1. Würden Sie immer noch empfohlen, mit einer komplizierten (für meinen algo-weniger Gehirn 🙂 Algorithmus wie MPTT für die Effizienz in meinem Fall, oder gibt es eine einfache Möglichkeit, dies zu erreichen in einer einzigen Funktion?
  2. Wenn ja, welche würden Sie empfehlen, zu wissen, ich bin nicht mit einer Datenbank?
  3. Können Sie ein Beispiel geben, oder ist dies viel größer als ich denke?

Hinweis: Dies ist keine Hausaufgabe. Ich bin nicht in der Schule. Ich bin wirklich nur das schlechte an algorithmen. Ich habe Django-MPTT für ein Projekt die benötigten DB-stored-Bäume... aber immer noch nicht, verstehen es sehr gut.

Wenn ich denke, ich werde sagen, dass die Antwort liegt in der Rekursion.

InformationsquelleAutor orokusaki | 2011-06-06

  1. 6

    http://en.wikipedia.org/wiki/Depth-first_search

    http://en.wikipedia.org/wiki/Tree_traversal

    Sie durchqueren wie folgt in zwei Durchgängen:

    • Ersten Durchlauf: Suchen nach die-query-Knoten mit dem entsprechenden Schlüssel. (Dieser Schritt ist unnötig, wenn Sie haben eine hashmap von alle der Knoten im gesamten Baum; Sie haben das (gute), so ist dieser Schritt nicht erforderlich.)

    • Zweiten Durchgang: Rufen Sie eine modifizierte version des Algorithmus auf die query-Knoten, aber diese Zeit, Wann immer Sie besuchen ein Knoten, der Ertrag (oder hängen Sie an eine nichtlokale Akkumulator-variable).

    Aber Ihre situation ist ein bisschen merkwürdig, denn normalerweise haben die Bäume Zeiger auf Kinder als auch, wie eine Art doppelt verkettete Liste. Leider haben wir nicht diese Informationen... aber glücklicherweise ist es einfach, die Informationen:

    nodes = tree.values()
for node in nodes:
    if node.parent:
        if not hasattr(node.parent, 'children'):
            node.parent.children = []
        node.parent.children +=[ node ]

    Jetzt können wir gehen, mit unserem Beispiel:

    def traverse(root, callback):
    """
        Peform callback on all nodes in depth-first order
        e.g. traverse(root, lambda x:print(x))
    """
    yield root, callback(root)
    for child in root.children:
        traverse(child)

def getAllDescendents(title):
    queryNode = titlesToNodes[title]  #what you call 'tree'
    for node,blah in traverse(queryNode, lambda x:None):
        yield node
    Danke. Können Sie vergleichen eine oder beide dieser mit MPTT, oder MPTT ist eine Erweiterung in die Tiefe-zuerst-Methode?
    die Definitionen von "MPTT" ich habe in der Lage, leicht zu finden sind imrannazar.com/Modified-Preorder-Tree-Traversal und imrannazar.com/Modified-Preorder-Tree-Traversal . Auf den ersten Blick, es scheint zu stehen für "Modified Preorder Tree Traversal" und besteht aus dem hinzufügen von extra-Nummern der Knoten, die Dinge irgendwie in ein Datenbank-Szenario. Sie sind nicht mit einer Datenbank, da alles im Speicher, so dass Sie gerade dabei sind eine Reine Preorder Traversal, noch hat es scheinen, wie Sie brauchen diese "MPTT" hacks da Sie arbeiten, im Arbeitsspeicher.

    InformationsquelleAutor ninjagecko

Schreibe einen Kommentar