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

2024-04-02 19:04:59 773人浏览泡泡鱼

摘要

目录引言思路建立 ID-数组索引映射关系构造树形结构原理总结引言我们经常会碰到树形数据结构，比如组织层级、省市县或者动植物分类等等数据。下面是一个树形结构的例子：在实际应用中，

引言

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

在实际应用中，比较常见的做法是将这些信息存储为下面的结构，特别是当存在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 },

],

},

],

};