JavaScript平铺数组转树形结构的实现示例

后台丢来了1w条数据

千算万算，还是没有逃过，后台真的就上万条数据一次丢给前端了。好吧，好在还不是10w条。如下，后台返回的是这样的结构：

const flatArr = [  { id: '001', name: '节点1' },  { id: '0011', parentId: '001', name: '节点1-1' },  { id: '00111', parentId: '0011', name: '节点1-1-1' },  { id: '002', name: '节点2' },]

可以看到，这实际上就是一个平铺的数组，我们的需求是，要将这样数据渲染在Element-ui的级联选择器中，他接收的是如下的树形结构：

let options = [  {    value: 'zhinan',    label: '指南',    children: [      {        value: 'shejiyuanze',        label: '设计原则',        children: [          { value: 'yizhi', label: '一致' },          { value: 'fankui', label: '反馈'}        ],      }    ]  }]

好家伙，这不就是需要我将平铺数组转成树形结构嘛！
一顿操作猛如虎，二话不说写递归。

递归方式

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

非递归方式

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

总结

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

我们来看一个对比图：

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

最后，不得不感慨一下，通过这个对比，我们也可以明显的感受到算法的重要性，不同的实现方式，差异可以很大，这值得引起每一个 developer 对算法的重视！

到此这篇关于JavaScript平铺数组转树形结构的实现示例的文章就介绍到这了,更多相关JavaScript平铺数组转树形结构内容请搜索wanshiok.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持wanshiok.com！