在Python中从树中查找并返回节点

Question

class WNode(object):
    def __init__(self,w):
        self._w=w
        self._content=[]
    def find(self, x):
        if self._w is x:
            return self
        else:
            for i in self._content:
                return i.find(x)
        return None

嗨。我很难找到一个方法树。查找（self，x）如果存在x，则返回树中名为x的节点（使用递归）。我写的那个似乎只在某些情况下有效（在一些级别的简单树中），但在其他情况下（尤其是在较大的树中），即使存在节点，它也不会返回任何结果。有人知道如何创建一个工作的find（self，x）方法来返回x节点吗？在

Answer 1

另一个答案。与您和Todd Tao的解决方案类似，它实现了DFS。但是，一旦它完成对分支的探索失败，它将继续下一个分支。你的代码正在搜索最左边的分支。在

class WNode(object):

    def __init__(self,w):
        self._w=w
        self._content=[]

    def find(self, x):
        if self._w == x:
            return self
        else:
            y = None
            for i in self._content:
                y = i.find(x)
                if y:
                    break
            return y
        return None

if __name__ == '__main__':
    r = WNode(1)
    r._content = [WNode(2), WNode(3), WNode(4)]
    for i in xrange(1, 6):
        print('find({}) = {}'.format(i, r.find(i)))

Answer 2

这是因为您的find函数只查找最左边分支中的节点。想一个树的例子如下：

      A
    /   \
   B     C
  / \
 D   E

假设您正在寻找节点C，find函数首先查找分支B，然后检查D.D没有子节点，因此它结束for循环并返回None。它不会搜索其他分支，因为有返回的内容。在

实际上，如果你想在树中找到一个节点，你应该实现BFS或DFS算法来遍历你的树。由于您的find函数是DFS，我将为您编写DFS代码：

^{pr2}$

s_list作为一个搜索路径，它记录了find应该检查的每个节点。如果检查了所有节点，则返回None。在