python - 查找树中的节点

Question

我无法在树中找到具有任意分支因子的节点。每个节点都承载数据并具有零个或更多子节点。搜索方法位于 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 是否位于调用该方法的节点中，然后检查所有该节点的子节点。我不断陷入无限循环，真的陷入了这一点，任何见解将不胜感激。

Answer 1

此代码存在一些问题。首先，请注意第 2 行有 _level = [self] 。这意味着 if _level == []第 5 行始终为 false。

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

第三个问题是return语句。您有return self.find(x) + _level 。分两部分进行评估。一、调用self.find(x) ，然后将返回的内容与 _level 的内容连接起来。但是，当你调用self.find(x)时它将使用相同的参数调用相同的方法，然后依次命中相同的 return self.find(x) + _level行，它将再次调用相同的方法，并且永远如此。