Rekurzívna funkcia pre stromy v Pythone - python, rekurzia, strom

Snažím sa vytvoriť funkciu v Pythone, ktorá vezme ľubovoľný uzol stromu a vyplní zoznam zoznamov podľa zadaného uzla.

Vzhľadom na tento zle nakreslený strom:

Ak napríklad začneme v uzle 5, mali by sme získať:

• Zoznam obsahujúci všetky uzly s rovnakým nadradeným uzlom, vrátane toho, na ktorom sme začali (4 a 5)
• Akékoľvek detské uzly, ale nie ich deti (6).
• Rodičovské uzly a všetky nadradené uzly s nimirodič a ich nadradené uzly atď., kým sa nedostaneme ku koreňovému uzlu, ale nezahŕňame koreňový uzol (v tomto prípade iba 2 a 3, ale ak bol strom hlbší a začali sme nižšie, bolo by viac) tu.

Uzly by mali skončiť v zozname zoznamov, jeden zoznam pre každú hĺbku.

Uzly v pythone:

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

Vidíme iba rodičov, nie deti, ale toto je formát údajov, s ktorým musím bohužiaľ pracovať.

Ak teda vezmeme uzol 5, chceme skončiť zoznamom uzlov, ktorý bude vyzerať takto:

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

Toto je kód, ktorý som doteraz dostal. Myslím, že rekurzívna funkcia je pravdepodobne najjednoduchšia cesta. Nanešťastie sa zdá, že nemá nič spoločné s tým, čo si myslím, že by malo, a samozrejme, že robím niečo veľmi zlé. od prípadného odovzdania, čo by bolo oveľa jednoduchšie.

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)

Tu je výstup:

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

Nie som si úplne istý, kde sa tu mýlim.

odpovede:

5 pre odpoveď č. 1

Problém je tu

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

Aktuálny parent bude prepísaný rodičom.

Navyše by ste mali pridať return node_list na konci funkcie alebo použitie node_list ako výsledky.

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

---