Implementazione di un iteratore di albero depth-first in Python

Question

Sto cercando di implementare una classe iteratore per alberi non necessariamente binari in Python. Dopo che l'iteratore è stato creato con il nodo radice di un albero, la sua funzione next() può essere richiamata ripetutamente per attraversare l'albero in ordine di profondità (ad esempio, this order), restituendo infine None quando non sono rimasti nodi.

Ecco la Node classe di base per un albero:

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 

Come potete vedere sopra, ho introdotto una proprietà visited ai nodi per il mio primo approccio, dal momento che non ho visto un modo intorno ad esso . Con questo ulteriore misura di Stato, la classe Iterator si presenta così:

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

Questo è tutto bene, ma voglio sbarazzarsi della necessità per la proprietà visited, senza ricorrere a ricorsione o altre alterazioni alla classe Node.

Tutto lo stato di cui ho bisogno dovrebbe essere curato nell'iteratore, ma non riesco a capire come si possa fare. Mantenere una lista visitata per l'intero albero non è scalabile e fuori questione, quindi ci deve essere un modo intelligente per usare lo stack.

Ciò che soprattutto mi confonde è questo - poiché la funzione-, ovviamente, restituisce, come posso ricordare dove sono stato senza contrassegnare qualcosa o utilizzare la memoria in eccesso? Intuitivamente, penso al looping sui bambini, ma quella logica è rotta/dimenticata quando la funzione restituisce!

AGGIORNAMENTO - Ecco un piccolo 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

Se davvero necessario evitare la ricorsione, questo iteratore funziona:

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

---

Detto questo, penso che tu sia pensando troppo a questo. A '(ricorsiva) generatore di buona ole fa anche il trucco:

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 

entrambi questi passano i test:

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 

e si può facilmente rendere Node.__iter__ usare la forma non ricorsiva, se si preferisce :

def __iter__(self): 
    return node_depth_first_iter(self) 

Answer 2

che potrebbe ancora potenzialmente contenere ogni etichetta, però. Voglio l'iteratore per mantenere solo un sottoinsieme dell'albero alla volta.

Ma già sono con tutto. Ricorda che un oggetto è essenzialmente un dizionario con una voce per ogni attributo. Avere self.visited = False nel __init__ di Node significa che si sta memorizzando una chiave ridondante "visited" e il valore False per ogni singolo oggetto Node indipendentemente da cosa. Un set, almeno, ha anche il potenziale di non che contiene ogni singolo ID di nodo.Prova questo:

class Iterator(object): 
    def __init__(self, root): 
     self.visited_ids = set() 
     ... 

    def next(self): 
     ... 
     #self.current.visited = True 
     self.visited_ids.add(id(self.current)) 
     ... 
       #if not child.visited: 
       if id(child) not in self.visited_ids: 

Cercare l'ID nell'insieme dovrebbe essere veloce come accedere all'attributo di un nodo. L'unico modo in cui questo può essere più dispendioso della soluzione è il sovraccarico dell'oggetto stesso (non i suoi elementi), che è solo un problema se si hanno più iteratori simultanei (cosa che ovviamente non si fa, altrimenti l'attributo nodo visited non può essere utile a voi).