Python非二叉树元素查找与祖先路径追踪函数实现求助

问题描述 #

我是编程新手，想要定义一个函数，在非二叉树中查找指定元素，并将该元素的所有祖先（包含自身）存入列表。
该树以元组形式编码：索引0为节点值，索引1为子节点列表，每个子节点为同结构的元组。

示例 #

树结构数据 #

tree_data = (
    'Alan', [
        (
            'Bob', [
                ('Chris', []),
                (
                    'Debbie', [
                        ('Cindy', [])
                    ]
                )
            ]
        ),
        (
            'Eric', [
                ('Dan', []),
                (
                    'Fanny', [
                        ('George', [])
                    ]
                )
            ]
        ),
        ('Hannah', [])
    ]
)

预期结果 #

查找'George'应返回：['George', 'Eric', 'Alan']

现有问题 #

我编写的代码仅能添加元素和直接父节点，无法获取更上层祖先；且添加return语句后返回None，请求帮助。

现有代码 #

lst = [] 
def list_parentals(tree, element):   
    if tree[0] == element: 
        lst.append(element)            
    else:
        for child in tree[1]:
            list_parentals(child, element)
            if child[0] == element:
                lst.append(tree[0])

问题分析 #

1. 全局变量依赖：使用全局列表lst会导致多次调用时残留旧数据，且函数结果依赖外部状态，不符合封装性要求。
2. 逻辑缺陷：仅判断直接子节点是否为目标，当目标在更深层子树时，上层父节点无法感知下层已找到目标，因此不会将自身加入列表。
3. 无有效返回值：函数未返回找到目标的状态，上层调用无法得知子树是否命中目标，无法向上传递路径信息。

解决方案 #

方案1：递归返回路径列表（推荐） #

通过递归返回路径列表，找到目标时逐步向上拼接父节点，无需全局变量：

def list_parentals(tree, element):
    # 当前节点是目标，返回包含自身的列表
    if tree[0] == element:
        return [element]
    # 遍历所有子节点
    for child in tree[1]:
        path = list_parentals(child, element)
        # 子树中找到目标，将当前节点加入路径末尾
        if path:
            path.append(tree[0])
            return path
    # 所有子树未找到目标，返回空列表
    return []

测试验证

print(list_parentals(tree_data, 'George'))  # 输出: ['George', 'Eric', 'Alan']
print(list_parentals(tree_data, 'Cindy'))   # 输出: ['Cindy', 'Debbie', 'Bob', 'Alan']
print(list_parentals(tree_data, 'Hannah'))  # 输出: ['Hannah', 'Alan']

方案2：内部辅助函数收集路径 #

使用嵌套的辅助函数，通过列表传递收集路径：

def list_parentals(tree, element):
    def helper(node, path):
        if node[0] == element:
            path.append(node[0])
            return True
        for child in node[1]:
            if helper(child, path):
                path.append(node[0])
                return True
        return False
    
    path = []
    helper(tree, path)
    return path

内容的提问来源于stack exchange，提问作者VV18