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

目录
  • 后台丢来了1w条数据
  • 递归方式
  • 非递归方式
  • 总结

后台丢来了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平铺数组转树形结构内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 一篇文章带你入门Java Script

    目录 概述 特点 和Java的区别 弱类型语言 强类型语言 书写位置 数组 函数 JS中的自定义对象(扩展内容) Object形式的自定义对象 JS中的事件 常用的事件: 动态注册基本步骤: DOM模型 总结 概述 JavaScript是目前web开发中不可缺少的脚本语言,js不需要编译即可运行,运行在客户端,需要通过浏览器来解析执行JavaScript代码. JS组成部分: 组成部分 作用 ECMA Script 构成了JS核心的语法基础 BOM Browser Object Model 浏览

  • JavaScript实现网页贪吃蛇游戏

    JavaScript实现网页贪吃蛇游戏

    本文实例为大家分享了JavaScript实现网页贪吃蛇游戏的具体代码,供大家参考,具体内容如下 <!DOCTYPE html> <html> <head><title>贪吃蛇</title> </head> <body> <canvas id="canvas" width="400" height="400"></canvas> <s

  • JavaScript实现大文件分片上传处理

    很多时候我们在处理文件上传时,如视频文件,小则几十M,大则 1G+,以一般的HTTP请求发送数据的方式的话,会遇到的问题: 1.文件过大,超出服务端的请求大小限制: 2.请求时间过长,请求超时: 3.传输中断,必须重新上传导致前功尽弃 这些问题很影响用户的体验感,所以下面介绍一种基于原生JavaScript进行文件分片处理上传的方案,具体实现过程如下: 1.通过dom获取文件对象,并且对文件进行MD5加密(文件内容+文件标题形式),采用SparkMD5进行文件加密: 2.进行分片设置,文件Fil

  • javaScript实现网页版的弹球游戏

    javaScript实现网页版的弹球游戏

    利用javeScript对象以及方法实现的网页弹球游戏,供大家参考,具体内容如下 <!DOCTYPE html> <html> <head> <tilie>呼呼哈嘿的网页弹球</title> </head> <body> <canvas id="canvas"width="400"height="400"></canvas> <scr

  • JavaScript数据类型转换实例(其他类型转字符串、数值型、布尔类型)

    前言 什么是数据类型转换? 使用表单.prompt 获取过来的数据默认类型是字符串类型的,此时就不能直接进行加减法运算,而需要转换变量的数据类型. 通俗来说,数据类型转换就是将一种数据类型转换成另外一种数据类型. 在平常代码的使用中,我们偶尔会遇到需要进行数据类型转换的时候,比如将数值型转换为字符串,或者将null/undefined转换为布尔类型等等,这篇文章我们主要讲以下三种类型的转换: 其他类型转为字符串 其他类型转为数值型 其他类型转为布尔类型 其他类型转为字符串: 有三种方法 //第一

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

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

    目录 后台丢来了1w条数据 递归方式 非递归方式 总结 后台丢来了1w条数据 千算万算,还是没有逃过,后台真的就上万条数据一次丢给前端了.好吧,好在还不是10w条.如下,后台返回的是这样的结构: const flatArr = [ { id: '001', name: '节点1' }, { id: '0011', parentId: '001', name: '节点1-1' }, { id: '00111', parentId: '0011', name: '节点1-1-1' }, { id:

  • 如何将JavaScript将数组转为树形结构

    1.需求 后台给了一个这样的数据让咱前端去转换为树形结构(没有重复数据).不多说,先来看看给了一个怎样的数组数据,转换为怎样的树形结构. 服务器传过来的数组 const arr = [ [ {"deptId":"D019", "deptName":"销售部"}, {"deptId":"D019101", "deptName":"华北销售中心"} ]

  • JS前端二维数组生成树形结构示例详解

    目录 问题描述 实现步骤 完整代码 问题描述 前端在构建国家的省市区结构时,接口返回的不是树形结构,这个时候就需要我们进行转化.以下数据为例 [ [ { "districtId": 1586533852834, "parentCode": "000", "nodeCode": "000001", "name": "浙江省", "districtType&qu

  • AngularJS实现树形结构(ztree)菜单示例代码

    AngularJS实现树形结构(ztree)菜单示例代码

    树形结构 树形结构有多种形式和实现方式,zTree可以说得上是一种比较简洁又美观的且实现起来也相对简单.zTree是一个依靠jQuery实现的多功能"树插件".它最大的优点是配置灵活,只要id与pid的值相同就可形成一个简单的父子结构.再加上免费开源,使用zTree的人越来越多. 效果图如下 首先你需要知道AngularJS的双向数据绑定是什么才可以更好的理解下面的代码,想了很久才想出用下面的代码来实现左侧菜单树形结构 要实现上面的功能你需要操作如下步骤: 在HTML标签内添加ng-a

  • PostgreSQL树形结构的递归查询示例

    背景 处理不确定深度的层级结构,比如组织机构,一个常用的设计是在一张表里面保存 ID 和 Parent_ID ,并且通过自联结的办法构造一颗树.这种方式对写数据的过程很友好,但是查询过程就变得相对复杂.在不引入MPTT模型的前提下,必须通过递归算法来查询某个节点和下级子节点. Oracle提供的connect by扩展语法,简单好用.但是其他的RDBMS就没这么人性化了(或者我不知道).最近在项目中使用PostgreSQL来查询树形数据,记录一下. 构造样本数据 drop table if ex

  • Java实现平铺列表(List)互转树形(Tree)结构

    Java实现平铺列表(List)互转树形(Tree)结构

    目录 需求 实践List to Tree 递归实现 非递归实现 实例 实践Tree to List 递归实现 非递归实现 实例 总结 很多时候为满足前后端交互的数据结构需求,往往我们需要把平铺的List数据与Tree型层级数据结构进行互转,这篇文章提供详实的递归和非递归的方式去实现数据结构转换,为了使用到lambda的特性,Java version >=8. 需求 我们从基础设施层获取了一个列表数据,列表其中的对象结构如下,注意约束条件如果没有pid,默认为null. @Getter @Sett

  • Vue组件模板形式实现对象数组数据循环为树形结构(实例代码)

    Vue组件模板形式实现对象数组数据循环为树形结构(实例代码)

    数据结构为数组中包含对象--树形结构,用Vue组件的写法实现以下的效果: 树形列表,缩进显示层级,第5级数据加底色,数据样式显色,点击展开折叠数据.本文为用Vue实现方式,另有一篇为用knockout.js的实现方法. html代码 <div id="table-component-div"> <table-component v-for="item in data1" v-bind:list="item"></ta

  • javascript将扁平的数据转为树形结构的高效率算法

    当我们需要将一个一维数组转换成一个多层结构的时候,最简单但是最慢的就是多个for循环嵌套,但是这样做有一些缺点,那就是效率太低.而且有多少层就需要嵌套几个for循环,不好用. 我实现了用O(n)级算法将 一个扁平的数组即一维数组代表的菜单结构转换成一个多层级的菜单结构. 一位数组中每一个元素必须要包含以下属性: 拥有一个唯一的id 拥有一个parent_id, 这个id指向它父级的id 其他则为每一个元素中的一些信息,我这里是菜单,就有菜单的名称和url信息. 注: 在层级结构中,第一层的par

  • 浅谈JavaScript构造树形结构的一种高效算法

    浅谈JavaScript构造树形结构的一种高效算法

    引言 我们经常会碰到树形数据结构,比如组织层级.省市县或者动植物分类等等数据.下面是一个树形结构的例子: 在实际应用中,比较常见的做法是将这些信息存储为下面的结构,特别是当存在1对多的父/子节点关系时: const data = [ { id: 56, parentId: 62 }, { id: 81, parentId: 80 }, { id: 74, parentId: null }, { id: 76, parentId: 80 }, { id: 63, parentId: 62 }, {

  • Javascript中扁平化数据结构与JSON树形结构转换详解

    目录 一. 先说简单的树形结构数扁平化处理 二. 再讲将扁平化数据结构转JSON树状形结构 扩充一个知识点:for in 与 for of 的区别 : 总结 不废话,直接开干 一. 先说简单的树形结构数扁平化处理 上思想: 思想:采用递归,每个对象都有childern,只要有children属性提取出来将其放在空数组中 然后将对象的其他属性解构出来,最后将数组合并 上代码: //已知JSON树状形结构的数据data let data = [ {id:1,title:'标题1',parent_id

随机推荐