使用对象引用在 JavaScript 中构建深度树
介绍
一些简要术语
总体方法论
制作 ID 到数组位置的映射
创建树
为什么这种方法有效
结论
介绍
假设我们有一个树状数据结构。它可以是组织层级结构、项目分解结构、动植物分类结构等等。以下是一个树状结构的示例：
在应用程序中，通常会以以下格式存储这些信息，尤其是在存在一对多父子节点关系的情况下：
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) 时间内完成这项任务！
制作 ID 到数组位置的映射
虽然并非完全必要，但我们先来创建一个元素 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,
};
创建树
我们准备创建树状图！让我们遍历对象，并为每个元素分配指向其父元素的引用。注意我们使用 `or`idMapping来帮助我们找到父元素。
let root;
data.forEach(el => {
// Handle the root element
if (el.parentId === null) {
root = el;
return;
}
// Use our mapping to locate the parent element in our data array
const parentEl = data[idMapping[el.parentId]];
// Add our current el to its parent's `children` array
parentEl.children = [...(parentEl.children || []), el];
});
就这样！我们可以console.log从树根上确认：
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 },
],
},
],
};
为什么这种方法有效
要理解为什么这种方法有效，最好的方法是记住数据数组中的每个元素都是对内存中一个对象的引用，循环el中的变量forEach引用内存中的一个对象（数据数组元素引用的内存中的对应对象），并且parentEl它也引用内存中的一个对象（同样，是数据数组中引用的对象之一）。
如果内存中的一个对象拥有一个子对象引用数组，那么这些子对象也可以拥有自己不断增长的子对象引用数组。由于这一切都是通过引用传递的，因此在修改某个子对象时，无需告知其父对象任何信息。
结论
对象引用是 JavaScript 的基础概念之一，我认为它值得我们深入学习和理解。真正掌握这个概念，既能帮助我们避免棘手的 bug，也能为看似复杂的问题提供相对简单的解决方案。
文章来源：https://dev.to/nas5w/building-deep-trees-in-javascript-using-object-references-4565