如何从多组元组中提取树形结构的各分支节点列表

给定数据 #

边集合如下：

edge = [('CDDC', '4C35'), ('4C35', 'BE83'), ('13E8', '7A21'), ('7A21', '7D43'), ('7D43', 'A7F6'), ('A7F6', '9526'), ('A7F6', '09D2'), ('09D2', '6DEA'), ('6DEA', '9290'), ('6245', '795A'), ('9290', 'F7BB'), ('F7BB', '2ABD'), ('2ABD', 'FE11'), ('FE11', 'F64C'), ('795A', 'EAD0'), ('EAD0', '86E4'), ('13E8', '01D7'), ('86E4', '88F6'), ('88F6', '2E95'), ('EDC6', '26C7')]

需求示例（以13E8为根的树为例） #

期望提取出各分支/叶子的节点列表：

[13E8, 7A21, 7D43, A7F6],
[A7F6, 9526],
[A7F6, 09D2, 6DEA, 9290],
[13E8, 01D7]

注：示例中9525应为笔误，实际对应边中的9526

具体实现思路 #

1. 构建树的结构映射

先把边集合转换成便于遍历的树形结构：

• 用父节点到子节点的映射字典：键是父节点，值是该节点的所有子节点列表
• 找出所有根节点：即从未出现在边的子节点位置的节点（根节点没有父节点）

代码实现：

# 构建父节点到子节点的映射
parent_to_children = {}
all_nodes = set()
for parent, child in edge:
    all_nodes.add(parent)
    all_nodes.add(child)
    if parent not in parent_to_children:
        parent_to_children[parent] = []
    parent_to_children[parent].append(child)

# 找出所有根节点（没有父节点的节点）
child_nodes = set(child for _, child in edge)
root_nodes = [node for node in all_nodes if node not in child_nodes]

2. 遍历树提取分支路径

对每个根节点，用深度优先遍历（DFS） 遍历整个树，过程中记录当前路径：

• 若当前节点是叶子节点（没有子节点）：把完整路径作为分支段保存
• 若当前节点是分支点（子节点数量≥2）：先保存到该节点的路径，再分别对每个子节点，从该分支点开始新路径遍历
• 若当前节点是普通节点（只有1个子节点）：继续延伸当前路径，直到遇到分支点或叶子节点

代码实现（以DFS为例）：

def extract_branches(root, parent_map):
    branches = []
    
    def dfs(current_node, current_path):
        current_path.append(current_node)
        # 获取当前节点的子节点，没有则为空列表
        children = parent_map.get(current_node, [])
        
        if len(children) == 0:
            # 叶子节点，保存当前路径
            branches.append(current_path.copy())
        elif len(children) >= 2:
            # 分支点，先保存当前路径，再遍历每个子节点
            branches.append(current_path.copy())
            for child in children:
                dfs(child, [current_node])
        else:
            # 只有一个子节点，继续延伸路径
            dfs(children[0], current_path)
        
        current_path.pop()
    
    dfs(root, [])
    return branches

# 提取所有树的分支
all_branches = []
for root in root_nodes:
    all_branches.extend(extract_branches(root, parent_to_children))

# 打印结果
for branch in all_branches:
    print(branch)

3. 结果说明

运行上述代码后，会得到所有符合要求的分支列表：

• 单链结构（如CDDC→4C35→BE83）会输出完整的单链路径
• 分支节点（如A7F6）会先保存到该节点的路径，再输出每个子节点开始的分支路径

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