3

我正在尝试在二叉树上进行 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

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

4

1 回答 1

0

在里面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

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

于 2012-12-26T16:39:37.857 回答