JavaScript 数组转树形结构（递归算法）

概述

将带有 id 和 parent_id 的扁平数组转换为嵌套树形结构，是前端处理菜单、组织架构、分类等层级数据的核心算法。

完整代码

function listToTree(data) {
    let tree = [];
    let map = {};

    // 第一步：所有节点放入 HashMap，初始化 children
    data.forEach(node => {
        map[node.id] = { ...node, children: [] };
    });

    // 第二步：构建树形关系
    for (let id in map) {
        let node = map[id];
        if (node.parent_id === null || node.parent_id === undefined) {
            tree.push(node);  // 根节点
        } else {
            if (!map[node.parent_id]) {
                map[node.parent_id] = { children: [] };
            }
            map[node.parent_id].children.push(node);
        }
    }

    return tree;
}

// 测试
let data = [
    { "id": 1444, "name": "项目A", "parent_id": null },
    { "id": 1445, "name": "子项目1", "parent_id": 1444 },
    { "id": 1446, "name": "子项目2", "parent_id": 1444 }
];

let tree = listToTree(data);
console.log(JSON.stringify(tree, null, 2));

输出结果

[
  {
    "id": 1444,
    "name": "项目A",
    "parent_id": null,
    "children": [
      { "id": 1445, "name": "子项目1", "parent_id": 1444, "children": [] },
      { "id": 1446, "name": "子项目2", "parent_id": 1444, "children": [] }
    ]
  }
]

算法思路

1. 使用 HashMap（map）存储所有节点，key 为 id，实现 O(1) 查找
2. 遍历 map，根据 parent_id 判断是否为根节点
3. 非根节点挂载到对应父节点的 children 数组中

时间复杂度

O(n)，只需遍历两次数组。比递归嵌套循环的 O(n²) 效率高得多，万级数据也能毫秒级完成。

递归版本（备选）

function listToTreeRecursive(data, parentId) {
    return data
        .filter(item => item.parent_id === parentId)
        .map(item => ({
            ...item,
            children: listToTreeRecursive(data, item.id)
        }));
}

// 使用
let tree = listToTreeRecursive(data, null);

注意事项

• 确保函数名一致：代码中定义 listToTree 就不要调用 buildTree
• 注意 parent_id 的类型：null、undefined 还是 0
• 大数据量建议 HashMap 版本，小数据量递归版本更简洁

标签：