List转树形结构

将一个列表（List）转换为树形结构通常涉及将数据中的某些元素作为父节点，而其他元素作为子节点，按照层级关系组织。具体方法根据你的数据结构和需求会有所不同。下面是一个常见的例子，展示如何将一个带有父子关系的列表转换为树形结构。

示例数据

假设我们有一个这样的列表，包含了元素的 ID 和父节点的 ID，表示了树形结构的父子关系：

data = [
    {"id": 1, "parent_id": None, "name": "Root"},
    {"id": 2, "parent_id": 1, "name": "Child 1"},
    {"id": 3, "parent_id": 1, "name": "Child 2"},
    {"id": 4, "parent_id": 2, "name": "Child 1.1"},
    {"id": 5, "parent_id": 2, "name": "Child 1.2"},
    {"id": 6, "parent_id": 3, "name": "Child 2.1"}
]

目标结构

将上述数据转换为树形结构后，我们的目标是得到一个类似下面的树状结构：

{
    "id": 1,
    "name": "Root",
    "children": [
        {
            "id": 2,
            "name": "Child 1",
            "children": [
                {"id": 4, "name": "Child 1.1", "children": []},
                {"id": 5, "name": "Child 1.2", "children": []}
            ]
        },
        {
            "id": 3,
            "name": "Child 2",
            "children": [
                {"id": 6, "name": "Child 2.1", "children": []}
            ]
        }
    ]
}

转换代码

from collections import defaultdict

def list_to_tree(data):
    # 创建一个字典存储每个节点
    tree = {}
    # 创建一个字典来存储子节点，方便插入
    children_map = defaultdict(list)
    
    # 将每个元素放到tree中，并按parent_id分类
    for item in data:
        tree[item["id"]] = {**item, "children": []}
        if item["parent_id"] is not None:
            children_map[item["parent_id"]].append(item["id"])
    
    # 将子节点插入到父节点的children列表中
    for parent_id, child_ids in children_map.items():
        for child_id in child_ids:
            tree[parent_id]["children"].append(tree[child_id])
    
    # 找到根节点（parent_id 为 None 的节点）
    root = [node for node in tree.values() if node["parent_id"] is None][0]
    
    return root

# 转换为树形结构
tree = list_to_tree(data)

# 打印结果
import json
print(json.dumps(tree, indent=4, ensure_ascii=False))

代码解析

数据存储：我们使用一个 tree 字典来存储每个节点，键是 id，值是节点本身（包含父子关系）。
父子关系建立：通过 children_map 字典，我们将每个父节点的 id 作为键，子节点的 id 列表作为值。这样，我们就能够快速查找每个父节点对应的子节点。
构建树：遍历 children_map，将每个子节点添加到对应父节点的 children 列表中。
返回根节点：找到 parent_id 为 None 的节点作为树的根节点，并返回它。

输出结果

{
    "id": 1,
    "parent_id": null,
    "name": "Root",
    "children": [
        {
            "id": 2,
            "parent_id": 1,
            "name": "Child 1",
            "children": [
                {
                    "id": 4,
                    "parent_id": 2,
                    "name": "Child 1.1",
                    "children": []
                },
                {
                    "id": 5,
                    "parent_id": 2,
                    "name": "Child 1.2",
                    "children": []
                }
            ]
        },
        {
            "id": 3,
            "parent_id": 1,
            "name": "Child 2",
            "children": [
                {
                    "id": 6,
                    "parent_id": 3,
                    "name": "Child 2.1",
                    "children": []
                }
            ]
        }
    ]
}

总结

这个方法通过利用字典和列表的组合，按照父子关系将一个扁平的列表数据转换为树形结构。它的优势在于清晰的逻辑和高效的插入过程。你可以根据你的实际数据结构做相应调整。如果需要处理更复杂的层级关系，或者节点包含更多属性，也可以进一步扩展该方法。

秒客网