Récursif? en boucle sur n niveaux en Python

Question

Travailler en python Je souhaite extraire un jeu de données avec la structure suivante:

Chaque élément a un identifiant unique et l'identifiant unique de son parent. Chaque parent peut avoir un ou plusieurs enfants, dont chacun peut avoir un ou plusieurs enfants, à n niveaux, c'est-à-dire que les données ont une structure arborescente retournée. Alors qu'il a le potentiel de continuer à l'infini, en réalité, une profondeur de 10 niveaux est inhabituel, tout comme avoir plus de 10 frères et soeurs à chaque niveau.

Pour chaque élément de l'ensemble de données que je souhaite afficher, affichez tous les éléments pour lesquels cet élément est leur parent ... et ainsi de suite jusqu'à ce qu'il atteigne le bas de l'ensemble de données.

Faire les deux premiers niveaux est facile, mais je ne sais pas comment le rendre efficacement à travers les niveaux.

Tous les pointeurs très appréciés.

Answer 1

vous devriez probablement utiliser un defaultdictionary pour cela:

from collections import defaultdict  

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

alors vous pouvez imprimer récursive (avec indentation) comme

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

Answer 2

Etes-vous en train de dire que chaque article ne fait référence qu'à ses parents? Si oui, alors qu'en est-il

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

Cela renvoie une liste qui contient tous les éléments qui sont en quelque sorte descendus de l'élément.

Answer 3

Si vous voulez garder la structure de votre ensemble de données, cela produira une liste du format [id, [les enfants de id], ID2, [les enfants de ID2]]

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

Answer 4

que diriez-vous si mething comme celui-ci,

#!/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, []) 

Il est également intéressant de noter que Python a une assez faible limite de récursion par défaut, 1000 je pense.

Dans le cas où votre arbre devient vraiment assez profond, vous allez frapper très rapidement. Vous pouvez mettre en marche ce avec,

sys.setrecursionlimit(100000) 

et de vérifier avec,

sys.getrecursionlimit()