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

用户时到运转 發表於 2021-2-4 15:54:00

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

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

</div>
 
出处：https://www.cnblogs.com/lzkwin/p/12143458.html
 

</div>
<div id="MySignature" role="contentinfo">
<div class="div_masklayer" id="div_masklayer"></div>
<div class="div_popup" id="Div_popup">
<div style="float:left;width:50%">
<img class="img_zfb" id="img_zfb" src="https://images.cnblogs.com/cnblogs_com/mq0036/508398/o_12.png" />
</div>
<div style="float:left;width:50%">
<img class="img_zfb" id="img_zfb" src="https://images.cnblogs.com/cnblogs_com/mq0036/508398/o_200921131119o_12.png">
</div>
您的资助是我最大的动力！ 金额随意,欢迎来赏！ 
付款后有任何问题请给我留言。
</div>

<div class="autograph">
 如果，您认为阅读这篇博客让您有些收获，不妨点击一下右下角的【推荐】按钮。 
 如果，您希望更容易地发现我的新博客，不妨点击一下绿色通道的【关注我】。(●'◡'●)
因为，我的写作热情也离不开您的肯定与支持，感谢您的阅读，我是【Jack_孟】！
<div class="blogds">
 如果对你有所帮助，赞助一杯咖啡！打

            
 付款后有任何问题请给我留言!!!
</div>
本文来自博客园，作者：jack_Meng，转载请注明原文链接：https://www.cnblogs.com/mq0036/p/14373063.html
【免责声明】本文来自源于网络，如涉及版权或侵权问题，请及时联系我们，我们将第一时间删除或更改！
</div> 
来源：https://www.cnblogs.com/mq0036/p/14373063.html

頁: [1]

琼殿技术论坛's Archiver

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