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)

を実行する代わりに、if len(node.children()==0すべての (おそらくゼロの) 子に降りた後に len(leafs) をチェックします。したがって、 node.children() を 1 回だけ呼び出します。

于 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; 再帰呼び出しでheadsパラメータがありません。とにかく機能している理由は、他の人が言ったことです。デフォルトのパラメーターはグローバルであり、呼び出し間で再利用されます。

再帰を完全に回避したい場合は、この場合、キューまたはスタックとループのいずれかを使用できます。

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 に答える