0

在树形结构中，我试图找到一个分支的所有叶子。这是我写的：

def leafs_of_branch(node,heads=[]):
    if len(node.children()) == 0:
        heads.append(str(node))
    else:    
        for des in node.children():
           leafs_of_branch(des)
    return heads


leafs_of_branch(node)

我不知道为什么，但对我来说感觉不对。它有效，但我想知道是否有更好的方法来使用递归而不创建heads参数。

4

5 回答 5

2

这

def leafs_of_branch(node,heads=[]):

总是一个坏主意。会更好

def leafs_of_branch(node,heads=None):
    heads = heads or []

否则，您总是对 leafs_of_branch 使用相同的列表。在您的特定情况下，它可能没问题，但迟早您会遇到问题。

我建议：

def leafs_of_branch(node):
    leafs = []
    for des in node.children():
        leafs.extend(leafs_of_branch(des))
    if len(leafs)==0:
        leafs.append(str(node))
    return leafs

leafs_of_branch(node)

我没有做 a if len(node.children()==0，而是在下降到所有（可能为零）孩子之后检查 len(leafs) 。因此我只调用一次 node.children() 。

于 2013-01-07T16:00:57.150 回答
1

我相信这应该有效：

def leafs_of_branch(node):
    if len(node.children()) == 0:
       return [str(node)]
    else:
       x = []
       for des in node.children():
           x += leafs_of_branch(des)  #x.extend(leafs_of_branch(des)) would work too :-)
       return x

它不是很漂亮，可能会更简洁一些，但我试图尽可能地保持原始代码的形式，以使发生的事情一目了然。

如果您多次调用它，您的原始版本实际上将不起作用，因为当您附加到heads列表时，该列表实际上会在两次调用之间保存。

于 2013-01-07T16:00:19.107 回答
1

只要递归进行，您就做对了IMO；您在递归调用中缺少 head 参数。无论如何它工作的原因是其他人所说的，默认参数是全局的并且在调用之间重用。

如果你想避免递归 altogheter，在这种情况下你可以使用 Queue 或 Stack 和循环：

def leafs_of_branch(node):
    traverse = [node]
    leafs = []

    while traverse:
        node = traverse.pop()
        children = node.children()

        if children:
            traverse.extend(children)
        else:
            leafs.append(str(node))

    return leafs
于 2013-01-07T16:05:11.710 回答
0

首先，避免使用可变对象（列表、字典等）作为默认值，因为默认值是全局的并且在函数调用之间重用：

def bad_func(val, dest=[]):
    dest.append(val)
    print dest

>>> bad_func(1)
[1]
>>> bad_func(2)
[1, 2]  # surprise!

因此，随后的调用将使某些事情完全出乎意料。

至于递归问题，我会这样重写：

from itertools import chain

def leafs_of_branch(node):
    children = node.children()
    if not children:  # better than len(children) == 0
        return (node, )

    all_leafs = (leafs_of_branch(child) for child in children)
    return chain(*all_leafs)
于 2013-01-07T16:01:15.140 回答
0

您也可以通过这种方式递归地定义一个迭代器。

def leafs_of_branch(node):
    if len(node.children()) == 0:
        yield str(node)
    else:    
        for des in node.children():
            for leaf in leafs_of_branch(des):
                yield leaf

leafs = list(leafs_of_branch(node))
于 2013-01-07T16:14:24.707 回答