Pythonの木の再帰関数

Question

私はPythonで関数を作ろうとしています。その関数はツリーの任意のノードをとり、そのノードに基づいてリストを生成します。

を考えると、次ひどく描かれた木：

私たちは、たとえば、ノード5は、我々が得るべきである、で起動した場合：

• 同じ親を持つすべてのノードを含むリスト（4と5）で始まったノードを含むノード
• 子ノードはありませんが、子ノードはありません（6）。
• ルートノードに到達するまで親ノードと同じ親ノードとその親ノードを持つ親ノードはありますが、ルートノードは含まれません（この場合2と3だけですが、ツリーが深い場合。私たちは

より、ここがあると思います、下開始したノードは、リストのリスト内の各深さに1つのリストを終了する必要が

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

子供のみではなく親しか見ることはできませんが、これはデータですrmat私は悲しいことに、仕事をしなければならない。我々はノード5を取る場合

だからこれから、我々はこのような何かを探しているノードリストで終わるしたい：

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

これは私がこれまで持っているコードです。私は再帰関数はおそらく最も簡単な方法だと考えています。残念ながら、それは私がそれがすべきだと思うようなことは何もしていないようです。明らかに私は何か非常に間違っています。そして、このコードでは子ノードを取得することは考慮されていません。子ノードを処理する方法は完全にはわかりませんが、あとで手続きするほうがはるかに簡単です。ここで

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) 

が出力されます：私は間違ってここに行くよどこ

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

は正確にわかりません。

Answer 1

問題は、現在のparentが親によって上書きされますここに

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

です。

さらに、関数の最後にreturn node_listを追加するか、結果として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: 
      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}]]