python - 迭代递归(在 Python 树中)

Question

我已经用 Python 编写了一个 Tree 类，但是我在为它创建迭代器时遇到了问题我希望能够做到

phonebook = MyTree()
# Build up tree

for node in phonebook:
    print "%s: %s" % (node.key(), node.data())

但它不起作用(说生成器对象没有 key() 和 data())。我的 Tree 类的 __iter__ 函数返回我创建的迭代器类。到目前为止，这是我所拥有的(我知道这是错误的并且它在返回生成器对象时不起作用，因为这就是 yield 所做的，我希望它记住它在递归中的位置......所以我不能使用 return) .基本上我只想按顺序返回节点。

class TreeIterator():
    def __init__(self, root, size):
        self._current = root
        self._size = size
        self.num_visited = 0

    def __iter__(self):
        return self

    def next(self):
        return self._next(self._current)

    def _next(self, curr):
        self.num_visited = self.num_visited + 1
        if self.num_visited == self._size:
            raise StopIteration

        if curr.left is not None and curr.left is not TreeNode.NULL:
            yield self._next(curr.left)

        yield curr

        if curr.right is not None and curr.right is not TreeNode.NULL:
            yield self._next(curr.right)   

Answer 1

尝试改变

if curr.left is not None and curr.left is not TreeNode.NULL:
    yield self._next(curr.left)

yield curr

if curr.right is not None and curr.right is not TreeNode.NULL:
    yield self._next(curr.right)   

进入

if curr.left is not None and curr.left is not TreeNode.NULL:
    for x in self._next(curr.left):
        yield x

yield curr

if curr.right is not None and curr.right is not TreeNode.NULL:
    for x in self._next(curr.right):
        yield x

看起来您正在yield一个迭代器，而不是一个值。我还认为您的一般方法太复杂了。

self._next(curr.left) 返回一个生成器/迭代器。它包含一堆值，而不仅仅是一个值，因此您需要遍历它。