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.Implementowanie pierwszego iteratora drzewa głębi w języku Python
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
Lista odwiedzanych * może być nieskalowalna, ale co z odwiedzanym zestawem, np. na podstawie identyfikatora obiektu węzła? – michaelb
To jednak może potencjalnie zawierać każdą etykietę. Chcę, aby iterator trzymał tylko podzbiór drzewa na raz. – nicole
Jaki jest oczekiwany wynik "małego testu"? –