Python实现：为家谱表中每条父子路径生成唯一ID

核心逻辑 #

遍历家谱树，追踪从根节点到叶子节点的完整路径，给每个最终子节点（叶子）分配唯一ID，所有指向同一叶子的路径共享该ID。

具体步骤 #

• 构建树形映射：把parent_id和child_id的关系转换成父节点到子节点列表的字典，同时找出所有根节点（没有父节点的节点）。
• 遍历所有路径：用递归或迭代方式，从每个根节点出发，遍历到所有叶子节点，记录每一条完整路径。
• 分配唯一ID：用字典维护叶子节点与ID的映射，遇到新叶子就生成新ID，已存在的叶子直接复用已有ID。
• 生成结果记录：把每条路径、对应的唯一ID、最终子节点整理成结构化记录。

Python代码示例 #

假设你的家谱数据是如下格式的列表：

family_data = [
    (1, 2),
    (1, 3),
    (2, 4),
    (3, 4),
    (3, 5)
]

实现代码：

# 1. 构建父到子的映射，找出所有根节点
parent_to_children = {}
all_nodes = set()

for parent, child in family_data:
    parent_to_children.setdefault(parent, []).append(child)
    all_nodes.update({parent, child})

# 根节点：没有出现在child_id中的节点
root_nodes = [node for node in all_nodes if node not in {child for _, child in family_data}]

# 2. 遍历路径并分配唯一ID
leaf_id_map = {}
current_id = 1
result_records = []

def traverse(current_node, path):
    global current_id
    # 当前节点是叶子（无后续子节点）
    if current_node not in parent_to_children:
        if current_node not in leaf_id_map:
            leaf_id_map[current_node] = current_id
            current_id += 1
        # 添加路径记录
        result_records.append({
            "完整路径": "->".join(map(str, path + [current_node])),
            "唯一ID": leaf_id_map[current_node],
            "最终子节点": current_node
        })
        return
    # 递归遍历子节点
    for child in parent_to_children[current_node]:
        traverse(child, path + [current_node])

# 遍历所有根节点
for root in root_nodes:
    traverse(root, [])

# 打印结果
for record in result_records:
    print(record)

注意事项 #

• 如果家谱存在循环（比如子节点指向父节点），需要在遍历中加入循环检测，避免无限递归。
• 若数据量极大，递归可能触发栈溢出，建议改用迭代方式（用栈模拟递归过程）：

# 迭代版遍历
for root in root_nodes:
    stack = [(root, [])]
    while stack:
        current_node, path = stack.pop()
        if current_node not in parent_to_children:
            if current_node not in leaf_id_map:
                leaf_id_map[current_node] = current_id
                current_id += 1
            result_records.append({
                "完整路径": "->".join(map(str, path + [current_node])),
                "唯一ID": leaf_id_map[current_node],
                "最终子节点": current_node
            })
        else:
            # 反转子节点顺序，保证遍历顺序和递归一致（可选）
            for child in reversed(parent_to_children[current_node]):
                stack.append((child, path + [current_node]))

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