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

问题出在这里

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