Рекурсивный? зацикливание на n уровней в Python

Question

Работая в Python, я хочу извлечь набор данных со следующей структурой:

Каждый элемент имеет уникальный идентификатор и уникальный идентификатор его родителя. У каждого родителя может быть один или несколько дочерних элементов, у каждого из которых может быть один или несколько дочерних элементов до n уровней, то есть данные имеют перевернутую древовидную структуру. В то время как у него есть потенциал, чтобы продолжаться бесконечность, в действительности глубина 10 уровней необычна, так как имеет более 10 братьев и сестер на каждом уровне.

Для каждого элемента в наборе данных, который я хочу показать, отображаются все элементы, для которых этот элемент является их родителем ... и так далее, пока он не достигнет нижней части набора данных.

Выполнить первые два уровня легко, но я не уверен, как сделать так, чтобы он эффективно проходил вниз по уровням.

Любые указатели очень ценятся.

Answer 1

Если вы хотите сохранить структуру вашего набора данных, вы получите список в формате [id, [children of id], id2, [children of id2]]

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

Answer 2

вы, вероятно, должны использовать 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)

Answer 3

Вы говорите, что каждый предмет содержит ссылку только на своих родителей? Если так, то как насчет

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

Возвращает список, содержащий все элементы, которые каким-то образом произошли от элемента.

Answer 4

Как насчет этого,

#!/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()