JS构造树形结构的思路、原理及过程是什么

Admin 2022-07-19 群英技术资讯 466 次浏览

今天这篇给大家分享的知识是“JS构造树形结构的思路、原理及过程是什么”,小编觉得挺不错的,对大家学习或是工作可能会有所帮助,对此分享发大家做个参考,希望这篇“JS构造树形结构的思路、原理及过程是什么”文章能帮助大家解决问题。

引言

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

在实际应用中,比较常见的做法是将这些信息存储为下面的结构,特别是当存在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,又可以为看似复杂的问题提供相对简单的解决方案。


现在大家对于JS构造树形结构的思路、原理及过程是什么的内容应该都有一定的认识了吧,希望这篇能对大家有所帮助。最后,想要了解更多,欢迎关注群英网络,群英网络将为大家推送更多相关的文章。 群英智防CDN,智能加速解决方案

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:mmqy2019@163.com进行举报,并提供相关证据,查实之后,将立刻删除涉嫌侵权内容。

猜你喜欢

成为群英会员,开启智能安全云计算之旅

立即注册
专业资深工程师驻守
7X24小时快速响应
一站式无忧技术支持
免费备案服务
免费拨打  400-678-4567
免费拨打  400-678-4567 免费拨打 400-678-4567 或 0668-2555555
在线客服
微信公众号
返回顶部
返回顶部 返回顶部
在线客服
在线客服