递归迭代（在Python树）

我用Python编写的一个树类，但我有它创造迭代问题，我希望能够做到递归迭代（在Python树）

phonebook = MyTree() 
# Build up tree 

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

但它不工作（说生成器对象没有key（）和data（））。 My Tree类的__iter__函数返回我创建的迭代器类。这是我到目前为止（我知道这是错误的，它不工作，因为它返回一个生成器对象，因为这是什么产量，我想它记住它在递归中的位置虽然..我不能使用返回）。基本上我只想返回节点。

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)

来源

2010-12-16 robev

尝试改变

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)返回一个生成器/迭代器。它包含一堆值，而不仅仅是一个，所以你需要循环。

来源

2010-12-16 16:39:54 robert

这工作，我真的见过这之前，但我不能得到它的工作。你能解释为什么这个工作吗？对于self_next（curr.left）中的x，我仍然不太明白。 – robev 2010-12-16 16:45:27

您的功能TreeIterator._next()是一个生成器函数。这意味着它在被调用时返回一个迭代器。因此，您可以将返回值_next()存储在此返回值上，并调用.next()以获取此迭代器的后续元素。另一方面，你所做的总是返回一个新创建的迭代器TreeIterator.next()，这是永远不会迭代。这也解释了你得到的错误信息：你的迭代器不是返回树条目，而是新的迭代器。

我认为这个问题最简单的解决方法是完全删除TreeIterator类，并将其._next()方法复制到树类的.__iter__()方法。也许有些东西需要修正，但我不知道你的树类。

来源

2010-12-16 16:38:17

感谢我摆脱了类及其所有属性（这是没有必要）的。然而，它仍然没有奏效，罗伯特的回答确定了主要问题。 – robev 2010-12-16 16:49:05

@robev：其实这两者都是“主要问题”。您需要修复这两个错误以使其正常工作。但很高兴我们可以帮助你:) – 2010-12-16 16:53:03

看起来好像你正试图对类型进行迭代，而不是类型的实例。更改此：

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

到：

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

来源

2010-12-16 16:40:49

对不起，这是一个错字，我正在做＃2 :) – robev 2010-12-16 16:43:33

递归迭代（在Python树）

回答

相关问题