具有子列表的树中的python迭代器

Question

我没有完全掌握python迭代器， 我得到一个带有子列表的对象，我想遍历这个结构。 我想得到与printall函数相同的行为，但是需要一个迭代器。

    class t:
            def __init__(self, i):
                    self.l = []
                    self.a = 0
                    for ii in range(i):
                            self.a = ii
                            self.l.append(t(i-1))

            def __iter__(self):
                    return self

            def next(self):
                    for i in self.l:
                            yield i.__iter__()
                    yield self

            def printall(self):
                    for i in self.l:
                            i.printall()
                    print self.a

希望这是足够的信息，谢谢

编辑：

我只想能够遍历树的所有叶，并对对象执行一些操作，即当我有一个实例时

    bla = t(3) 

我想通过每个节点

    for x in bla:
            print x.a

例如。我想每个x都能做点什么， 我只需要接触每个孩子一次

Answer 1

听起来你希望迭代器充当树遍历。学习itertools模块，你就可以真正地去各个地方。

from itertools import chain, imap

class t:
  def __init__(self, value):
    self.value = value
    self.children = []
  def __iter__(self):
    "implement the iterator protocol"
    for v in chain(*imap(iter, self.children)):
      yield v
    yield self.value

root = t(0)
root.children.append(t(1))
root.children.append(t(2))
root.children[1].children.append(t(3))
print list(iter(root))   # -> [1, 3, 2, 0]
print list(iter(root.children[1]))  # -> [3, 2]

编辑：下面是最初接受的实现。它有性能问题；我会删除它，但删除已被接受的答案的内容似乎是错误的。它将完全遍历整个结构，在生成任何值之前创建O(N*log[M](N))生成器对象（对于包含N总元素的分支因子M的平衡树）。但它确实通过一个简单的表达式产生了预期的结果。

（上面的实现按需访问树的各个区域，并且一次只有O(M+log[M](N))个生成器对象在内存中。在这两种实现中，只需要O(log[M](N))级别的嵌套生成器。）

from itertools import chain

def isingle(item):
  "iterator that yields only a single value then stops, for chaining"
  yield item

class t:
  # copy __init__ from above
  def __iter__(self):
    "implement the iterator protocol"
    return chain(*(map(iter, self.children) + [isingle(self.value)]))

Answer 2

我的第一个建议是在PEP-8后面用一个更清晰的类来更改类的名称。管理类名（如t）有点困难：

class Tree:
    def __init__(self, i):
        self.l = []
        self.a = 0
        for ii in range(i):
            self.a = ii
            self.l.append(Tree(i-1))

现在，您应该更改__iter__()方法以返回self中的下一个元素，而不是self本身-不需要双关：）方法__iter__()应该返回一个迭代器到原始对象，而不是对象本身：

def __iter__(self):
    return next(self)

接下来是困难的部分：方法next()。我总是发现很难编写递归迭代器，但这并非不可能：对于每个子级，对其进行迭代并生成迭代值：

def next(self):
    for i in self.l:
        for ii in i:
            yield ii
    yield self

由于该方法是递归的，因此它负责生成所有子代。当在叶节点（没有子节点的节点）上调用next()方法时，它将只返回节点本身。OTOH，当在带有子节点的节点上调用时，它将为每个子节点调用自己并产生返回值。这意味着它将被子节点等的子节点调用，直到叶节点。在被一个节点的所有子节点调用后（这意味着所有子节点都已产生），它应该产生自己的值，因此必须产生原始节点本身。

现在，您的printall()函数应该可以完美地工作了：

if __name__ == "__main__":
t = Tree(6)
t.printall()

一些最终考虑：

• 始终使类扩展object：

  类树（对象）：

• 我打赌你想写一个__init__()方法，如下所示：

  def __init__(self, i):
      self.l = []
      self.a = i
      for ii in range(i):
          self.l.append(Tree(i-1))
  

• wberry解决方案更好，因为它更简洁，而且可能更高效。但是，我认为OP正在研究树、递归等，所以我认为一个更硬编码的解决方案会有指导意义：）

Answer 3

从您发布的代码中可以清楚地看到，您缺少的是生成器的功能，以及如何__iter__和next应该如何工作

所以让我们从迭代器协议开始。如果一个对象在调用其__iter__方法时返回迭代器，并且迭代器是一个具有next方法的对象，可以调用0次或多次，并且最终应该引发StopIteration。

某些类型的对象成为它们自己的迭代器（具有__iter__返回self）并不罕见，但这通常仅限于对象本身以某种方式表示某个对象内部的位置。例如，内置的file对象是它自己的迭代器，因为文件有一个内在的seek位置（可以使用file.seek()和file.tell()来操作）。其他表示集合整体性的对象，比如list，返回的不是它们自己。

所以，你的树听起来更像后者而不是前者；它没有表示它在哪个节点上的position属性；它同时是所有节点，所以它可能不应该有一个next()方法；__iter__需要返回其他东西。

把我们带到发电机那里。当一个普通函数包含一个yield语句时，它自动地不是一个函数，而是一个生成器。区别在于，当您调用一个函数时，它的主体被执行（并且可能返回一个值）。当您调用生成器时，它会立即返回，而根本不执行主体；相反，您会得到一个迭代器！当您遍历它时，函数体将被调用；每次都前进到下一个yield，直到它最终返回。

所以，把这些放在一起

class t:
    def __init__(self):
        self.l = []
        self.a = 0

    def __iter__(self):
        # first, yield everthing every one of the child nodes would yield.
        for child in self.l:
            for item in child:
                # the two for loops is because there's multiple children, and we need to iterate
                # over each one.
                yield item

        # finally, yield self
        yield self

但是，因为我们所做的是迭代一系列的迭代器（还有一件事，self），itertools.chain就像在接受的答案中一样，真的很有意义。