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

明らかに、'keep it up' デバッグ行があるため、ノードがそこにあります。ただし、再帰ステップをスキップしているようです。そうしないと、Start again が出力されます。私は利回りを self.depth(Node.right) ステートメントに追加して置き換えようとしましたが、それは何の役にも立たないようです。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)

「メイン」の for ループは、代わりに次のようになります。

for node in depthFirstSearch:
    print node

また、深さ優先検索アルゴリズムには正しい考えがありますが、実際にはまだ何も検索していないことにも気付きました。とはいえ、あなたはすでにこれを知っていると思います。

于 2012-12-26T16:39:37.857 に答える