1

任意の分岐係数を持つツリーでノードを見つけるのに苦労しています。各ノードはデータを運び、ゼロ以上の子を持ちます。search メソッドは Node クラス内にあり、その Node がデータを運ぶかどうかを確認してから、その Node のすべての子を確認します。再帰メソッドで無限ループになってしまいますが、何か助けはありますか?

def find(self, x):

    _level = [self]
    _nextlevel = []

    if _level == []: 
        return None
    else:
        for node in _level:
            if node.data is x:
                return node
            _nextlevel += node.children
        _level = _nextlevel
    return self.find(x) + _level

find メソッドは Node クラスにあり、メソッドが呼び出されたノードにデータ x があるかどうかをチェックし、そのノードのすべての子をチェックします。私は無限ループを取得し続けます。この時点で本当に立ち往生しています。洞察をいただければ幸いです。

4

2 に答える 2

1

このコードにはいくつかの問題があります。まず、2 行目にあることに注意してください_level = [self]。つまり、if _level == []5 行目は常に false になります。

2 番目の問題は、forループが 内のすべてを通過することです_levelが、上記のように、それは常に[self]2 行目によるものです。

3 番目の問題は return ステートメントです。あなたが持っていreturn self.find(x) + _levelます。それは2つの部分で評価されます。最初に を呼び出しself.find(x)、それが返すものを の内容と連結します_level。しかし、self.find(x)それを呼び出すと、同じ引数で同じメソッドが呼び出され、同じreturn self.find(x) + _level行にヒットし、同じメソッドが再び呼び出され、永遠に繰り返されます。

于 2013-08-04T20:19:59.183 に答える
1

再帰的検索の単純なパターンは、ジェネレーターを使用することです。これにより、再帰の状態を自分で管理することなく、呼び出し元のコードに簡単に答えを渡すことができます。

class Example(object):
     def __init__(self, datum,  *children):
         self.Children = list(children) # < assumed to be of the same or duck-similar class
         self.Datum = datum

     def GetChildren(self):
         for item in self.Children: 
             for subitem in item.GetChildren():
                 yield subitem
             yield item

     def FindInChildren(self, query):  # where query is an expression that is true for desired data
         for item in self.GetChildren():
             if query(item):
                yield item
于 2013-08-05T02:27:03.923 に答える