在Python树中迭代递归

Question

我在Python中写了一个树的类，但在创建迭代器时遇到了问题。我想要能够这样做：

phonebook = MyTree()
# Build up tree

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

但是它不工作（提示生成器对象没有key()和data()方法）。我的树类的__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

看起来你是在尝试遍历类型，而不是类型的实例。把这个：

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

改成：

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

Answer 2

你的函数 TreeIterator._next() 是一个生成器函数。这意味着当你调用它的时候，它会返回一个 迭代器。所以你可以把 _next() 的返回值存起来，然后对这个返回值调用 .next()，这样就能获取到这个迭代器的下一个元素。然而，你在 TreeIterator.next() 中做的事情是每次都返回一个 新创建的 迭代器，而这个迭代器从来没有被遍历过。这也解释了你收到的错误信息：你的迭代器并没有返回树的条目，而是返回了新的迭代器。

我认为解决这个问题最简单的方法是完全去掉 TreeIterator 类，把它的 ._next() 方法复制到你树类的 .__iter__() 方法中。也许还需要修正一些地方，但我不太了解你的树类。

Answer 3

试着把

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

看起来你是在返回一个迭代器，而不是一个具体的值。我觉得你的整体方法也太复杂了。

self._next(curr.left) 返回的是一个生成器/迭代器。它里面有很多值，而不仅仅是一个，所以你需要对它进行循环处理。