Implementieren eines Depth-First-Tree-Iterators in Python

Question

Ich versuche, eine Iterator-Klasse für nicht notwendigerweise binäre Bäume in Python zu implementieren. Nachdem der Iterator mit dem Wurzelknoten eines Baums konstruiert wurde, kann seine next()-Funktion wiederholt aufgerufen werden, um den Baum in der Tiefe - erste Ordnung (z. B. this order) zu durchlaufen, wobei schließlich None zurückgegeben wird, wenn keine Knoten mehr übrig sind.

Hier ist die grundlegende Node Klasse für einen Baum:

class Node(object): 

    def __init__(self, title, children=None): 
     self.title = title 
     self.children = children or [] 
     self.visited = False 

    def __str__(self): 
     return self.title 

Wie Sie oben sehen können, ich führte eine visited Eigenschaft auf den Knoten für meinen ersten Ansatz, da ich nicht einen Weg, um es zu sehen war . Mit diesen Extramaß Zustand sieht die Iterator Klasse wie folgt:

class Iterator(object): 

    def __init__(self, root): 
     self.stack = [] 
     self.current = root 

    def next(self): 
     if self.current is None: 
      return None 

     self.stack.append(self.current) 
     self.current.visited = True 

     # Root case 
     if len(self.stack) == 1: 
      return self.current 

     while self.stack: 
      self.current = self.stack[-1] 
      for child in self.current.children: 
       if not child.visited: 
        self.current = child 
        return child 

      self.stack.pop() 

Das alles ist schön und gut, aber ich mag für die visited Eigenschaft von der Notwendigkeit zu befreien, ohne zu Rekursion zurückgreifen oder anderen Veränderungen in die Node Klasse.

Der gesamte Zustand, den ich brauche, sollte im Iterator erledigt werden, aber ich weiß nicht, wie das gemacht werden kann. Eine besuchte Liste für den gesamten Baum zu halten ist nicht skalierbar und kommt nicht in Frage, also muss es einen cleveren Weg geben, den Stapel zu benutzen.

Was mich besonders verwirrt ist das - seit die next() Funktion natürlich zurückkehrt, wie kann ich mich erinnern, wo ich gewesen bin, ohne irgendetwas zu markieren oder überschüssigen Speicher zu verwenden? Intuitiv denke ich daran, über Kinder zu schleifen, aber diese Logik ist gebrochen/vergessen, wenn die next() Funktion zurückkehrt!

UPDATE - Hier ist ein kleiner Test:

tree = Node(
    'A', [ 
     Node('B', [ 
      Node('C', [ 
       Node('D') 
       ]), 
      Node('E'), 
      ]), 
     Node('F'), 
     Node('G'), 
     ]) 

iter = Iterator(tree) 

out = object() 
while out: 
    out = iter.next() 
    print out 

Answer 1

Wenn Sie wirklich Rekursion vermeiden müssen, diese Iterator funktioniert:

from collections import deque 

def node_depth_first_iter(node): 
    stack = deque([node]) 
    while stack: 
     # Pop out the first element in the stack 
     node = stack.popleft() 
     yield node 
     # push children onto the front of the stack. 
     # Note that with a deque.extendleft, the first on in is the last 
     # one out, so we need to push them in reverse order. 
     stack.extendleft(reversed(node.children)) 

---

das gesagt ist, glaube ich, dass du bist darüber nachzudenken, zu schwer. Ein gut ole‘(rekursiv) Generator funktioniert auch den Trick:

class Node(object): 

    def __init__(self, title, children=None): 
     self.title = title 
     self.children = children or [] 

    def __str__(self): 
     return self.title 

    def __iter__(self): 
     yield self 
     for child in self.children: 
      for node in child: 
       yield node 

beides passieren Ihre Tests:

expected = ['A', 'B', 'C', 'D', 'E', 'F', 'G'] 
# Test recursive generator using Node.__iter__ 
assert [str(n) for n in tree] == expected 

# test non-recursive Iterator 
assert [str(n) for n in node_depth_first_iter(tree)] == expected 

und man kann leicht Node.__iter__ die nicht-rekursive Form verwenden, wenn Sie es vorziehen, :

def __iter__(self): 
    return node_depth_first_iter(self) 

Answer 2

Das nach wie vor potentiell jedes Etikett halten konnte, though. Ich möchte, dass der Iterator immer nur eine Teilmenge der Struktur auf einmal speichert.

Aber Sie bereits sind alles zu halten. Denken Sie daran, dass ein Objekt im Wesentlichen ein Wörterbuch mit einem Eintrag für jedes Attribut ist. Mit self.visited = False in der __init__ von Node bedeutet, dass Sie einen redundanten "visited" Schlüssel und False Wert für jedes einzelne Objekt Node egal was speichern. Ein Satz hat zumindest auch das Potential von nicht, der jede einzelne Knoten-ID enthält.Versuchen Sie dies:

Nachschlagen die ID in der Menge sollte genauso schnell sein wie den Zugriff auf ein Knoten Attribut. Die einzige Möglichkeit, die dies verschwenderischer als Ihre Lösung sein kann, ist der Overhead des Set-Objekts selbst (nicht seiner Elemente), was nur von Bedeutung ist, wenn Sie mehrere gleichzeitige Iteratoren haben (was Sie offensichtlich nicht tun, sonst könnte der Knoten Attribut couldn 't dir nützlich sein).