Python用递归函数实现家族树血统判断及关系链保存功能

现有代码问题分析 #

• 全局变量line会导致多次调用结果污染，且未存储完整的中间代节点
• 裸try-except会吞掉非预期的运行错误，逻辑不严谨
• 缺少路径回溯拼接的逻辑，仅存储了最终匹配的祖先节点

实现思路 #

• 递归方向从待校验后代向上溯源父母，匹配到目标祖先时回溯拼接路径
• 递归返回结果同时携带匹配成功的路径，避免使用全局变量
• 明确终止条件：要么溯源到无父母记录的节点（匹配失败），要么匹配到目标祖先（匹配成功）

完整实现代码 #

def lineage(ancestor, descendant, family_tree):
    # 嵌套递归溯源函数，返回(是否匹配, 路径列表)
    def dfs(current_person):
        # 终止条件1：当前人物就是目标祖先，匹配成功
        if current_person == ancestor:
            return True, [ancestor]
        # 终止条件2：当前人物没有父母记录，匹配失败
        if current_person not in family_tree:
            return False, []
        # 分别查询父系、母系溯源结果
        dad, mom = family_tree[current_person]
        # 父系匹配成功则拼接当前节点到路径
        dad_match, dad_path = dfs(dad)
        if dad_match:
            return True, dad_path + [current_person]
        # 母系匹配成功则拼接当前节点到路径
        mom_match, mom_path = dfs(mom)
        if mom_match:
            return True, mom_path + [current_person]
        # 双系都未匹配
        return False, []
    
    has_lineage, path = dfs(descendant)
    if has_lineage:
        # 按要求逐行打印关系链
        for person in path:
            print(person)
    return has_lineage

测试验证 #

# 家族树示例数据
d = { 
'Kevin': ('Tom', 'Marge'), 
'Marge': ('John', 'Mary'), 
'Elle': ('Tom', 'Marge'), 
'Seth': ('Tom', 'Marge'), 
'Mary': ('Carl', 'Elena'), 
'Tom': ('Joseph', 'Alice'), 
'Alice': ('Rob', 'Amy'), 
'John': ('James', 'Elena'), 
'Joseph': ('Adam', 'Emma'), 
'James': ('Nick', 'Maria') }

# 测试用例1
print("Is there a lineage?", lineage('Amy', 'Kevin', d))
# 输出：
# Amy
# Alice
# Tom
# Kevin
# Is there a lineage? True

# 测试用例2
print("Is there a lineage?", lineage('Mary', 'Alice', d))
# 输出：
# Is there a lineage? False

内容的提问来源于stack exchange，提问作者t-y