• 售前

  • 售后

热门帖子
入门百科

JavaScript平铺数组转树形布局的实现示例

[复制链接]
墙和鸡蛋 显示全部楼层 发表于 2021-8-14 14:32:48 |阅读模式 打印 上一主题 下一主题
目次


  • 背景丢来了1w条数据
  • 递归方式
  • 非递归方式
  • 总结

背景丢来了1w条数据


千算万算,还是没有逃过,背景真的就上万条数据一次丢给前端了。好吧,好在还不是10w条。如下,背景返回的是这样的结构:
  1. const flatArr = [
  2.   { id: '001', name: '节点1' },
  3.   { id: '0011', parentId: '001', name: '节点1-1' },
  4.   { id: '00111', parentId: '0011', name: '节点1-1-1' },
  5.   { id: '002', name: '节点2' },
  6. ]
复制代码
可以看到,这实际上就是一个平铺的数组,我们的需求是,要将这样数据渲染在Element-ui的级联选择器中,他接收的是如下的树形结构:
  1. let options = [
  2.   {
  3.     value: 'zhinan',
  4.     label: '指南',
  5.     children: [
  6.       {
  7.         value: 'shejiyuanze',
  8.         label: '设计原则',
  9.         children: [
  10.           { value: 'yizhi', label: '一致' },
  11.           { value: 'fankui', label: '反馈'}
  12.         ],
  13.       }
  14.     ]
  15.   }
  16. ]
复制代码
好家伙,这不就是需要我将平铺数组转成树形结构嘛!
一顿操作猛如虎,二话不说写递归。


递归方式


大功告成,代码简洁,思绪清楚,一运行,what?页面卡死了,console.time() 盘算,大概使用了18s才盘算出我们需要的树形结构。
我反省了下我自己,这但是上万条数据,每次从下往上递归寻找父节点的子节点时都需要遍历一次数组,这当然耗时了!而且盘算时长已经明显导致了页面卡顿,此法肯定是不可取的,那么,有没有更好的方案呢?


非递归方式


这里奇妙的应用了对象生存的是引用的特点,每次将当前节点的 id 作为 key,生存对应节点的引用信息,遍历数组时,每次更新 objMap 的 children 信息,这样 objMap中生存了全部节点极其子节点,最重要的是,我们只需要遍历一遍数组,时间复杂度为O(n)。使用这种方式,盘算时长只需要60ms!


总结

       
  • 递归方式:每次递归寻找当前节点的子节点时都需要重新遍历一遍数组,时间复杂度为 O(nlogn)   
  • 非递归方式:从根节点往下寻找子节点,通过 Map 生存每个节点及其子节点的信息,子节点生存的是 Map 上的引用,每个节点的子节点都可以在 Map 中通过 id 找到,时间复杂度为 O(n)
我们来看一个对比图:

通过上面时间复杂度随数据量增大的走势可以看出,当数据越来越大时,递归算法的耗时将远宏大于非递归算法。因此,当数据量小时,使用递归算法有肯定的优势,但是当数据大到肯定的水平时,递归的做法的劣势将越来越明显,使用非递归算法会快很多!

末了,不得不感慨一下,通过这个对比,我们也可以明显的感受到算法的重要性,差别的实现方式,差异可以很大,这值得引起每一个 developer 对算法的器重!
到此这篇关于JavaScript平铺数组转树形结构的实现示例的文章就先容到这了,更多干系JavaScript平铺数组转树形结构内容请搜索脚本之家从前的文章或继续欣赏下面的干系文章盼望大家以后多多支持脚本之家!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作