在 n 叉树的子节点数组中搜索一个节点

Question

我已经解决了这个问题 2 周了。

我在 Python 中有一个基本的树节点 class:

class Node:
    def __init__(self, data):
        self.data= data
        self.children = []
        self.parent = None

然后我有一个通用的递归搜索函数：

def find_node(node, data):
    if node.data == data:
        return node

    if len(node.children)>0:
        for child in node.children:
            find_node(child, data)

我不明白为什么 Python 只在我传递给 find_node 函数的每个“数据”的第一次出现时搜索。

我总是传递根节点，然后传递标识我要查找的节点的字符串。

真是用头撞墙

Answer 1

您的代码中有两个问题，第一个是如果函数被递归调用，您没有 returning 节点。第二个是如果你只使用 return find_node(child, data) 函数将在第一次传递时 return 但你只想 return 如果在递归函数中找到节点。因此你必须改变

find_node(child, data)

类似

potNode = find_node(child, data)
if not potNode is None:
    return potNode

在 n 叉树的子节点数组中搜索一个节点

Search a node in array of children nodes in n-ary tree

python

tree

recursive-datastructures