Python之以深度优先顺序使用生成器迭代树

我正在尝试对二叉树进行 DFS。树是有效的。当 yield 被 print 替换时(当它不是生成器时)，该函数本身起作用。

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 

很明显，由于“保持”调试线，节点就在那里。不过，它似乎直接跳过了递归步骤。否则它会再次打印 Start。我试过将 yield 添加到 self.depth(Node.right) 语句中，但这似乎没有任何帮助。 Return 语句在生成器内部也不好，这对我来说很有意义。谢谢!

请您参考如下方法:

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

例如:

self.depth(Node.left) 

应该是这样的

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

在 Python 3.3+ 中，它可以像这样简单

yield from self.depth(Node.left) 

“主”中的 for 循环应该如下所示:

for node in depthFirstSearch: 
    print node 

我还注意到您的深度优先搜索算法有正确的想法，但您实际上还没有搜索任何东西。不过，我猜您已经知道这一点。