如何从Python字典生成所有可能的层级路径？

问题描述 #

需要从给定的层级关系字典中，输出所有可能的节点路径（包含所有中间层级路径），且方案需适配大规模数据场景。示例如下：

修正后的示例字典（原字典存在语法错误，已将=改为:，并补充parent的子节点child3、child4以匹配期望输出） #

dictionary = {
    'parent': ['child1', 'child2', 'child3', 'child4'],
    'child1': ['child1_1', 'child1_2'],
    'child2': ['child2_1', 'child2_2'],
    'child3': [],
    'child1_1': ['child1_1_1', 'child1_1_2'],
    'child1_1_1': [],
    'child1_1_2': [],
    'child1_2': [],
    'child2_1': [],
    'child2_2': [],
    'child4': []
}

期望输出 #

parent/child1
parent/child1/child1_1
parent/child1/child1_1/child1_1_1
parent/child1/child1_1/child1_1_2
parent/child1/child1_2
parent/child2/child2_1
parent/child2/child2_2
parent/child3
parent/child4

解决方案 #

采用迭代深度优先遍历实现，避免递归的栈溢出问题，更适合大规模数据场景：

完整代码 #

def find_root_nodes(node_dict):
    # 收集所有被作为子节点的元素
    all_children = set()
    for children in node_dict.values():
        all_children.update(children)
    # 根节点是未出现在子节点集合中的键
    return [node for node in node_dict if node not in all_children]

def generate_all_paths(node_dict):
    paths = []
    roots = find_root_nodes(node_dict)
    # 用栈存储当前节点和对应的路径，避免递归深度限制
    stack = [(root, root) for root in roots]
    
    while stack:
        current_node, current_path = stack.pop()
        # 逆序遍历子节点，保证输出顺序与示例一致
        for child in reversed(node_dict[current_node]):
            new_path = f"{current_path}/{child}"
            paths.append(new_path)
            # 将子节点和新路径压入栈，继续遍历后续层级
            stack.append((child, new_path))
    
    # 按字典序排序，匹配示例输出顺序
    paths.sort()
    return paths

# 生成并打印路径
for path in generate_all_paths(dictionary):
    print(path)

代码说明 #

1. 根节点识别：find_root_nodes函数找出所有没有父节点的根节点（未出现在任何子节点列表中的键）。
2. 迭代遍历：使用栈实现深度优先遍历，每个栈元素存储当前节点和对应的路径，避免递归的深度限制问题。
3. 路径生成：遍历每个节点的子节点，生成新路径并加入结果列表，再将子节点和新路径压入栈继续处理。
4. 排序输出：最后对路径列表按字典序排序，保证输出顺序与示例一致。

优势 #

• 适配大规模数据：迭代方式无递归深度限制，层级极深的场景也能稳定运行。
• 高效：时间复杂度为O(N)（N为节点总数），每个节点仅处理一次。
• 灵活：可直接扩展处理多根节点的场景。

内容的提问来源于stack exchange，提问作者Görkem Akıncı