Python中树的递归函数

Question

我正在尝试在Python中创建一个函数，这个函数可以接收树中的任意一个节点，然后根据这个节点生成一个列表的列表。

下面是一个画得不太好的树：

比如说，如果我们从节点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}
]

我们只能看到父节点，而看不到子节点，但这就是我必须处理的数据格式，真让人遗憾。

所以从这里出发，如果我们选择节点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

def processNode(bp, space=''):
    if ('name' in bp[0].keys() ):
        print( space + bp[0]['name'])
    if ('subNodesTitle' in bp[0].keys()):
        print( bp[0]['subNodesTitle'])
        processNode( bp[0]['subNodes'],space=space+' ')
    if (len(bp) > 1):
        processNode( bp[1:],space=space )
processNode(root)

这个函数可以在一个不平衡的树结构中进行递归操作，

Answer 2

问题出在这里

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