Implementowanie pierwszego iteratora drzewa głębi w języku Python

Question

Próbuję zaimplementować klasę iteratora dla niekoniecznie-binarnych drzew w języku Python. Po zbudowaniu iteratora z węzłem głównym drzewa, jego funkcja next() może być wielokrotnie wywoływana w celu przechodzenia przez drzewo w pierwszej kolejności głębi (na przykład this order), ostatecznie zwracając None, gdy nie ma już żadnych węzłów.

Oto podstawowe Node klasa na drzewie:

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 

Jak widać powyżej, wprowadziłem właściwość visited do węzłów na moim pierwszym podejściu, ponieważ nie widzę sposób wokół niego . Dzięki tej dodatkowej miary stanu, klasa Iterator wygląda następująco:

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

To wszystko jest dobrze, ale chcę, aby pozbyć się konieczności nieruchomości visited, bez uciekania się do rekursji lub jakichkolwiek innych zmian do klasy Node.

Cały stan, którego potrzebuję powinien być zajęty w iteratorze, ale nie mam pojęcia, jak to zrobić. Trzymanie listy odwiedzonych dla całego drzewa jest nieskalowane i nie wchodzi w grę, więc musi być sprytny sposób użycia stosu.

To, co mnie szczególnie kręci, to - skoro funkcja next(), oczywiście, zwraca, jak mogę zapamiętać, gdzie byłem, nie oznaczając niczego ani nie używając nadmiernej pamięci? Intuicyjnie myślę o pętli nad dziećmi, ale ta logika jest zepsuta/zapomniana, gdy funkcja next() powraca!

AKTUALIZACJA - Oto mały 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

Jeśli naprawdę musi unikać rekurencji, to iterator działa:

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

---

Z powiedział, że myślę, że jesteś myślenie o tym zbyt trudne. Dobrym-ole”(rekurencyjne) generator ma również 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 

oba te zdać testy:

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 

i można łatwo zrobić Node.__iter__ skorzystać z formularza nierekursywnych jeśli wolisz :

def __iter__(self): 
    return node_depth_first_iter(self) 

Answer 2

To mogłoby potencjalnie nadal trzymać każdą etykietę, choć. Chcę, aby iterator zachowywał tylko podzbiór drzewa na raz.

Ale już są trzymając wszystko. Pamiętaj, że obiekt jest zasadniczo słownikiem z wpisem dla każdego atrybutu. Posiadanie self.visited = False w __init__ z Node oznacza, że ​​przechowujesz nadmiarowy klucz "visited" i wartość False dla każdego pojedynczego obiektu Node bez względu na to, co. Zbiór, co najmniej, ma także potencjał , a nie posiadania każdego identyfikatora pojedynczego węzła.Wypróbuj to:

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: 

Wyszukiwanie identyfikatora w zestawie powinno być równie szybkie jak uzyskanie dostępu do atrybutu węzła. Jedynym sposobem, który może być bardziej marnotrawny niż twoje rozwiązanie, jest narzut związany z samym obiektem (nie jego elementami), co jest problemem tylko, jeśli masz wiele równoczesnych iteratorów (których oczywiście nie robisz, w przeciwnym razie atrybut węzła visited mógłby nie być przyda ci się).