用父/子压平树并返回所有节点

Question

可能已经太晚了，但在解决之前我无法入睡：

我有一棵树，有一些父母，他们有孩子，他们也有孩子等等。

现在我需要一个函数来获取树中的所有节点。

这是目前有效的方法，但只有一层深度：

def nodes_from_tree(tree, parent):
    r = []
    if len(tree.get_children(parent)) == 0:
        return parent
    for child in tree.get_children(parent):
        r.append(nodes_from_tree(tree, child))
    return r

然后我尝试通过r，所以它记住了孩子们，但我多次使用该函数并r累积存储所有节点，尽管我将其设置为r=[]：

def nodes_from_tree(tree, parent, r=[]):
    r = []
    if len(tree.get_children(parent)) == 0:
        return parent
    for child in tree.get_children(parent):
        r.append(nodes_from_tree(tree, child, r))
    return r

编辑：这是树结构：

parent1    parent2    parent3
   |          |          |
   |          |          |
 child        |          |
              |          |
      +--------------+   |
      |       |      |   |
    child   child  child |
      |                  |
  +---+---+              |
child   child        +---+---+
                     |       |
                   child     |
                             |
                       +-----+-----+-----+
                       |     |     |     |
                     child child child child

可用方法：

tree.get_parents()       # returns the nodes of the very top level
tree.get_children(node)  # returns the children of parent or child

Answer 1

我认为你的问题只是你错误地积累了东西。

\n\n

首先，如果您点击中间节点，每个子节点都应该返回一个列表，但您正在appending 该列表而不是extending 它。因此，[1, 2, 3, 4]您不会得到类似[[1, 2], [3, 4]]\xe2\x80\x94 的东西，换句话说，您只是将其转换为列表列表树，而不是平面列表。将其更改为extend.

\n\n

其次，如果您点击叶节点，则根本不会返回列表，而只是返回parent。将其更改为return [parent].

\n\n

第三，如果你到达中间节点，你不会包含parent任何地方，所以你最终只会得到叶子。但您想要所有节点。因此将 更改r = []为r = [parent].

\n\n

if通过最后的更改，您根本不需要该块。如果没有孩子，循环将发生 0 次，并且最终将按[parent]原样返回，完全按照您的意愿返回。

\n\n

所以：

\n\n

def nodes_from_tree(tree, parent, r=[]):\n    r = [parent]\n    for child in tree.get_children(parent):\n        r.extend(nodes_from_tree(tree, child, r))\n    return r\n

\n\n\n\n

同时，虽然这个版本可以工作，但它仍然很混乱。您混合了两种不同风格的递归。一种方法是沿链向下传递一个累加器并在向下的过程中添加累加器；另一个是在链上返回值并在向上的过程中累积结果。你各做一半。

\n\n

事实证明，您执行上游递归的方式使下游递归根本没有效果。虽然你确实将其传递r给每个孩子，但你永远不会修改它，甚至不会使用它；您只需创建一个新r列表并将其返回。

\n\n

解决这个问题的最简单方法是删除累加器参数：

\n\n

def nodes_from_tree(tree, parent):\n    r = [parent]\n    for child in tree.get_children(parent):\n        r.extend(nodes_from_tree(tree, child))\n    return r\n

\n\n

（值得注意的是，如果您以下游累加器风格而不是上游收集风格进行分支递归，则只能进行尾部调用优化。但这在Python中并不重要，因为Python不进行尾部调用优化。所以，写下对您来说更有意义的一项。）

\n