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

引言

我们经常会碰到树形数据结构，比如组织层级、省市县或者动植物分类等等数据。下面是一个树形结构的例子：

在实际应用中，比较常见的做法是将这些信息存储为下面的结构，特别是当存在1对多的父/子节点关系时：

const data = [
  { id: 56, parentId: 62 },
  { id: 81, parentId: 80 },
  { id: 74, parentId: null },
  { id: 76, parentId: 80 },
  { id: 63, parentId: 62 },
  { id: 80, parentId: 86 },
  { id: 87, parentId: 86 },
  { id: 62, parentId: 74 },
  { id: 86, parentId: 74 },
];

那么，如何将这种对象数组格式转换为层级树的格式呢？其实，利用 JavaScript 对象引用的特性，实现起来会非常简单。它可以不用递归，在O(n)时间内完成。

术语

为了表述方便，我们先来定义几个术语。我们把数组中的每个元素（也就树形图里的每个圆圈）称为“节点”。节点可以是多个节点的“父节点”，也可以是某个节点的“子节点”。上图中，节点 86是节点 80和节点 87的“父节点”，节点 86是节点 74的子节点。树的最顶部节点称为“根节点”。

思路

为了构造树形结构，我们需要：

  • 遍历data数组
  • 找到当前元素的父元素
  • 在父元素对象上添加一个对该子元素的引用
  • 元素如果没有父元素，那我们就认为它是树的根节点

我们可以看到到，引用被保存在对象树下，这就是为什么我们可以在O(n)时间内完成这个任务！

建立 ID-数组索引映射关系

虽然不是必需的，但是这个映射关系可以帮我们快速找到元素的位置，方便找到到父元素的引用。

const idMapping = data.reduce((acc, el, i) => {
  acc[el.id] = i;
  return acc;
}, {});

映射结果如下，后面你会看到它的用处有多大：

{

  56: 0,

  62: 7,

  63: 4,

  74: 2,

  76: 3,

  80: 5,

  81: 1,

  86: 8,

  87: 6,

};

构造树形结构

现在我们开始构造这个树形结构。遍历这个对象数组，找到每个元素的父元素对象，然后添加对这个元素的引用。现在你应该看到了，这个idMapping用来定位元素的位置多么方便（常数时间）。

let root;
data.forEach(el => {
  // 判断根节点
  if (el.parentId === null) {
    root = el;
    return;
  }
  // 用映射表找到父元素
  const parentEl = data[idMapping[el.parentId]];
  // 把当前元素添加到父元素的`children`数组中
  parentEl.children = [...(parentEl.children || []), el];
});

完事！用console.log打印root看下：

console.log(root);

{

  id: 74,

  parentId: null,

  children: [

    {

      id: 62,

      parentId: 74,

      children: [{ id: 56, parentId: 62 }, { id: 63, parentId: 62 }],

    },

    {

      id: 86,

      parentId: 74,

      children: [

        {

          id: 80,

          parentId: 86,

          children: [{ id: 81, parentId: 80 }, { id: 76, parentId: 80 }],

        },

        { id: 87, parentId: 86 },

      ],

    },

  ],

};

原理

为什么可以这么做呢？这是因为，data数组里的每个元素都是内存里的一个对象引用，forEach循环里的el变量其实是指向内存里的一个对象，parentEl也引用了一个对象。

如果内存中的一个对象引用了一个 children 数组，这些子元素同样可以引用自己的子元素数组，这些关联关系都是通过引用完成的。

总结

对象引用是 JavaScript 中最基本的概念之一，需要更多的学习和理解。真正理解这个概念后，既可以避免棘手的 bug，又可以为看似复杂的问题提供相对简单的解决方案。

