Python中树的递归函数 [英] Recursive function for trees in Python

问题描述

我正在尝试在 Python 中创建一个函数，该函数采用树的任意节点，并根据节点给出的列表填充列表.

I'm trying to make a function in Python, that takes an arbitrary node of a tree, and populates a list of lists based on the node give.

给定以下错误绘制的树:

Given the following badly drawn tree:

例如，如果我们从节点 5 开始，我们应该得到:

If we start at, for example, node 5, we should get:

• 包含具有相同父节点的所有节点的列表，包括我们从 (4 和 5) 开始的节点
• 任何子节点，但不是它们的子节点 (6).
• 父节点和任何具有相同父节点的父节点，以及它们的父节点等，直到我们到达根节点，但不包括根节点(在这种情况下只有 2 和 3，但如果树更深我们从低处开始，这里会有更多.

节点应该以一个列表列表结束，每个深度一个列表.

And the nodes should end up in a list of lists, one list for each depth.

python中的节点:

The nodes in 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}
]

我们只能看到父母，不能看到孩子，但遗憾的是，这是我必须使用的数据格式.

We can only see parents, not children, but this is the data format I have to work with, sadly.

因此，如果我们采用节点 5，我们希望最终得到一个看起来像这样的节点列表:

So from this, if we take node 5, we want to end up with a node list looking something like this:

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

这是我目前的代码.我认为递归函数可能是最简单的方法.不幸的是，它似乎没有像我认为的那样做，显然我做错了什么.并且这段代码甚至没有考虑获取我完全不知道如何处理的子节点，除了可能会更容易处理之后.

This is the code I have so far. I figure a recursive function is probably the simplest way. Unfortunately it seems to do nothing like what I think it should, and obviously I'm doing something very wrong. And this code doesn't even consider geting the child nodes which I'm not entirely sure how to deal with at all, apart from possibly handing the afterwards which would be much easier.

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

不确定我哪里出错了.

推荐答案

问题来了

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

当前的 parent 将被其父级覆盖.

The current parent will be overwritten by its parent.

此外，您应该在函数末尾添加return node_list，或者使用node_list作为结果.

Moreover, you should add return node_list at the end of the function, or use node_list as results.

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

这篇关于Python中树的递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！