Python - 使用生成器按深度优先顺序迭代树

Question

我正在尝试对一棵二叉树进行深度优先搜索。该树是有效的。当yield不是一个生成器时，函数本身可以正常工作。

class BinaryTree(object):
 def __init__(self, root):
    self.root = root

 def dfs(self):
    print "Depth First"
    return self.depth(self.root)

 def depth(self, Node):
    print "Starts"
    yield Node
    if Node.left != None:
        print "keep it up left" 
        self.depth(Node.left)
    if Node.right != None:
        print "keep it up right"    
        self.depth(Node.right)
    print "oh no"

编辑：以下是主要内容的摘录：

tree = BinaryTree(15) #adds the key 15 as the root
tree.addKey(10)       #adds additional entries
...
tree.addKey(5)
depthFirstSearch = tree.dfs()
for i in range(8): 
    print depthFirstSearch.next()
    print "outside of fnc"

为了完整性，树的形状如下：

{15: {10: {3: {2: , }, {5: , }}, }, {17: , {60: {23: , }, }}}

输出结果如下：

Depth First
Starts 
15
outside of fnc
keep it up left
keep it up right
oh no

很明显由于"keep it up"的调试行，结点是存在的。但似乎跳过了递归步骤，否则将会打印"Start again"。我尝试替换为在self.depth(Node.right)语句中添加一个yield，但这似乎没有帮助。在生成器内部不好使用return语句，这对我来说很合理。谢谢！

- Chet

---

你介意展示一下你如何定义 depthFirstSearch 吗？ - Tyler Crompton

抱歉，看到编辑了。 - Chet

Answer 1

在 BinaryTree.depth 中，您正在进行递归，但没有对递归调用执行任何操作。

例如：

self.depth(Node.left)

应该是类似这样的

for node in self.depth(Node.left):
    yield node

在Python 3.3以上的版本中，它可以非常简单：

yield from self.depth(Node.left)

你的 "main" 函数中的 for 循环应该像这样：

for node in depthFirstSearch:
    print node

我还注意到你的深度优先搜索算法有正确的思路，但实际上你还没有开始搜索任何东西。虽然我猜你已经知道这一点了。

- Tyler Crompton

---

我知道主函数中的for循环。我一直在尝试学习生成器，并想要更改迭代次数，以便可以玩弄StopIteration异常。如果我正在递归，为什么“Start”只打印一次？你的答案完美解决了我的问题。 - Chet

这是生成器的本质，我猜测。惰性求值？ - Chet

@Chet，你说得对。从你的代码中可以看出，你已经知道了这一点。Python 识别使用 yield 的任何函数都是生成器。因此，当调用生成器时，它会生成一个新的迭代器实例。在你的 BinaryTree.dfs 方法中，你返回了生成的迭代器。然而，在你的 BinaryTree.depth 方法中，你生成了新的迭代器，但却没有对它们进行任何操作。它们被创建了，但从未被使用过。这就是为什么你必须在循环中 yield 每个节点的原因。另外，根据我的经验，你很少需要显式地使用 StopIteration。 - Tyler Crompton