以上就是浅谈JavaScript构造树形结构的一种高效算法的详细内容，更多关于JavaScript构造树形结构的算法的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • JS数组Reduce方法功能与用法实例详解

    本文实例讲述了JS数组Reduce方法功能与用法.分享给大家供大家参考,具体如下: 概述 一直以来都在函数式编程的大门之外徘徊,要入门的话首先得熟悉各种高阶函数,数组的reduce方法就是其中之一. reduce方法将会对数组元素从左到右依次执行reducer函数,然后返回一个累计的值.举个形象的例子:你要组装一台电脑,买了主板.CPU.显卡.内存.硬盘.电源...这些零件是组装电脑的必要条件. 装的过程可以简单概括为拆掉每个零件的包装,再装到一起.类比一下reduce函数就可以明白了,那些零件

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

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

  • js实现无限层级树形数据结构(创新算法)

    由于做项目的需要,把一个线性数组转成树形数组,在网上查了很多文章,觉得他们写的太复杂了,于是自己写了一个,在折腾了一下午终于把它写出来啦(激动.gif),用两个filter过滤器就搞定了,代码简洁明了,数据结构小白都能看懂. js代码:把扁平数据转成树形数据 function setTreeData(source){ let cloneData = JSON.parse(JSON.stringify(source)) // 对源数据深度克隆 return cloneData.filter(fat

  • js中的reduce()函数讲解

    js中的reduce()函数讲解

    定义: reduce() 方法接收一个函数作为累加器,数组中的每个值(从左到右)开始缩减,最终计算为一个值.对空数组是不会执行回调函数的. 案例 1.数组求和 // 1.数组求和 var arr = [1,5,8,6,15,78,65,25,48,55] var sum = arr.reduce(function(total,currentValue){ return total+currentValue; }); console.log(sum);//306 var eachSum = 0;

  • Javascript数组方法reduce的妙用之处分享

    前言 Javascript数组方法中,相比map.filter.forEach等常用的迭代方法,reduce常常被我们所忽略,今天一起来探究一下reduce在我们实战开发当中,能有哪些妙用之处,下面从reduce语法开始介绍. 语法 array.reduce(function(accumulator, arrayElement, currentIndex, arr), initialValue) 若传入初始值,accumulator首次迭代就是初始值,否则就是数组的第一个元素:后续迭代中将是上一

  • JS使用reduce()方法处理树形结构数据

    JS使用reduce()方法处理树形结构数据

    定义 reduce() 方法对数组中的每个元素执行一个由您提供的reducer函数(升序执行),将其结果汇总为单个返回值. reduce() 与forEach().map().filter()这些方法一样,也会对数组中的每一项进行遍历,但是reduce() 可以将遍历的前一个数组项产生的结果与当前遍历项进行运算. 语法 array.reduce(function(prev, cur, index, array){ ... }, init); 回调函数中的参数: prev 必需.表示调用回调时的返

  • JS数组方法reduce的用法实例分析

    本文实例讲述了JS数组方法reduce的用法.分享给大家供大家参考,具体如下: 数组方法 reduce 用来迭代一个数组,并且把它累积到一个值中. 使用 reduce 方法时,你要传入一个回调函数,这个回调函数的参数是一个 累加器 (比如例子中的 previousVal) 和当前值 (currentVal). reduce 方法有一个可选的第二参数,它可以被用来设置累加器的初始值.如果没有在这定义初始值,那么初始值将变成数组中的第一项,而 currentVal 将从数组的第二项开始. 使用 re

  • JavaScript中reduce()的5个基本用法示例

    前言 reduce()方法可以搞定的东西,for循环,或者forEach方法有时候也可以搞定,那为啥要用reduce()?这个问题,之前我也想过,要说原因还真找不到,唯一能找到的是:通往成功的道路有很多,但是总有一条路是最捷径的,亦或许reduce()逼格更高... 语法 arr.reduce(callback,[initialValue]) reduce()方法对数组中的每一个元素执行一个reducer函数(由你提供),从而得到一个单一的输出值. reduce() 方法将一个数组中的所有元素还

  • JS数组reduce()方法原理及使用技巧解析

    1.语法 arr.reduce(callback,[initialValue]) reduce 为数组中的每一个元素依次执行回调函数,不包括数组中被删除或从未被赋值的元素,接受四个参数:初始值(或者上一次回调函数的返回值),当前元素值,当前索引,调用 reduce 的数组. callback (执行数组中每个值的函数,包含四个参数) 1.previousValue (上一次调用回调返回的值,或者是提供的初始值(initialValue)) 2.currentValue (数组中当前被处理的元素)

  • 浅谈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 }, {

  • 浅谈MYSQL中树形结构表3种设计优劣分析与分享

    浅谈MYSQL中树形结构表3种设计优劣分析与分享

    目录 简介 问题 设计1:邻接表 表设计 SQL示例 设计2:路径枚举 表设计 SQL示例 设计3:闭包表 表设计 SQL示例 结合使用 表设计 总结 简介 在开发中经常遇到树形结构的场景,本文将以部门表为例对比几种设计的优缺点: 问题 需求背景:根据部门检索人员, 问题:选择一个顶级部门情况下,跨级展示当前部门以及子部门下的所有人员,表怎么设计更合理 ? 递归吗 ?递归可以解决,但是势必消耗性能 设计1:邻接表 注:(常见父Id设计) 表设计 CREATE TABLE `dept_info01

  • 浅谈JavaScript中的分支结构

    浅谈JavaScript中的分支结构

    说到JavaScript中的分支结构,我们就不得不提到流程控制这个词,我们所有的程序都是由数据和算法组成的. 程序=数据+算法 通常我们所说的算法都可以通过"顺序","分支","循环"三种结构来组合完成. 在ECMA中规定了一些语句(也称为流程控制语句,分支结构语句),从本质上来说,这些语句定义了ECMAScript中的主要语法,语句通常使用一个或者多个关键字来完成给定任务. 1.1 if 语句 if 语句 - 只有当指定条件为 true 时,使

  • 浅谈JavaScript 浏览器对象

    浅谈JavaScript 浏览器对象

    window window对象不但充当全局作用域,而且表示浏览器窗口. window对象有innerWidth和innerHeight属性,可以获取浏览器窗口的内部宽度和高度.内部宽高是指除去菜单栏.工具栏.边框等占位元素后,用于显示网页的净宽高.还有一个outerWidth和outerHeight属性,可以获取浏览器窗口的整个宽高. 补充: 网页可见区域宽:document.body.clientWidth 网页可见区域高:document.body.clientHeight 网页可见区域宽:

  • 浅谈JavaScript工具链不完全指南

    浅谈JavaScript工具链不完全指南

    目录 概述 静态类型检查 代码风格检查(Linter) 包管理器 模块加载器 打包工具 任务管理工具(Task Runner) 转译器 构建工具 调试工具 Node 进程管理器 项目脚手架 概述 在 JavaScript 语言日渐强大的同时,与其配套的开发工具也蓬勃发展.现在的 Web 前端项目,早已不是写几个 HTML 页面,加点 CSS 和 JS 就完事了.随便一个实用的项目,可能都需要用到一些框架和第三方库,以及相应的脚手架.依赖包管理.预编译.构建打包.压缩合并等等工具.纯手工完成这些任

  • 浅谈JavaScript中面向对象的的深拷贝和浅拷贝

    理解深拷贝和浅拷贝之前需要弄懂一些基础概念,内存中存储的变量类型分为值类型和引用类型. 1.值类型赋值的存储特点, 将变量内的数据全部拷贝一份, 存储给新的变量. 例如:var num = 123 :var num1=num; 表示变量中存储的数字是 123.然后将数据拷贝一份,就是将 123 拷贝一份. 那么内存中有 2 个 数组;将拷贝数据赋值给 num2,其特点是在内存中有两个数据副本.这可以理解为浅拷贝. 2.引用类型的赋值. var o={name:'张三'}: var obj=o;

  • 浅谈JavaScript 函数参数传递到底是值传递还是引用传递

    在传统的观念里,都认为JavaScript函数传递的是引用传递(也称之为指针传递),也有人认为是值传递和引用传递都具备.那么JS的参数传递到底是怎么回事呢?事实上以下的演示也完全可以用于Java 首先来一个比较简单的,基本类型的传递: function add(num){ num+=10; return num; } num=10; alert(add(num)); aelrt(num); //输出20,10 对于这里的输出20,10,按照JS的官方解释就是在基本类型参数传递的时候,做了一件复制

  • 浅谈javascript运算符——条件,逗号,赋值,()和void运算符

    前面的话 javascript中运算符总共有46个,除了前面已经介绍过的算术运算符.关系运算符.位运算符.逻辑运算符之外,还有很多运算符.本文将介绍条件运算符.逗号运算符.赋值运算符.()和void运算符 条件运算符 条件运算符是javascript中唯一的一个三元运算符(三个操作数),有时直接称做'三元运算符'.通常这个运算符写成'?:',当然在代码中往往不会这么简写,因为这个运算符拥有三个操作数,第一个操作数在'?'之前,第二个操作数在'?'和':'之间,第三个操作数在':'之后 varia

  • 浅谈javascript中的constructor

    constructor,构造函数,对这个名字,我们都不陌生,constructor始终指向创建当前对象的构造函数. 这里有一点需要注意的是,每个函数都有一个prototype属性,这个prototype的constructor指向这个函数,这个时候我们修改这个函数的prototype时,就发生了意外.如 function Person(name,age){ this.name = name; this.age = age; } Person.prototype.getAge = function

  • 浅谈javascript中的Function和Arguments

    javascript的Function 属性: 1.Arguments对象 2.caller 对调用单前函数的Function的引用,如果是顶层代码调用,  则返回null(firefox返回undefined).  注:只有在代码执行时才有意义 3.length 声明函数是指定的命名参数的个数(函数定义是,定义参数的个数) 4.prototype 一个对象,用于构造函数,这个对象定义的属性和方法  由构造函数创建的所有对象共享. 方法: applay() --> applay(this,[])

随机推荐