0

可能为时已晚，但在解决之前我无法入睡：

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

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

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

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
4

2 回答 2

2

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

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

其次，如果你点击一个叶子节点，你根本不会返回一个列表，只是parent. 将此更改为return [parent].

第三，如果你点击一个中间节点，你不包括parent任何地方，所以你只会得到叶子。但是你想要所有的节点。所以更改r = []为r = [parent].

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

所以：

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

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

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

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

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

（值得注意的是，分支递归只能在下游累加器样式而不是上游收集样式中进行尾调用优化。但这在 Python 中并不重要，因为 Python 不进行尾调用优化。所以，写下对你更有意义的那个。）

于 2013-05-14T01:07:58.490 回答
2

如果我理解您的问题，您想制作一个包含树中所有值的平面列表，在这种情况下，由元组表示的树将起作用：

def nodes_from_tree(tree,nodes=list()):
    if isinstance(tree,tuple):
        for child in tree:
            nodes_from_tree(child,nodes=nodes)
    else:
        nodes.append(tree)

mynodes = []
tree = (('Root',
        ('Parent',(
            ('Child1',),
            ('Child2',)
            )
        ),
        ('Parent2',(
            ('child1',(
                ('childchild1','childchild2')
            )),
            ('child2',),
            ('child3',)
        )),
        ('Parent3',(
            ('child1',),
            ('child2',(
                ('childchild1',),
                ('childchild2',),
                ('childchild3',),
                ('childchild4',)
            ))
        ))
    ))
nodes_from_tree(tree,nodes=mynodes)
print(mynodes)

生产

['Root', 'Parent', 'Child1', 'Child2', 'Parent2', 'child1', 'childchild1', 'childchild2',
 'child2', 'child3', 'Parent3', 'child1', 'child2', 'childchild1', 'childchild2', 'childchild3', 'childchild4']
于 2013-05-14T01:02:01.900 回答