在Python中樹的遞歸函數

我想在Python中創建一個函數，它需要一棵樹的任意節點，並根據節點給出的填充列表列表。在Python中樹的遞歸函數

考慮下面的Badly Drawn樹：

Tree

如果我們開始在，例如，節點5，我們應該得到：

包含與同父的所有節點列表節點，包括我們在（4和5）開始的節點
任何子節點，但不是他們的子節點（6）。
父節點和任何具有相同父節點的父節點及其父節點等，直到我們到達根節點，但不包括根節點（在這種情況下只有2和3，但如果樹更深我們開始走低，有會更這裏

和節點應該在列表的列表結束了，一個列表每個深度

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

我們只能看到父母，而不是孩子，但這是數據fo我不得不與悲傷地合作。

所以從這個，如果我們採取節點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}], []]

不完全知道我要去哪裏錯在這裏。

來源

2013-03-20 Tom Carrick

具有這樣的裂縫，但要確保我明白了...你想三個不同的列表，嵌套在主力名單中，每一個居住在你的子彈列表描述？ – DeaconDesperado 2013-03-20 13:46:24

不完全。對於這個例子有。但如果樹更深，會有更多的列表。如果我們開始變得越來越淺，就越少基本上是每個深度的列表。 – 2013-03-20 13:58:49

爲了澄清，如果我們開始在節點7，會有一個列表7，列表6，列表4,5和列表2,3 – 2013-03-20 14:01:32

的問題是在這裏

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

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

來源

2013-03-20 14:16:30 nymk

啊，一個新手的錯誤。謝謝！ – 2013-03-20 14:26:50

在Python中樹的遞歸函數

回答

相關問題