JavaScript高效构建层级树形结构：O(n)算法解析

引言

在开发过程中，我们常需处理树形数据，例如组织架构、行政区划或生物分类等。此类数据的典型形态如下所示：

实际业务中，这类数据通常以扁平的对象数组形式存储，尤其在涉及一对多的父子节点关系时，这种存储方式更为常见：

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的父节点，同时是节点74的子节点。位于树顶端的节点被称为“根节点”。

思路

构建树形结构的核心步骤如下：

• 遍历包含所有数据的数组
• 定位当前元素的父元素
• 在父元素对象上添加指向当前子元素的引用
• 若元素无父元素，则将其判定为树的根节点

由于引用关系直接保存在对象树内部，我们得以在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 },

      ],

    },

  ],

};

原理

该方法的可行性基于JavaScript的对象引用机制。data数组中的每个元素均为内存中的对象引用，forEach循环中的el变量指向内存中的具体对象，parentEl同样引用了一个对象。

若内存中的某个对象引用了children数组，而这些子元素又各自引用自己的子元素数组，这种层级关联完全通过引用实现。

总结

对象引用是JavaScript的核心概念之一，需深入理解。透彻掌握此概念，既能规避复杂Bug，又能为看似棘手的问题提供简洁方案。

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