在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中树的递归函数

回答

相关问题