扁平数据转树形结构探究

快来打我* 2023-01-18 12:19 9阅读 0赞

## 前言 ##

前段时间，由于业务需求，需要把后端返回的扁平化的数组结构，转换成树形结构，以适应于前端多级菜单栏的渲染，一开始查阅了一些资料，但发现并不是自己想要的答案。为了得到自己最想要的结果，特地花了时间对该问题进行了一些探究性尝试，并对探究过程和结果进行记录。希望能给遇到相同问题的人提供一些参考。

原始的数据结构如下：

// id为当前菜单的唯一标识
    // parentId 为上级父类菜单标识
    // name为菜单名
    // 后端返回的数据级数具有不确定性，即可能有1/2/3/4级等，data集合的个数具有不确定性，即可能有10个、8个等。
    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" },
      {  id: 11, parentId: 10, name: "菜单11" },
      {  id: 12, parentId: 11, name: "菜单12" },
      {  id: 13, parentId: 12, name: "菜单13" },
      {  id: 14, parentId: 13, name: "菜单14" },
      // 此处省略后面的内容了，可能还有多个........
    ];

目标数据结构如下：

let result = [
      { 
        id: 1,
        name: "菜单1",
        parentId: 0,
        chilren: [
          { 
            id: 4,
            name: "菜单4",
            parentId: 1,
            chilren: [
              { 
                id: 7,
                name: "菜单7",
                parentId: 0,
                chilren: [],
              },
            ],
          },
          { 
            id: 5,
            name: "菜单5",
            parentId: 0,
            chilren: [],
          },
        ],
      },
      { 
        id: 2,
        name: "菜单2",
        parentId: 0,
        chilren: [
          { 
            id: 6,
            name: "菜单6",
            parentId: 0,
            chilren: [],
          },
        ],
      },
      //此处省略后面的内容........
    ];

## 初步分析 ##

初步分析思路是：使用递归算法，即遍历dataJSONArray数组，取出每一个对象，获取其id，然后再遍历整个dataJSONArray，取出每个对象的parentId，如果id==parentId就是它的children了，将该对象push进children，循环往复，直至每个对象都正确找到它的孩子节点，如下是具体代码分析。

## 递归算法 ##

*  **递归代码算法**

**递归算法测试**

![在这里插入图片描述][20210506103507117.png_pic_center]

`思考：从代码实现中，可以看到，使用了递归算法，可能会存在多次调用queryChildren(data[i], data)的情况，也就意味着，当调用的过多的函数，到达了临界值，可能导致调用堆栈无法容纳这些调用的返回地址，就出现的堆栈溢出的极端情况。`

**堆栈溢出模拟**

// 随机写一个多层次多数据的原始数据
    let dataJSONArray = [];
    for (let i = 0; i < 100000; i++) { 
      let map = { };
      map.id = i + 1;
      map.name = "菜单" + i + 1;
      map.parentId = i;
      dataJSONArray.push(map);
      console.log("=======i======" + i);
    }
    let result = transToTree1(dataJSONArray);
    // 可以看到，在该测试情况下，出现了堆栈溢出的极端情况，虽然这种源数据结构几乎不存在，但是这里为了说明存在堆栈溢出的情形特地模拟出来。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpcHNob3BfZmluX2Rldg_size_16_color_FFFFFF_t_70_pic_center]

另外还有一种情形也会出现堆栈溢出

// 如果源数据出现类似下面的情形，即id==parentId，会出现无限死循环。所以，如果源数据存在这种情况，需要在代码里做一个特殊的判断处理。
    { "id": 0, "parentId": 0, "name": "菜单1"}

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpcHNob3BfZmluX2Rldg_size_16_color_FFFFFF_t_70_pic_center 1]

## 二次循环算法 ##

实现思路：第一次循环，源数据dataJSONArray，转换成一个map，dataJSONArray每个对象的id作为map的id，使其能通过 id 快速查询。第二次循环，遍历源数据dataJSONArray，通过parentId与第一次循环的map进行匹对，数据封装。

![在这里插入图片描述][20210506103704171.png_pic_center]

二次循环算法相较于递归算法的实现，避免了堆栈溢出的问题，复杂度得到了一定程度的降低，至于算法效率有没有得到了提高暂时无法确定，后面会有测试比较。

虽然避免了堆栈溢出的问题，但也增加了时间复杂度，遍历的次数是data.length\*2（有点多），能不能只循环一次就能解决问题呢？经过一番折腾，成功地将二次循环减少为一次循环。

## 一次循环算法 ##

一次循环算法的主要思路是：使用对象变量的特性，利用 map 结构直接指向 children数组，在循环中初始化的同时还能快速查找插入相应的 children 里。

## 基于filter的低代码实现 ##

虽然实现了一次循环算法，但是总感觉代码太多了，于是查找了下资料，发现确实是有人可以低代码就可以实现了，下面是其中的一种基于filter的低代码实现。

