JS构造树形结构的思路、原理及过程是什么
Admin 2022-07-19 群英技术资讯 466 次浏览
我们经常会碰到树形数据结构,比如组织层级、省市县或者动植物分类等等数据。下面是一个树形结构的例子:
在实际应用中,比较常见的做法是将这些信息存储为下面的结构,特别是当存在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的子节点。树的最顶部节点称为“根节点”。
为了构造树形结构,我们需要:
我们可以看到到,引用被保存在对象树下,这就是为什么我们可以在O(n)时间内完成这个任务!
虽然不是必需的,但是这个映射关系可以帮我们快速找到元素的位置,方便找到到父元素的引用。
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,又可以为看似复杂的问题提供相对简单的解决方案。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:mmqy2019@163.com进行举报,并提供相关证据,查实之后,将立刻删除涉嫌侵权内容。
猜你喜欢
JavaScript实现简单的音乐播放器 本文实例为大家分享了JavaScript实现简单音乐播放器的具体代码,供大家参考,具体内容如下 主要功能:快进.快退.暂停.上下一首.禁音.鼠标控制音量.自动下一首.显示歌名 <html> <head> @*不提供音频*@ <meta name="viewport" content="width=device-width" /> <title>ceshi14</title> ...
最近小编在做一个项目,其中涉及到一个模块关于星座查询功能,即在文本框中输入一个生日值,点击按钮可以得到对应的星座,怎么实现这个需求呢?下面小编通过示例代码给大家介绍下,需要的朋友参考下吧
javascript求pi五次方的方法:1、利用Math对象的“PI”属性获取pi(圆周率)的值;2、使用Math对象的pow()方法计算并返回pi五次方的值,语法“Math.pow(Math.PI,5)”。
这篇文章主要为大家详细介绍了JS实现圆形进度条拖拽滑动,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
这篇文章主要介绍了vue 设置背景颜色及透明度的操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教
成为群英会员,开启智能安全云计算之旅
立即注册Copyright © QY Network Company Ltd. All Rights Reserved. 2003-2020 群英 版权所有
增值电信经营许可证 : B1.B2-20140078 粤ICP备09006778号 域名注册商资质 粤 D3.1-20240008