递归？Python中循环到n层

Question

在使用Python的时候，我想提取一个数据集，这个数据集的结构是这样的：

每个项目都有一个独特的ID，还有一个它父级的独特ID。每个父级可以有一个或多个子级，而每个子级也可以有一个或多个自己的子级，这样一直往下可以有很多层，也就是数据呈现出一种倒置的树状结构。虽然理论上可以无限延伸，但实际上，深度达到10层就已经很少见了，而且每一层的兄弟节点超过10个也不常见。

对于数据集中的每个项目，我想展示所有以这个项目为父级的项目……一直到数据集的最底层。

处理前两层是比较简单的，但我不太确定如何高效地递归地向下遍历各层。

如果能给点建议就太好了。

Answer 1

你是在说每个项目只保存对它父级的引用吗？如果是这样的话，那这个代码块会怎么样呢：

def getChildren(item) :
    children = []
    for possibleChild in allItems :
        if (possibleChild.parent == item) :
            children.extend(getChildren(possibleChild))
    return children

这个代码会返回一个列表，里面包含所有以某种方式从这个项目派生出来的项目。

Answer 2

如果你想保持数据集的结构，这样做会生成一个列表，格式是 [id, [id的子项], id2, [id2的子项]]

def children(id):                                                                         
    return [id]+[children(x.id) for x in filter(lambda x:x.parent == id, items)]

Answer 3

你可能应该使用一个默认字典来处理这个问题：

from collections import defaultdict    

itemdict = defaultdict(list)
for id, parent_id in itemlist:
   itemdict[parent_id].append(id)

然后你可以递归地打印出来（带有缩进），像这样：

def printitem(id, depth=0):
    print '  '*depth, id
    for child in itemdict[id]:
        printitem(child, depth+1)