JavaScript 将扁平的数组输出转为树形结构(需要考虑性能)

 扁平数组转为树形结构，做后台管理系统时也是经常用到的功能；面试时也是常常出现的，今天实现一下，引用两篇掘金大佬的文章，感谢大佬

 一、什么是好算法？什么是坏算法？

        判断一个算法的好坏，一般从执行时间和占用空间来看,执行时间越短，占用的内存空间越小，那么它就是好的算法。对应的，我们常常用时间复杂度代表执行时间，空间复杂度代表占用的内存空间。

时间复杂度

时间复杂度的计算并不是计算程序具体运行的时间，而是算法执行语句的次数。

 随着n的不断增大，时间复杂度不断增大，算法花费时间越多。 常见的时间复杂度有

• 常数阶O(1)
• 对数阶O(log2 n)
• 线性阶O(n)
• 线性对数阶O(n log2 n)
• 平方阶O(n^2)
• 立方阶O(n^3)
• k次方阶O(n^K)
• 指数阶O(2^n)

 计算方法

1. 选取相对增长最高的项
2. 最高项系数是都化为1
3. 若是常数的话用O(1)表示

举个例子：如f(n)=3*n^4+3n+300 则 O(n)=n^4

通常我们计算时间复杂度都是计算最坏情况。计算时间复杂度的要注意的几个点

• 如果算法的执行时间不随n的 增加而 增长，假如算法中有上千条语句，执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。 举例如下：代码执行100次，是一个常数，复杂度也是O(1)。

    let x = 1;
    while (x <100) {
     x++;
    }

• 有多个循环语句时候，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的方法决定的。举例如下：在下面for循环当中，外层循环每执行一次，内层循环要执行n次，执行次数是根据n所决定的，时间复杂度是O(n^2)。 

  for (i = 0; i < n; i++){
         for (j = 0; j < n; j++) {
             // ...code
         }
     }

• 循环不仅与n有关，还与执行循环判断条件有关。举例如下：在代码中，如果arr[i]不等于1的话，时间复杂度是O(n)。如果arr[i]等于1的话，循环不执行，时间复杂度是O(0)。 

    for(var i = 0; i<n && arr[i] !=1; i++) {
    // ...code
    }

 空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间的大小。

计算方法： 

1. 忽略常数，用O(1)表示
2. 递归算法的空间复杂度=(递归深度n)*(每次递归所要的辅助空间)

计算空间复杂度的简单几点

• 仅仅只复制单个变量，空间复杂度为O(1)。举例如下：空间复杂度为O(n) = O(1)。

   let a = 1;
   let b = 2;
   let c = 3;
   console.log('输出a,b,c', a, b, c);

• 递归实现，调用fun函数，每次都创建1个变量k。调用n次，空间复杂度O(n*1) = O(n)。

    function fun(n) {
       let k = 10;
       if (n == k) {
           return n;
       } else {
           return fun(++n)
       }
    }

测试数据：

    const array = [
      { 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" },
      { id: 11, parentId: 10, name: "菜单11" },
      { id: 12, parentId: 11, name: "菜单12" },
      { id: 13, parentId: 12, name: "菜单13" },
      { id: 14, parentId: 13, name: "菜单14" },
    ];

二、扁平的数组转为树形结构

1. 性能不好(1W条数据需要 18s)，实现较为简单：递归方式

/**
 * 方法一：简单递归
 * @param { Array } data 数据源
 * @param { Array } result 输出结果
 * @param { Number | String } parentId 根id
 */

const getChildren = (data, result = [], parentId) => {
  for (const item of data) {
    if (item.parentId === parentId) {
      const newItem = { ...item, children: [] };
      result.push(newItem);
      getChildren(data, newItem.children, item.id);
    }
  }
  return result;
};

const res2 = getChildren(array, [], 0);
console.log("res2", res2);

/**
 * 方法二：递归实现
 * @param { Array } list 数组
 * @param { String } parentId 父级 id
 * @param { Object } param2 可配置参数
 */

const generateTree = (
  list,
  parentId = 0,
  { idName = "id", parentIdName = "parentId", childName = "children" } = {}
) => {
  if (!Array.isArray(list)) {
    throw new Error("type only Array");
    // new Error("type only Array");
    return list;
  }
  return list.reduce((pre, cur) => {
    // 找到parentId 的子节点之后，递归找子节点的下一级节点
    if (cur[parentIdName] === parentId) {
      const children = generateTree(list, cur[idName]);
      if (children?.length) {
        cur[childName] = children;
      }
      return [...pre, cur];
    }
    return pre;
  }, []);
};
const result = generateTree(array, 0);

2. 性能可以，采用非递归方式

         应用了对象保存的是引用的特点，每次将当前节点的 id 作为 key，保存对应节点的引用信息，遍历数组时，每次更新 objMap 的 children 信息，这样 objMap中保留了所有节点极其子节点，最重要的是，我们只需要遍历一遍数组，时间复杂度为O(n)。使用这种方式，1W数据 计算时长只需要60ms！

/**
 * 方法三：不用递归的简单循环
 * @param { Array } 源数据
 */

const arrayToTree = (items) => {
  const result = []; // 结果集
  const itemMap = {};

  // 先转成map存储
  for (const item of items) {
    itemMap[item.id] = { ...item, children: [] };
  }

  for (const item of items) {
    const id = item.id;
    const parentId = item.parentId;
    const treeItem = itemMap[id];

    if (parentId === 0) {
      result.push(treeItem);
    } else {
      if (!itemMap[parentId]) {
        itemMap[parentId] = { children: [] };
      }
      itemMap[parentId].children.push(treeItem);
    }
  }
  return result;
};

const res3 = arrayToTree(array);
console.log("res3", res3);

/**
 * 方法四：非递归实现 (映射 + 引用)
 * 前提：每一项都有parentId，根元素
 * @param { Array } list 数组
 * @param { String } rootId 根元素Id
 * @param { Object } param2 可配置参数
 */

const generateTree2 = (
  list,
  rootId = 0,
  { idName = "id", parentIdName = "parentId", childName = "childern" } = {}
) => {
  if (!Array.isArray(list)) {
    new Error("type only Array");
    return list;
  }
  const objMap = {}; //暂存数组以 id 为 key的映射关系
  const result = []; // 结果

  for (const item of list) {
    const id = item[idName];
    const parentId = item[parentIdName];

    // 该元素有可能已经放入map中，（找不到该项的parentId时 会先放入map
    objMap[id] = !objMap[id] ? item : { ...item, ...objMap[id] };

    const treeItem = objMap[id]; // 找到映射关系那一项（注意这里是引用）

    if (parentId === rootId) {
      // 已经到根元素则将映射结果放进结果集
      result.push(treeItem);
    } else {
      // 若父元素不存在，初始化父元素
      if (!objMap[parentId]) {
        objMap[parentId] = [];
      }

      // 若无该根元素则放入map中
      if (!objMap[parentId][childName]) {
        objMap[parentId][childName] = [];
      }
      objMap[parentId][childName].push(treeItem);
    }
  }
  return result;
};

const res = generateTree2(array);
console.log("res", res);

大佬原文地址1：1w条数据，平铺数组转树形结构https://juejin.cn/post/6988901231674523661#comment

大佬原文地址2：面试了十几个高级前端，竟然连（扁平数据结构转Tree）都写不出来https://juejin.cn/post/6983904373508145189?share_token=24aefc40-dd9e-465d-920b-7380e8728f2a#comment