扁平数据转树形结构探究
发布日期：2021-05-10 05:11:06
浏览次数：3
分类：技术文章
本文共 13392 字，大约阅读时间需要 44 分钟。
前言
前段时间，由于业务需求，需要把后端返回的扁平化的数组结构，转换成树形结构，以适应于前端多级菜单栏的渲染，一开始查阅了一些资料，但发现并不是自己想要的答案。为了得到自己最想要的结果，特地花了时间对该问题进行了一些探究性尝试，并对探究过程和结果进行记录。希望能给遇到相同问题的人提供一些参考。
原始的数据结构如下：
// 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，循环往复，直至每个对象都正确找到它的孩子节点，如下是具体代码分析。
递归算法
- 递归代码算法
function transToTree1(data) { //定义tree数组 const treeList = []; for (let i = 0, len = data.length; i < len; i++) { //找出有父类的对象 if (!data[i].parentId) { //查询其父类，并拼接对象 const item = queryChildren(data[i], data); // tree数组接收封装后的对象 treeList.push(item); } } return treeList;}function queryChildren(parent, data) { //定义子类children数组 const children = []; //遍历原数组 for (let i = 0, len = data.length; i < len; i++) { //如果它的父类id === parent的id，递归继续查询 if (data[i].parentId === parent.id) { const item = queryChildren(data[i], data); //children数组接收封装后的对象 children.push(item); } } parent.children = children; return parent;} 递归算法测试
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 = transToTree1(dataJSONArray);console.log(result);console.log(JSON.stringify(result, null, 2));//可以从下图中看到已经得到了想要的结果//输出结果[ { id: 1, parentId: 0, name: "菜单1", children: [ { id: 4, parentId: 1, name: "菜单4", children: [ { id: 7, parentId: 4, name: "菜单7", children: [ { id: 8, parentId: 7, name: "菜单8", children: [ { id: 9, parentId: 8, name: "菜单9", children: [ { id: 10, parentId: 9, name: "菜单10", children: [ { id: 11, parentId: 10, name: "菜单11", children: [ { id: 12, parentId: 11, name: "菜单12", children: [ { id: 13, parentId: 12, name: "菜单13", children: [ { id: 14, parentId: 13, name: "菜单14", children: [], }, ], }, ], }, ], }, ], }, ], }, ], }, ], }, ], }, { id: 5, parentId: 1, name: "菜单5", children: [], }, ], }, { id: 2, parentId: 0, name: "菜单2", children: [ { id: 6, parentId: 2, name: "菜单6", children: [], }, ], }, { id: 3, parentId: 0, name: "菜单3", children: [], },]; 
思考：从代码实现中，可以看到，使用了递归算法，可能会存在多次调用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);// 可以看到，在该测试情况下，出现了堆栈溢出的极端情况，虽然这种源数据结构几乎不存在，但是这里为了说明存在堆栈溢出的情形特地模拟出来。 
另外还有一种情形也会出现堆栈溢出
// 如果源数据出现类似下面的情形，即id==parentId，会出现无限死循环。所以，如果源数据存在这种情况，需要在代码里做一个特殊的判断处理。{ "id": 0, "parentId": 0, "name": "菜单1"} 
二次循环算法
实现思路：第一次循环，源数据dataJSONArray，转换成一个map，dataJSONArray每个对象的id作为map的id，使其能通过 id 快速查询。第二次循环，遍历源数据dataJSONArray，通过parentId与第一次循环的map进行匹对，数据封装。
function transToTree2(data) { const treeList = []; const record = { }; const length = data.length; //第一次循环转成map for (let i = 0; i < length; i++) { const item = data[i]; // 重置 children item.children = []; record[item.id] = item; } // 二次循环 for (let i = 0; i < length; i++) { const item = data[i]; //通过id进行比较 if (item.parentId) { if (record[item.parentId]) { record[item.parentId].children.push(item); } } else { //没有父节点的就直接push进数组 treeList.push(item); } } return treeList;}//输出结果：//与递归算法一致，递归算法没有children时没有children，这里展示 
二次循环算法相较于递归算法的实现，避免了堆栈溢出的问题，复杂度得到了一定程度的降低，至于算法效率有没有得到了提高暂时无法确定，后面会有测试比较。
虽然避免了堆栈溢出的问题，但也增加了时间复杂度，遍历的次数是data.length*2（有点多），能不能只循环一次就能解决问题呢？经过一番折腾，成功地将二次循环减少为一次循环。
一次循环算法
一次循环算法的主要思路是：使用对象变量的特性，利用 map 结构直接指向 children数组，在循环中初始化的同时还能快速查找插入相应的 children 里。
function transToTree3(data, options = { }) { //定义map属性 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;} 基于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、统计每组测试数据的结果数据，进行比较分析。
-
实验
部分实验截图
| 算法 | 100 | 1000 | 2000 | 3000 | 5000 | 10000 | 50000 |
|---|---|---|---|---|---|---|---|
| 递归 | 0ms | 0.2ms | 0.2ms | 1.8ms | 3.6ms | 10ms | 10.6ms |
| 二次循环 | 0.2ms | 0.8ms | 1.8ms | 2.4ms | 7.6ms | 10.6ms | 38.2ms |
| 一次循环 | 0.2ms | 1.2ms | 3.8ms | 4.2ms | 6.8ms | 9.2ms | 33.8ms |
| filter | 0.8ms | 18.6ms | 52.4ms | 93.2ms | 280ms | 681.2ms | 16402.2ms |
结论
- 实验结果表明：在上述四种算法中，虽然递归算法存在堆栈溢出问题，但是在几组不同测试源数据下，它的耗时都是最少的，执行效率是最高的，网上说的它的效率低下的说法，我表示有所保留和怀疑。
- filter算法虽然代码量少，简单，但是耗时在几种算法里是最大的。
- 二次循环算法与一次循环算法，整体耗时差异不大，数据量少时，二次循环耗时少，但是当数据量上升到一定程度，一次循环性能还比二次循环稍好一点点。
- 在数据量少的情况下，这几种算法的耗时差异不大，但是，当数据量大于2000左右时，filter算法的耗时显著增加，甚至当数据量大于5w时，其他算法的耗时都不超过1s，而filter算法已经超过了10s。
- 至于采用哪种算法好，需要根据项目的具体情况来进行选择。
总结
通过本次自己较为深入的研究和实践，得到了很大的收获。主要有以下几点：
- 遇到问题，需要进行科学严谨的分析，采用合适的方法论来进行验证和探索。
- 纸上得来终觉浅，绝知此事要躬行，实践出真知，很多结论，需要自己去实践才能得出结果，而不是人云亦云。
通过记录这一篇简单的研究博客，记录下自己技术研究的成长之路，并持之以恒，不断成长。也希望能给遇到类似问题的朋友提供一些帮助和参考，与大家共勉。
附全部代码：
let dataJSONArray = [];let nums = 100;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);}let avg1 = 0;let avg2 = 0;let avg3 = 0;let avg4 = 0;for (let i = 0; i < 5; i++) { let startTime = new Date().getTime(); let result1 = transToTree1(dataJSONArray); let endTime1 = new Date().getTime(); console.log("nums：", nums, ",递归算法耗时(ms)：", endTime1 - startTime); avg1 += endTime1 - startTime;}console.log("10次递归算法耗时均值(ms)", avg1 / 5);for (let i = 0; i < 10; i++) { let endTime1 = new Date().getTime(); let result2 = transToTree2(dataJSONArray); let endTime2 = new Date().getTime(); console.log("nums：", nums, ",二次循环算法耗时(ms)：", endTime2 - endTime1); avg2 += endTime2 - endTime1;}console.log("10次二次循环算法耗时均值(ms)", avg2 / 5);for (let i = 0; i < 10; i++) { let endTime2 = new Date().getTime(); let result3 = transToTree3(dataJSONArray); let endTime3 = new Date().getTime(); console.log("nums：", nums, ",一次循环算法耗时(ms)：", endTime3 - endTime2); avg3 += endTime3 - endTime2;}console.log("10次一次循环算法耗时均值(ms)", avg3 / 5);for (let i = 0; i < 10; i++) { let endTime3 = new Date().getTime(); let result4 = transToTree4(dataJSONArray); let endTime4 = new Date().getTime(); console.log("nums：", nums, ",filter算法耗时(ms)：", endTime4 - endTime3); avg4 += endTime4 - endTime3;}console.log("10次filter算法耗时均值(ms)", avg4 / 5);function transToTree1(data) { //定义tree数组 const treeList = []; for (let i = 0, len = data.length; i < len; i++) { //找出有父类的对象 if (!data[i].parentId) { //查询其父类，并拼接对象 const item = queryChildren(data[i], data); // tree数组接收封装后的对象 treeList.push(item); } } return treeList;}function queryChildren(parent, data) { //定义子类children数组 const children = []; //遍历原数组 for (let i = 0; i < data.length; i++) { //如果它的父类id === parent的id，递归继续查询 if (data[i].parentId === parent.id) { const item = queryChildren(data[i], data); //children数组接收封装后的对象 children.push(item); } } parent.children = children; return parent;}function transToTree2(data) { const treeList = []; const record = { }; const length = data.length; //第一次循环转成map for (let i = 0; i < length; i++) { const item = data[i]; // 重置 children item.children = []; record[item.id] = item; } // 二次循环 for (let i = 0; i < length; i++) { const item = data[i]; //通过id进行比较 if (item.parentId) { if (record[item.parentId]) { record[item.parentId].children.push(item); } } else { //没有父节点直接push进数组 treeList.push(item); } } return treeList;}function transToTree3(data, options = { }) { //定义map属性 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;}function transToTree4(data) { // 对源数据深度克隆，避免对源数据产生影响 let cloneData = 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; });} 转载地址：https://blog.csdn.net/vipshop_fin_dev/article/details/116448606 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关注你微信了！
[***.104.42.241]2023年12月01日 00时07分58秒
关于作者
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！
-- 愿君每日到此一游！
推荐文章
JS对象键值对的使用心得
2019-03-28
js中整型参数超过16位会丢失精度
2019-03-28
js中字符串与数值的弱转换
2019-03-28
VScode中leetcode插件无法登录解决方案
2019-03-28
react安装后vscode中编辑js文件自动补全html功能
2019-03-28
第十讲：工业网络——环间耦合网络（理论）
2019-03-28
mysql where 与having的区别
2019-03-28
MySQL条件查询练习题（含答案）
2019-03-28
mysql插入中文问题解决，干货！
2019-03-28
使用mysqlhotcopy工具快速备份
2019-03-28
常见的数据库
2019-03-28
删除完整性约束
2019-03-28
什么是解释器
2019-03-28
python命名为什么不能用数字开头
2019-03-28
Python的特点
2019-03-28
python认识错误（BUG）==
2019-03-28
python创建数组
2019-03-28
什么是python标识符
2019-03-28
怎么能写好python三大语句
2019-03-28
python查看数组的属性
2019-03-28
白红宇的个人博客 - 记录点点滴滴的事 - 您是第 279616359 位访客
访问时间: 2023-12-11 20:46:22
访问IP: 3.239.2.192
Copyright © 2020 - 2023 blog.css8.cn 京ICP备2021015314号-1
手机版