Fonction récursive pour les arbres en Python

Je suis en train de faire une fonction en Python, qui prend l'arbitraire d'un nœud d'un arbre, et remplit une liste de listes en fonction du nœud donner.

Le suivant badly drawn arbre:

Si nous commençons à, par exemple, le nœud 5, on doit faire:

• Une liste contenant tous les nœuds avec le même nœud parent, y compris celui que nous avons commencé à (4 et 5)
• Tous les nœuds enfants, mais pas leurs enfants (6).
• Nœuds parents et de tous les nœuds parents avec le même parent, et de leurs parents des nœuds, etc. jusqu'à ce que nous obtenons pour le nœud racine, mais pas y compris le nœud racine (juste 2 et 3 dans ce cas, mais si l'arbre était plus profond et nous avons commencé à baisser, il n'y aurait plus ici.

Et les nœuds devrait se retrouver dans une liste de listes, une liste pour chaque profondeur.

Les nœuds en python:

nodes = [
    {'id': 1, 'parent': None},
    {'id': 2, 'parent': 1},
    {'id': 3, 'parent': 1},
    {'id': 4, 'parent': 2},
    {'id': 5, 'parent': 2},
    {'id': 6, 'parent': 5},
    {'id': 7, 'parent': 6},
    {'id': 8, 'parent': 3}
]

Nous ne pouvons voir les parents, pas les enfants, mais c'est le format de données que j'ai à travailler avec, malheureusement.

Donc à partir de cela, si nous prenons le nœud 5, nous voulons jusqu'à la fin avec une liste de noeud à la recherche de quelque chose comme ceci:

nl = [
    [{'id': 6, 'parent': 5}],
    [{'id': 4, 'parent': 2}, {'id': 5, 'parent': 2}],
    [{'id': 2, 'parent': 1}, {'id': 3, 'parent': 1}],
]

C'est le code que j'ai jusqu'ici. Je l'ai trouver une fonction récursive est probablement la façon la plus simple. Malheureusement, il semble ne rien faire comme ce que je pense qu'il devrait, et évidemment, je suis en train de faire quelque chose de très mal. Et ce code ne même pas envisager de geting les nœuds enfants dont je ne suis pas entièrement sûr de savoir comment faire face à tout, à part éventuellement la remise de l'après, ce qui serait beaucoup plus facile.

node_list = []

def pop_list(nodes=None, parent=None, node_list=None):
    if parent is None:
        return node_list
    node_list.append([])
    for node in nodes:
        if node['parent'] == parent:
            node_list[-1].append(node)
        if node['id'] == parent:
            parent = node['parent']
    return pop_list(nodes, parent, node_list)

print pop_list(nodes, 5, node_list)

Voici le résultat:

[[], [{'id': 3, 'parent': 1}], []]

Pas exactement où je vais mal ici.

source d'informationauteur Tom Carrick