5

私は幅の深さ優先のツリートラバーサル関数を書いています。私がやりたいことはこれです:

def traverse(node):
    yield node
    for n in node.children:
        yield_all traverse(n) # << if Python had a yield_all statement

アイデアは、ツリー内のノードの (フラットな) シーケンスで終わることです。

アプローチ #1: (利回りの伝播)

def traverse(node):
    yield node
    for n in node.children:
        for m in traverse(n):
            yield m

アプローチ #2: (フラット化シーケンス)

def traverse(node):
    return itertools.chain([node],*(traverse(n) for n in node.children))

yield最初のアプローチはよりクリーンに見えますが、各レベルでサブツリーの各ノードを明示的に指定するのは奇妙に感じます。

2 番目のアプローチは簡潔で少し汚れていますが、Haskell で記述したものと一致します。

traverse node = node : concatMap traverse (children node)

だから私の質問は：どちらが良いですか？または、最適な 3 番目のオプションがありませんか?

4

4 に答える 4

5

[更新] PEP-380を参照してください。このyieldall構文は、 Python3.3以降で次のように使用できますyield from。

def traverse(node):
    yield node
    for n in node.children:
        yield from traverse(n)
于 2010-12-14T22:20:44.570 に答える
3

私は最初に行きます。数回後には、収量の伝播を乗り越えることができます。:-)

于 2010-12-14T22:23:36.337 に答える
1

これは意見の質問なので、すべての回答は単なる価値判断になります。ただし、私が考える限り、エレガントな第 3 の方法はありません。

私の意見では、最初の方法が勝つということです。より明確で読みやすくなっています。Python は Haskell ではありません。関数型の処理を行うことはできますが、多くの場合、関数型のアプローチは見栄えがよくありません。

于 2010-12-14T22:35:37.780 に答える
0

ノード位置でのトラバース:

def iter_tree(t, i=0, j=0):
    yield (i, j), t
    for j, n in enumerate(t.children):
        yield from iter_tree(n, i + 1, j)

for (i, j), n in iter_tree(t):
    print(i*'    ', (i, j), n)
于 2016-07-25T14:41:34.077 に答える