JavaScript 构造树形结构的一种高效算法
<h3 id="引言">引言</h3><p>我们经常会碰到树形数据结构，比如组织层级、省市县或者动植物分类等等数据。下面是一个树形结构的例子：</p>
<p><img src="https://upload-images.jianshu.io/upload_images/1618526-afcc0d3ca19a31ce.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt="树形结构" loading="lazy"></p>
<p>在实际应用中，比较常见的做法是将这些信息存储为下面的结构，特别是当存在1对多的父/子节点关系时：</p>
<pre><code>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 },
];
</code></pre>
<p>那么，如何将这种对象数组格式转换为层级树的格式呢？其实，利用 JavaScript 对象引用的特性，实现起来会非常简单。它可以不用递归，在O(n)时间内完成。</p>
<h4 id="术语">术语</h4>
<p>为了表述方便，我们先来定义几个术语。我们把数组中的每个元素（也就树形图里的每个圆圈）称为<strong>“节点”</strong>。节点可以是多个节点的<strong>“父节点”</strong>，也可以是某个节点的<strong>“子节点”</strong>。上图中，<code>节点 86</code>是<code>节点 80</code> 和<code>节点 87</code>的“父节点”，<code>节点 86</code> 是<code>节点 74</code>的子节点。树的最顶部节点称为<strong>“根节点”</strong>。</p>
<h3 id="思路">思路</h3>
<p>为了构造树形结构，我们需要：</p>
<ol>
<li>遍历<code>data</code>数组</li>
<li>找到当前元素的父元素</li>
<li>在父元素对象上添加一个对该子元素的引用</li>
<li>元素如果没有父元素，那我们就认为它是树的根节点</li>
</ol>
<p>我们可以看到到，引用被保存在对象树下，这就是为什么我们可以在O(n)时间内完成这个任务！</p>
<h3 id="建立-id-数组索引映射关系">建立 ID-数组索引映射关系</h3>
<p>虽然不是必需的，但是这个映射关系可以帮我们快速找到元素的位置，方便找到到父元素的引用。</p>
<pre><code>const idMapping = data.reduce((acc, el, i) => {
acc = i;
return acc;
}, {});
</code></pre>
<p>映射结果如下，后面你会看到它的用处有多大：</p>
<pre><code>{
56: 0,
62: 7,
63: 4,
74: 2,
76: 3,
80: 5,
81: 1,
86: 8,
87: 6,
};
</code></pre>
<h3 id="构造树形结构">构造树形结构</h3>
<p>现在我们开始构造这个树形结构。遍历这个对象数组，找到每个元素的父元素对象，然后添加对这个元素的引用。现在你应该看到了，这个 <code>idMapping</code>用来定位元素的位置多么方便（常数时间）。</p>
<pre><code>let root;
data.forEach(el => {
// 判断根节点
if (el.parentId === null) {
root = el;
return;
}
// 用映射表找到父元素
const parentEl = data];
// 把当前元素添加到父元素的`children`数组中
parentEl.children = [...(parentEl.children || []), el];
});
</code></pre>
<p>完事！用<code>console.log</code> 打印 <code>root</code> 看下：</p>
<pre><code>console.log(root);
</code></pre>
<pre><code>{
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 },
],
},
],
};
</code></pre>
<h3 id="原理">原理</h3>
<p>为什么可以这么做呢？这是因为，<code>data</code> 数组里的每个元素都是内存里的一个对象引用， <code>forEach</code>循环里的<code>el</code>变量其实是指向内存里的一个对象，<code>parentEl</code>也引用了一个对象。</p>
<p>如果内存中的一个对象引用了一个 children 数组，这些子元素同样可以引用自己的子元素数组，这些关联关系都是通过引用完成的。</p>
<h3 id="总结">总结</h3>
<p>对象引用是 JavaScript 中最基本的概念之一，需要更多的学习和理解。真正理解这个概念后，既可以避免棘手的 bug，又可以为看似复杂的问题提供相对简单的解决方案。<br>
</p>
<p>欢迎关注微信公众号：1024译站<br>
<img src="https://img2018.cnblogs.com/blog/121167/202001/121167-20200102101135714-1518087941.jpg" alt="微信公众号：1024译站" loading="lazy"></p><br><br>
来源：https://www.cnblogs.com/lzkwin/p/12143458.html
頁:
[1]