递归？在Python中循环到n级

在python中工作我想提取具有以下结构的数据集：递归？在Python中循环到n级

每个项目都有一个唯一的ID和其父项的唯一ID。每个父母可以有一个或多个孩子，每个孩子可以有一个或多个自己的孩子，也可以有n个孩子，即数据具有倒转的树状结构。虽然它有潜力继续发展，但实际上10个水平的深度并不常见，每个水平有10个以上的兄弟姐妹。

对于数据集中的每个项目，我想显示显示该项目是其父项的所有项目，等等，直到它到达数据集的底部。

做前两个级别很容易，但我不确定如何使其高效地遍历级别。

任何指针非常赞赏。

来源

2009-08-07 notreadbyhumans

你应该使用defaultdictionary此：

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)

来源

2009-08-07 22:27:11 Jimmy

你是说每个项目只保留对其父母的引用吗？如果是这样，那么怎么样

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

这将返回一个列表，其中包含所有项目后退的项目。

来源

2009-08-07 21:45:59 pfhayes

我是在想，这将返回是一个给定项目的后代项目的大名单，从正确的级别，但是你会失去数据集的结构？ – notreadbyhumans 2009-08-07 21:57:56

所以，这与这个单行列表理解相同：“def getChildren（item）： return [getChildren（child）for child in allItems if child.parent == item]” 我从来没有见过列表理解递归之前。 – hughdbrown 2009-08-07 22:53:32

如果你想保持你的数据集的结构，这会产生格式的列表[ID，[ID的孩子]，ID2，[的ID2]儿童]

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

来源

2009-08-07 22:19:50 ACoolie

如何使这样的方法，


#!/usr/bin/python                            

tree = { 0:(None, [1,2,3]), 
     1:(0, [4]), 
     2:(0, []), 
     3:(0, [5,6]), 
     4:(1, [7]), 
     5:(3, []), 
     6:(3, []), 
     7:(4, []), 
     } 

def find_children(tree, id): 
    print "node:", id, tree[id] 
    for child in tree[id][1]: 
     find_children(tree, child) 

if __name__=="__main__": 
    import sys 
    find_children(tree, int(sys.argv[1])) 

$ ./tree.py 3 
node: 3 (0, [5, 6]) 
node: 5 (3, []) 
node: 6 (3, [])

值得注意的是，python有一个相当低的默认递归限制，1000我认为。

如果你的树实际上变得很深，你会很快达到目的。可以杀青这个了，


sys.setrecursionlimit(100000)

，并检查它，


sys.getrecursionlimit()

来源

2009-08-08 15:44:28 si28719e

递归？在Python中循环到n级

回答

相关问题