在Python中实现深度优先树迭代器

Question

我正在尝试在Python中为不一定二进制树实现迭代器类.在使用树的根节点构造迭代器之后,next()可以重复调用其函数以按深度优先顺序(例如,此顺序)遍历树,最后None在没有剩余节点时返回.

这是Node树的基本类:

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

正如您在上面所看到的,我visited为第一种方法向节点引入了一个属性,因为我没有看到它的方法.通过额外的状态测量,Iterator该类看起来像这样:

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

这一切都很好,但我想摆脱对visited财产的需求,而不是诉诸递归或任何其他Node类改变.

我需要的所有状态都应该在迭代器中处理,但我对如何做到这一点感到茫然.保留整个树的访问列表是不可扩展的,并且不可能,因此必须有一种聪明的方法来使用堆栈.

特别让我感到困惑的是 - 因为next()功能当然会返回,我怎么能记住我没有标记任何内容或使用多余存储的地方？直觉上,我想到循环遍历子节点,但是当next()函数返回时,逻辑被破坏/遗忘!

更新 - 这是一个小测试:

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

如果你真的必须避免递归,这个迭代器工作:

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

话虽如此,我认为你在考虑这个问题太难了.一个好的'(递归)生成器也可以解决这个问题:

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

这两个都通过了你的测试:

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

Node.__iter__如果您愿意,可以轻松地使用非递归形式:

def __iter__(self):
   return node_depth_first_iter(self)