I'm writing a breadth depth-first tree traversal function, and what I want to do is this:
def traverse(node):
yield node
for n in node.children:
yield_all traverse(n) # << if Python had a yield_all statement
The idea is to end up with a (flat) sequence of nodes in the tree.
Approach #1: (propagating yields)
def traverse(node):
yield node
for n in node.children:
for m in traverse(n):
yield m
Approach #2: (flattening seque开发者_Python百科nces)
def traverse(node):
return itertools.chain([node],*(traverse(n) for n in node.children))
The first approach seems more clean, but I feel weird explicitly yield
ing each node in the subtree at each level.
The second approach is terse and slightly dirty, but it matches what I would write in Haskell:
traverse node = node : concatMap traverse (children node)
So my question is: Which is better? Or am I missing a best 3rd option?
[UPDATE] See PEP-380, this yield all syntax is available starting from Python 3.3 as yield from
:
def traverse(node):
yield node
for n in node.children:
yield from traverse(n)
I'd go with first. You'll get over propagating yields after a couple of times. :-)
This is an opinions question, so all the answers will just be value judgments. As far as I can think there's no elegant third way, though.
My opinion is that the first way wins hands down. It's clearer and easier to read -- Python isn't Haskell, even though it can do some functional stuff, and often the functional approach just doesn't look as neat.
Traversing with node position:
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)
精彩评论