使用python中的递归在泛型树中查找节点。

Question

我想使用递归在泛型树中查找节点，但似乎无法使其工作。我将其作为类中的方法，并且仅发布该方法。我正在使用python 3。任何帮助都将不胜感激

def search_tree2(self, node):
    if self.name == node.name:
        return self
    elif self.child_nodes:
        result = None
        for child in self.child_nodes:
            if child.name == node.name:
                result = child
            elif child.child_nodes:
                result = child.search_tree2(child)
                if result.child_nodes:
                    for kid in result.child_nodes:
                        if kid.name == node.name:
                            result = kid
        return result
    else:
        return None

编辑:添加了剩余的代码，使用Neel Mehta.For clarity的更新方法我想做的是在树中的任何节点上添加一个节点，方法是搜索节点，然后添加我在移动设备上的新node.Also，所以粘贴代码有点困难；这就是为什么我最初只发布了代码片段。

class Tree:
    def __init__(self, value=None, name=None, parent=None):
        self.value = value
        self.name = name
        self.parent = parent
        self.child_nodes = []

    def add_node(self, value=None, name=None, parent=None):
        node = Tree(value, name, parent)
        if node.parent.name == 'root':
            self.child_nodes.append(node)
        else:
            parent_node = self.search_tree2(node.parent)
            if parent_node:
                parent_node.child_nodes.append(node)
                print(node.name, 'added..')
            else:
                print('Parent Node not found.')
        return node

    def print_tree(self, node):
        if node.name:
            if node.name == 'root':
                pass
            else:
                print(node.name.title() + ', ', 'age ', str(node.value) + ', ' if node.value else 'unknown' + ', ',
                      'with parent ', node.parent.name, ' and ',
                      *[node.child_nodes[i].name + ' ' for i in range(len(node.child_nodes))] if len(
                          node.child_nodes) > 0 else 'no one ', 'as children.', sep='')
            if node.child_nodes:
                for member in node.child_nodes:
                    member.print_tree(member)

    def search_tree2(self, node):
        if self.name == node.name:
            return self
        elif self.child_nodes:
            for child in self.child_nodes:
                result = child.search_tree2(node)
                if result:
                    return result
        return None

    def delete_node(self, node):
        parent = self.search_tree2(node.parent)
        for child in parent.child_nodes:
            if child.name == node.name:
                parent.child_nodes.remove(child)


family = Tree(name='root', parent=None)
rebecca = family.add_node(value=64, name='Rebecca', parent=family)
jack = family.add_node(value=64, name='Jack', parent=family)
kate = family.add_node(value=36, name='Kate', parent=jack)
randall = family.add_node(value=36, name='Randall', parent=jack)
kevin = family.add_node(value=36, name='Kevin', parent=rebecca)
becky = family.add_node(value=11, name='Becky', parent=kevin)
daisy = family.add_node(value=8, name='Daisy', parent=randall)
jen = family.add_node(value=22, name='Jen', parent=kate)
william = family.add_node(value=8, name='William', parent=daisy)
kyle = family.add_node(value=20, name='Kyle', parent=kate)

Answer 1

正如您在问题中提到的，您希望使用递归。这意味着您应该从函数中调用要定义的函数。

当您迭代节点的子节点时，可以对子节点调用search_tree2。这将确保它递归整个树的深度。它还将在所有节点上执行您定义的逻辑，因此您不需要在子节点的循环中添加if条件。

然后，您的代码将如下所示：

def search_tree2(self, node):
    if self.name == node.name:
        return self
    elif self.child_nodes:
        for child in self.child_nodes:
            result = child.seach_tree2(node)
            if result:
                return result

    # Could not find the result in any of the children
    return None