python - recursiva - reglas de recursividad

Función recursiva para árboles en Python

Question

Estoy intentando hacer una función en Python, que toma un nodo arbitrario de un árbol, y completa una lista de listas basadas en el nodo give.

Dado el siguiente árbol mal dibujado:

Si comenzamos, por ejemplo, en el nodo 5, deberíamos obtener:

• Una lista que contiene todos los nodos con el mismo nodo primario, incluido el que comenzamos en (4 y 5)
• Cualquier nodo infantil, pero no sus hijos (6).
• Nodos principales y cualquier nodo primario con el mismo padre, y los nodos de sus padres, etc. hasta que lleguemos al nodo raíz, pero sin incluir el nodo raíz (solo 2 y 3 en este caso, pero si el árbol fue más profundo y comenzamos más bajo, habría más aquí.

Y los nodos deberían terminar en una lista de listas, una lista para cada profundidad.

Los nodos 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}
]

Solo podemos ver a los padres, no a los niños, pero este es el formato de datos con el que tengo que trabajar, lamentablemente.

Entonces, de esto, si tomamos el nodo 5, queremos terminar con una lista de nodos que se parezca a esto:

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

Este es el código que tengo hasta ahora. Me imagino que una función recursiva es probablemente la forma más simple. Desafortunadamente, parece no hacer nada de lo que creo que debería hacer, y obviamente estoy haciendo algo muy malo. Y este código ni siquiera considera administrar los nodos secundarios, de los que no estoy del todo seguro de cómo lidiar, además de posiblemente entregar los siguientes, lo cual sería mucho más fácil.

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)

Aquí está el resultado:

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

No estoy exactamente seguro de dónde me estoy equivocando aquí.

Answer 1

El problema está aquí

    if node[''id''] == parent:
        parent = node[''parent'']

El parent actual será sobrescrito por su padre.

Además, debe agregar return node_list al final de la función o usar node_list como resultados.

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:
            next_parent = node[''parent'']

    pop_list(nodes, next_parent, node_list)
    return node_list

>>> print pop_list(nodes, 5, node_list)
[[{''id'': 6, ''parent'': 5}], [{''id'': 4, ''parent'': 2}, {''id'': 5, ''parent'': 2}], [{''id'': 2, ''parent'': 1}, {''id'': 3, ''parent'': 1}]]