如何使用递归记录父子层级结构的所有路径并生成指定格式DataFrame

需求说明 #

遍历存储父子层级关系的DataFrame，输出所有深度不固定的路径到新DataFrame：

• 原始DataFrame包含parent、child、highest三列，highest=1对应行的parent为顶层根节点，无上层父节点
• 输出DataFrame列按层级从高到低排列，深度不足的路径对应低位层级列留空

原始样例数据：

期望输出样例：

优化实现代码 #

你原有的递归逻辑只做了遍历没有存储路径，调整后代码如下：

import pandas as pd

# 样例数据构造，实际使用时替换为自己的df即可
df = pd.DataFrame({
    'parent': ['a', 'b', 'b', 'd'],
    'child': ['b', 'c', 'd', 'e'],
    'highest': [1, 0, 0, 0]
})

all_paths = [] # 存储所有完整路径的全局列表

def search(parent, current_path):
    # 将当前节点加入路径
    current_path.append(parent)
    # 查找当前节点的所有子节点
    children = df[df['parent'] == parent]['child'].tolist()
    
    if not children: # 无可用子节点，当前路径为完整路径，存入列表
        all_paths.append(current_path.copy())
    else: # 递归遍历所有子节点
        for child in children:
            search(child, current_path)
    # 递归回溯，弹出当前节点
    current_path.pop()

# 遍历所有根节点启动递归
for root in df[df['highest'] == 1]['parent'].unique().tolist():
    search(root, [])

# 转换为目标格式DataFrame
max_depth = max(len(p) for p in all_paths)
# 列名按层级从高到低命名
result = pd.DataFrame(
    [p + [None]*(max_depth - len(p)) for p in all_paths],
    columns = [f'level {i}' for i in reversed(range(max_depth))]
)

print(result)

逻辑说明 #

• 递归函数新增current_path参数记录当前遍历的节点路径，每进入一个节点就把节点加入路径，递归返回前回溯弹出节点
• 当节点没有子节点时，判定为路径末端，将当前路径副本存入全局路径列表，避免后续回溯修改路径内容
• 所有路径遍历完成后，先统计最大深度，给长度不足的路径补空值，再按层级从高到低设置列名即可得到目标格式的结果

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