本文共 4498 字，大约阅读时间需要 14 分钟。

将扁平化数组转换为树形结构的多种方法探索

随着前端项目需求逐渐升级，经常会遇到需要将后端返回的扁平化数组结构转换为树形结构的问题。为解决这一需求，我进行了深入的研究和实践，总结出几种不同的实现方法，并对它们进行了性能测试和对比分析。以下是本文的具体内容和结论。

问题背景

首先，明确一下问题的背景和目标数据结构：

原始数据结构

let dataJSONArray = [
  { id: 1, parentId: 0, name: "菜单1" },
  { id: 2, parentId: 0, name: "菜单2" },
  { id: 3, parentId: 0, name: "菜单3" },
  { id: 4, parentId: 1, name: "菜单4" },
  { id: 5, parentId: 1, name: "菜单5" },
  { id: 6, parentId: 2, name: "菜单6" },
  { id: 7, parentId: 4, name: "菜单7" },
  { id: 8, parentId: 7, name: "菜单8" },
  { id: 9, parentId: 8, name: "菜单9" },
  { id: 10, parentId: 9, name: "菜单10" },
  // ... 后续数据以此类推
];

目标数据结构

let result = [
  { 
    id: 1, 
    name: "菜单1", 
    parentId: 0, 
    children: [
      { id: 4, name: "菜单4", parentId: 1, children: [ { id: 7, ... } ] },
      { id: 5, name: "菜单5", parentId: 0, children: [] }
    ]
  },
  { 
    id: 2, 
    name: "菜单2", 
    parentId: 0, 
    children: [
      { id: 6, name: "菜单6", parentId: 0, children: [] }
    ]
  },
  // ... 后续数据以此类推
];

递归算法

实现思路

使用递归算法，通过遍历数据数组，找到每个菜单的父菜单，并将其作为子菜单添加到目标菜单的 children 数组中。具体实现如下：

function transToTree1(data) {
  const treeList = [];
  for (let i = 0, len = data.length; i < len; i++) {
    if (!data[i].parentId) {
      const item = queryChildren(data[i], data);
      treeList.push(item);
    }
  }
  return treeList;
}
function queryChildren(parent, data) {
  const children = [];
  for (let i = 0; i < data.length; i++) {
    if (data[i].parentId === parent.id) {
      const item = queryChildren(data[i], data);
      children.push(item);
    }
  }
  parent.children = children;
  return parent;
}

优点

• 简洁直观，代码实现简单易懂。
• 适用于数据结构不复杂的情况。

缺点

• 若数据结构呈深度嵌套且层数较多，可能会导致堆栈溢出。例如：

  let dataJSONArray = [
    { id: 0, parentId: 0, name: "菜单1" },
    { id: 1, parentId: 0, name: "菜单2" },
    { id: 2, parentId: 1, name: "菜单3" },
    { id: 3, parentId: 2, name: "菜单4" },
    // ... 依此类推
  ];

  会导致递归调用堆积，进而引发堆栈溢出问题。

二次循环算法

实现思路

首先，将数据转换为一个 record 目录，便于通过 parentId快速查找父菜单。然后，通过两个循环分别处理父菜单和子菜单：

function transToTree2(data) {
  const treeList = [];
  const record = {};
  const length = data.length;
  
  // 第一次循环：建立记录目录
  for (let i = 0; i < length; i++) {
    const item = data[i];
    item.children = [];
    record[item.id] = item;
  }
  
  // 第二次循环：根据 parentId 比较
  for (let i = 0; i < length; i++) {
    const item = data[i];
    if (item.parentId) {
      if (record[item.parentId]) {
        record[item.parentId].children.push(item);
      }
    } else {
      treeList.push(item);
    }
  }
  return treeList;
}

优点

• 性能比递归算法更稳定，适合大规模数据。
• 简单易于实现，效率较高。

缺点

• 时间复杂度为 O(n)，显著高于一次循环算法。

一次循环算法

实现思路

进一步优化至一次循环，通过记录父菜单的 children 数组，并在循环中同时初始化和添加子菜单：

function transToTree3(data, options = {}) {
  const { key = "id", childKey = "children", parentKey = "parentId" } = options;
  const treeList = [];
  const record = {};
  
  for (let i = 0, len = data.length; i < len; i++) {
    const item = data[i];
    const id = item[key];
    
    if (!id) {
      continue;
    }
    
    if (record[id]) {
      item[childKey] = record[id];
    } else {
      item[childKey] = record[id] = [];
    }
    
    if (item[parentKey]) {
      const parentId = item[parentKey];
      if (!record[parentId]) {
        record[parentId] = [];
      }
      record[parentId].push(item);
    } else {
      treeList.push(item);
    }
  }
  return treeList;
}

优点

• 时间复杂度为 O(n)，性能优于二次循环算法。
• 代码简洁，逻辑清晰。

缺点

• 如果多个菜单的 ID 重复（理论上不可能），可能导致覆盖问题，但通过使用 record 记录可以避免。

基于 filter 的低代码实现

实现思路

通过 JavaScript filter 方法，直接将父菜单和子菜单匹配：

function transToTree4(data) {
  // 深度克隆数据，避免修改原始数据
  const cloneData = JSON.parse(JSON.stringify(data));
  return cloneData.filter((father) => {
    const branchArr = cloneData.filter((child) => father.id === child.parentId);
    if (branchArr.length > 0) {
      father.children = branchArr;
    }
    return father.parentId === 0;
  });
}

优点

• 代码量更少，实现简单易懂。
• 适合小型项目或需求不严格的场景。

缺点

• 性能较差，尤其在数据量较大时。

性能对比测试

通过实验数据对比各算法的性能，设定不同的数据规模（如 100、1000、2000、3000、5000、10000、50000），并统计每组数据的平均耗时：

结论

通过本次实验可以看出：

建议

• 小型项目：使用递归算法或基于 filter 的低代码实现。
• 中小型项目：选择一次循环或二次循环算法。
• 大型项目：优先选择一次循环算法。

总结

通过本次研究，我掌握了几种扁平化数据转树形结构的算法，并通过实验对各自的优缺点有了深入了解。同时，也学到了项目开发过程中，科学严谨分析和实践检 验的重要性。未来，我将继续深入研究，并尝试结合实际需求，选择最适合的解决方案。