python迭代器通过树与子列表 [英] python iterator through tree with list of children

问题描述

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

i don't get the full grasp on python iterators, i got an object with a list of children, and i want to iterate through this structure. I want to get the same behaviour as with the printall function but with an iterator.

    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

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

hope thats enough information, thanks

编辑：

我只是想能够遍历所有的叶子树和做一些对象的东西，即当我有一个实例时

i just want to be able to iterate through all the leafs of the tree and do something with the object, i.e. when i have an instance

    bla = t(3) 

我希望能够通过每个节点查看

i want to be able to go through every node with

    for x in bla:
            print x.a

例如。我想能够用每个x，
i只需要访问每个孩子一次

for example. i want to be able to something with each x, i just have to access every child once

推荐答案

听起来像您希望迭代器充当树遍历。研究 itertools 模块，你可以真正去的地方。

It sounds like you want the iterator to act as a tree traversal. Study the itertools module and you can really go places.

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 。但它确实通过一个简单的表达式产生了预期的结果。

EDIT: Below is the originally accepted implementation. It has a performance problem; I would remove it, but it seems wrong to remove content that was an accepted answer. It will fully traverse the entire structure, creating O(N*log[M](N)) generator objects (for a balanced tree with branching factor M containing N total elements), before yielding any values. But it does produce the desired result with a simple expression.

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

(The above implementation visits areas of the tree on demand and has only O(M+log[M](N)) generator objects in memory at a time. In both implementations, only O(log[M](N)) levels of nested generators are expected.)

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

这篇关于python迭代器通过树与子列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！