结合递归和产量进行树遍历

Question

我正在尝试结合递归和 yield 以按顺序遍历树

这就是我目前拥有的。但是，当我尝试遍历树时，它似乎只遍历了根节点

class Tree:
    ...
    def post_order(self, node: TreeNode):
        """Yield next node in post order from node"""
        for child in node.get_children():
            self.post_order(child)
        yield node


if __name__ == '__main__':
    root = TreeNode('root')
    depth1a = TreeNode('1a')
    depth1b = TreeNode('1b')
    root.add_children(depth1a, depth1b)
    tree = Tree(root)
    for node in tree.post_order(root):
        print(node.get_element())

当我运行代码时，它只打印出

root

这是第一个节点的元素，不是我想要的

1a
1b
root

有人知道我做错了什么吗？

谢谢大家

Answer 1

感谢张实唯，结果我不得不使用yield from。调用生成器函数不会从中产生：

class Tree:
    ...
    def post_order(self, node: TreeNode):
        """Yield next node in post order from node"""
        for child in node.get_children():
            yield from self.post_order(child)
        yield node

Answer 2

Mike Pham 的回答很好，但我想分享一种回溯方法，帮助我们理解如何使用直接递归而不是 for 循环手动构建所需的序列。这不是一个更好的程序；这是一个检查你对发电机掌握程度的练习 -

from functools import reduce

def empty ():
  yield from ()

def postorder (node, backtrack = empty(), visit = False):
  if visit:
    yield node.data
    yield from backtrack
  elif node.children:
    yield from reduce \
      ( lambda it, child: postorder (child, it)
      , node.children[::-1]
      , postorder (node, backtrack, True)
      )
  else:
    yield from postorder (node, backtrack, True)

测试一下 -

class node:
  def __init__ (self, data, *children):
    self.data = data
    self.children = children

tree = \
  node("a",
    node("b",
      node("e"),
      node("f",
        node("k"))),
    node("c"),
    node("d",
      node("g"),
      node("h"),
      node("i"),
      node("j")))

print(list(postorder(tree)))
# [ 'e', 'k', 'f', 'b', 'c', 'g', 'h', 'i', 'j', 'd', 'a' ]

这可能有助于您了解 yield 实际为您所做的事情。这是没有它的同一个程序。粗体 -

的细微差别

def empty ():
  return []

def postorder (node, backtrack = empty, visit = False):
  <b>def gen ():</b>
    if visit:
      return <b>[</b> node.data <b>] + backtrack()</b>
    elif node.children:
      return reduce \
        ( lambda it, child: postorder (child, it)
        , node.children[::-1]
        , postorder (node, backtrack, True)
        ) <b>()</b>
    else:
      return postorder (node, backtrack, True) <b>()</b>
  <b>return gen</b>

<b>def run (gen):
  return gen ()</b>

print(<b>run</b>(postorder(tree)))
# [ 'e', 'k', 'f', 'b', 'c', 'g', 'h', 'i', 'j', 'd', 'a' ]

结合递归和产量进行树遍历

Combining recursion and yield for tree traversal

python

recursion

yield

generator