function transToTree4(data) { 
      // 对源数据深度克隆，避免对源数据产生影响
      let cloneData = JSON.parse(JSON.stringify(data));
      // 循环所有项，并添加children属性
      return cloneData.filter((father) => { 
        // 返回每一项的子级数组
        let branchArr = cloneData.filter((child) => father.id == child.parentId);
        //给父级添加一个children属性，并赋值
        branchArr.length > 0 ? (father.children = branchArr) : "";
        //返回第一层
        return father.parentId == 0;
      });
    }

## 各种算法性能比拼 ##

经过一番的努力，已经成功掌握了四种扁平化数据转换成树形结构的算法了，但是从科学严谨的角度上来说，并不是低代码的算法就一定好，二次循环的就一定比一次循环的要好。所以，我决定采用控制变量法的方式，对这四种算法进行一个性能的比较并得出结果。

*  步骤

1、设置测试源数据：

//通过nums控制源数据的个数
    //通过map.parentId = Math.floor(Math.random() * nums);控制每个菜单的上级，随机
    let nums = 10000;
    for (let i = 0; i < nums; i++) { 
      let map = { };
      map.id = i + 1;
      map.name = "菜单" + i + 1;
      //设置每个菜单的父类菜单
      map.parentId = Math.floor(Math.random() * nums);
      dataJSONArray.push(map);
    }

2、设置测试样例数据，nums设置为100,1000,2000,3000,5000,10000,50000。每次测试10次，取平均值。

3、统计每组测试数据的结果数据，进行比较分析。

*  实验
    
    部分实验截图

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpcHNob3BfZmluX2Rldg_size_16_color_FFFFFF_t_70_pic_center 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpcHNob3BfZmluX2Rldg_size_16_color_FFFFFF_t_70_pic_center 3]

<table> 
 <thead> 
  <tr> 
   <th>算法</th> 
   <th>100</th> 
   <th>1000</th> 
   <th>2000</th> 
   <th>3000</th> 
   <th>5000</th> 
   <th>10000</th> 
   <th>50000</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>递归</td> 
   <td>0ms</td> 
   <td>0.2ms</td> 
   <td>0.2ms</td> 
   <td>1.8ms</td> 
   <td>3.6ms</td> 
   <td>10ms</td> 
   <td>10.6ms</td> 
  </tr> 
  <tr> 
   <td>二次循环</td> 
   <td>0.2ms</td> 
   <td>0.8ms</td> 
   <td>1.8ms</td> 
   <td>2.4ms</td> 
   <td>7.6ms</td> 
   <td>10.6ms</td> 
   <td>38.2ms</td> 
  </tr> 
  <tr> 
   <td>一次循环</td> 
   <td>0.2ms</td> 
   <td>1.2ms</td> 
   <td>3.8ms</td> 
   <td>4.2ms</td> 
   <td>6.8ms</td> 
   <td>9.2ms</td> 
   <td>33.8ms</td> 
  </tr> 
  <tr> 
   <td>filter</td> 
   <td>0.8ms</td> 
   <td>18.6ms</td> 
   <td>52.4ms</td> 
   <td>93.2ms</td> 
   <td>280ms</td> 
   <td>681.2ms</td> 
   <td>16402.2ms</td> 
  </tr> 
 </tbody> 
</table>

**结论**

*  实验结果表明：在上述四种算法中，虽然递归算法存在堆栈溢出问题，但是在几组不同测试源数据下，它的耗时都是最少的，执行效率是最高的，网上说的它的效率低下的说法，我表示有所保留和怀疑。
 *  filter算法虽然代码量少，简单，但是耗时在几种算法里是最大的。
 *  二次循环算法与一次循环算法，整体耗时差异不大，数据量少时，二次循环耗时少，但是当数据量上升到一定程度，一次循环性能还比二次循环稍好一点点。
 *  在数据量少的情况下，这几种算法的耗时差异不大，但是，当数据量大于2000左右时，filter算法的耗时显著增加，甚至当数据量大于5w时，其他算法的耗时都不超过1s，而filter算法已经超过了10s。
 *  至于采用哪种算法好，需要根据项目的具体情况来进行选择。

## 总结 ##

通过本次自己较为深入的研究和实践，得到了很大的收获。主要有以下几点：

*  遇到问题，需要进行科学严谨的分析，采用合适的方法论来进行验证和探索。
 *  纸上得来终觉浅，绝知此事要躬行，实践出真知，很多结论，需要自己去实践才能得出结果，而不是人云亦云。

通过记录这一篇简单的研究博客，记录下自己技术研究的成长之路，并持之以恒，不断成长。也希望能给遇到类似问题的朋友提供一些帮助和参考，与大家共勉。

附全部代码：

[20210506103507117.png_pic_center]: /images/20221021/0084f484e2e84b2e8f040c52c71abf48.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpcHNob3BfZmluX2Rldg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221021/8b4584947f2a4af1a2d87e66805ea1b6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpcHNob3BfZmluX2Rldg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221021/8cefe2088a094c6aba374b681b40413f.png
[20210506103704171.png_pic_center]: /images/20221021/937b0585760f453094f317cff491eb47.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpcHNob3BfZmluX2Rldg_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221021/15ea41de16364ef28ccf761f674220a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpcHNob3BfZmluX2Rldg_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221021/30945911299b499eb84389bcb41ff367.png