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

递归搜索的一个简单模式是使用生成器。这样可以很容易地将答案传递给调用代码，而无需自己管理递归的状态。

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 回答
1

这段代码有一些问题。首先，请注意在第 2 行您有_level = [self]. 这意味着第if _level == []5 行将永远是错误的。

第二个问题是您的for循环遍历了 中的所有内容_level，但是，如上所述，这始终是[self]由于第 2 行。

第三个问题是return语句。你有return self.find(x) + _level. 这将分两部分进行评估。首先，调用self.find(x)，然后将返回的内容与_level. 但是，当您调用它时self.find(x)，它将调用具有相同参数的相同方法，然后又会点击同一return self.find(x) + _level行，这将再次调用相同的方法，并且永远如此。

于 2013-08-04T20:19:59.183 回答