Python实现父子节点层级排序与坐标定位问题求助

需求说明 #

• 将字典列表按父节点下的层级顺序排列
• 为每个节点计算x、y坐标：子节点x轴相对父节点偏移20px；y轴根据上方所有节点总数，每个节点偏移20px

当前数据列表 #

my_list = [
    {"name": "AAA", "parent": "none", "children": ["BBB", "CCC", "DDD"], "x": 0, "y": 0},
    {"name": "BBB", "parent": "AAA", "children": ["EEE"], "x": 0, "y": 0},
    {"name": "CCC", "parent": "AAA", "children": ["FFF"], "x": 0, "y": 0},
    {"name": "DDD", "parent": "AAA", "children": [], "x": 0, "y": 0},
    {"name": "EEE", "parent": "BBB", "children": [], "x": 0, "y": 0},
    {"name": "FFF", "parent": "CCC", "children": [], "x": 0, "y": 0},
    {"name": "GGG", "parent": "none", "children": ["HHH"], "x": 0, "y": 0},
    {"name": "HHH", "parent": "GGG", "children": [], "x": 0, "y": 0},
]

期望输出 #

AAA (0, 0)
    BBB (20, 20)
        EEE (40, 40)
    CCC (20, 60)
        FFF (40, 80)
    DDD (20, 100)
GGG (0, 120)
    HHH (0, 140)

尝试的代码（存在问题） #

for value in name_list:
    if value["parent"] == "none":
        loop = True
        loop_list = value["children"]
        while loop:
            for child_name in loop_list:
                child = get_item(child_name)

                if len(child["children"]) != 0:
                    loop_list = child["children"]

                print("result") ;(

解决方案 #

步骤1：构建节点映射字典 #

先将列表转换为以节点名称为键的字典，方便快速查找节点：

node_map = {node["name"]: node for node in my_list}

步骤2：递归遍历计算坐标并排序 #

使用深度优先递归遍历，维护当前y坐标偏移，处理节点顺序和坐标赋值：

def process_tree(root_name, current_x, current_y, node_map, result):
    node = node_map[root_name]
    # 赋值当前节点坐标
    node["x"] = current_x
    node["y"] = current_y
    result.append(node)
    # 处理子节点，更新y坐标
    next_y = current_y + 20
    for child_name in node["children"]:
        next_y = process_tree(child_name, current_x + 20, next_y, node_map, result)
    # 返回当前分支处理完后的下一个y坐标
    return next_y

# 处理所有根节点
sorted_list = []
current_global_y = 0
for node in my_list:
    if node["parent"] == "none":
        current_global_y = process_tree(node["name"], 0, current_global_y, node_map, sorted_list)

步骤3：按树形格式输出 #

根据节点x坐标计算缩进，输出符合要求的格式：

for node in sorted_list:
    indent = "    " * (node["x"] // 20)
    print(f"{indent}{node['name']} ({node['x']}, {node['y']})")

完整代码 #

my_list = [
    {"name": "AAA", "parent": "none", "children": ["BBB", "CCC", "DDD"], "x": 0, "y": 0},
    {"name": "BBB", "parent": "AAA", "children": ["EEE"], "x": 0, "y": 0},
    {"name": "CCC", "parent": "AAA", "children": ["FFF"], "x": 0, "y": 0},
    {"name": "DDD", "parent": "AAA", "children": [], "x": 0, "y": 0},
    {"name": "EEE", "parent": "BBB", "children": [], "x": 0, "y": 0},
    {"name": "FFF", "parent": "CCC", "children": [], "x": 0, "y": 0},
    {"name": "GGG", "parent": "none", "children": ["HHH"], "x": 0, "y": 0},
    {"name": "HHH", "parent": "GGG", "children": [], "x": 0, "y": 0},
]

node_map = {node["name"]: node for node in my_list}
sorted_list = []

def process_tree(root_name, current_x, current_y, node_map, result):
    node = node_map[root_name]
    node["x"] = current_x
    node["y"] = current_y
    result.append(node)
    next_y = current_y + 20
    for child_name in node["children"]:
        next_y = process_tree(child_name, current_x + 20, next_y, node_map, result)
    return next_y

current_global_y = 0
for node in my_list:
    if node["parent"] == "none":
        current_global_y = process_tree(node["name"], 0, current_global_y, node_map, sorted_list)

for node in sorted_list:
    indent = "    " * (node["x"] // 20)
    print(f"{indent}{node['name']} ({node['x']}, {node['y']})")

代码说明 #

• 节点映射字典：避免每次遍历列表查找节点，提升处理效率。
• 递归遍历：深度优先遍历保证节点层级顺序正确，同时传递更新y坐标，确保每个节点的y值为上方所有节点总数乘以20。
• 缩进计算：根据x坐标（每20px对应一级）生成缩进，实现树形输出效果。

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