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在每个级别的子树中显式地设置每个节点。

第二种方法简洁且略显肮脏，但它符合我在 Haskell 中编写的内容：

traverse node = node : concatMap traverse (children node)

所以我的问题是：哪个更好？还是我错过了最佳的第三选择？

4

4 回答 4

5

[更新]见PEP-380，这产生所有语法从Python 3.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

这是一个意见问题，所以所有答案都只是价值判断。不过，据我所知，没有优雅的第三种方式。

我的观点是，第一种方式胜出。它更清晰、更易于阅读——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 回答