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

Pelagia ·

更新时间:2024-11-13

· 1895 次阅读

引言

思路

建立 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 },

],

},

],

};