数组转树与树转数组
<h1 data-id="heading-0">🧑💻 写在开头</h1><p>点赞 + 收藏 === 学会🤣🤣🤣</p>
<h2 data-id="heading-0">扁平数组转树形结构 (Array To Tree)</h2>
<h3 data-id="heading-1">核心痛点</h3>
<p>处理“数组转树”最直观的思路是使用递归配合双重循环：遍历数组中的每一项，再次遍历数组寻找其子节点。</p>
<p>这种做法的时间复杂度为 O(n2)O(n2)当数据量 nn较小时（如几十条菜单），性能损耗尚可忽略。但当数据量达到数千条（如组织架构、行政区划）时，计算次数呈指数级增长，会导致浏览器主线程阻塞，页面卡顿。</p>
<h3 data-id="heading-2">解决方案：Map 映射法</h3>
<p>为了解决性能瓶颈，我们需要将时间复杂度降低至 O(n)O(n)核心思路利用 JavaScript 对象是**引用类型（Reference Type）**的特性，结合 空间换时间 的策略：</p>
<ol>
<li>
<p>第一次遍历：构建一个以 id 为键，节点对象为值的 Map（或对象字典）。这一步可以让我们在 O(1)O(1)的时间内获取任意节点的引用。</p>
</li>
<li>
<p>第二次遍历：通过 parentId 直接从 Map 中查找父节点引用，并将当前节点挂载到父节点的 children 属性下。</p>
</li>
</ol>
<h3 data-id="heading-3">代码实现</h3>
<div class="cnblogs_Highlighter">
<pre class="brush:csharp;gutter:true;">/**
* 扁平数组转树形结构 - O(n)
* @param {Array} items 扁平数组
* @param {Object} config 配置项，兼容不同的字段名
* @returns {Array} 树形结构
*/
function arrayToTree(items, config = {}) {
const { id = 'id', pid = 'parentId', children = 'children' } = config;
const result = [];
const itemMap = new Map();
// 1. 初始化 Map，并处理数据深浅拷贝问题
// 这一步确保了后续操作的是新对象，不污染原数据
for (const item of items) {
// 扩展运算符实现浅拷贝，初始化 children 数组
itemMap.set(item, { ...item, : [] });
}
// 2. 二次遍历，利用引用地址组装树
for (const item of items) {
const idValue = item;
const pidValue = item;
const treeItem = itemMap.get(idValue);
// 尝试获取父节点引用
const parent = itemMap.get(pidValue);
if (parent) {
// 如果父节点存在，利用引用特性，直接 push 到父节点的 children 中
// 此时 Map 中的父节点对象和 result 中的对象指向同一块内存地址
parent.push(treeItem);
} else {
// 如果找不到父节点，说明是根节点（Root）
// 注意：这里兼容了 parentId 为 null、0 或不存在的情况
result.push(treeItem);
}
}
return result;
}</pre>
</div>
<h3 data-id="heading-4">深度解析</h3>
<blockquote>
<p>该算法仅对数组进行了两次遍历，总操作次数为 2n2n因此时间复杂度稳定在 O(n)O(n)关键在于 parent.push(treeItem) 这一步。在 JavaScript 堆内存中，treeItem 和 parent 都是独立的对象。当我们把 treeItem 放入 parent 的数组时，实际上是存储了 treeItem 的内存地址。</p>
</blockquote>
<div>
<div>
<p>无论层级多深，我们都无需递归查找，因为 Map 充当了“索引表”，让我们能直接定位到任何节点的内存地址并进行挂载。</p>
<hr>
<h2 data-id="heading-5">树形结构转扁平数组 (Tree To Array)</h2>
<h3 data-id="heading-6">核心场景</h3>
<ul>
<li><strong>全量搜索</strong>：在树中查找符合条件的节点。</li>
<li><strong>表格渲染</strong>：将树形数据展示为平铺的表格。</li>
<li><strong>数据清洗</strong>：去除树结构中的空 children 或无效字段。</li>
</ul>
<h3 data-id="heading-7">解决方案：迭代法 (Iterative Approach)</h3>
<p>虽然递归（Recursion）写法代码简洁，但在极端层级深度下（如深度超过 10000 层），递归调用栈（Call Stack）可能溢出。</p>
<p>为了代码的健壮性，推荐使用<strong>广度优先遍历 (BFS)</strong> 或 <strong>深度优先遍历 (DFS)</strong> 的迭代写法。这里展示基于栈（Stack）的 DFS 写法，因为它逻辑清晰且性能优异。</p>
<h3 data-id="heading-8">代码实现</h3>
</div>
<div class="cnblogs_Highlighter">
<pre class="brush:csharp;gutter:true;">/**
* 树形结构转扁平数组 - 迭代法 (DFS)
* @param {Array} tree 树形数据
* @returns {Array} 扁平数组
*/
function treeToArray(tree) {
const result = [];
// 使用扩展运算符浅拷贝，避免修改原数组引用
// stack 作为任务栈，模拟递归调用的过程
const stack = [...tree];
while (stack.length > 0) {
// 弹出栈顶元素（后进先出，模拟深度优先）
const node = stack.pop();
// 解构分离 children 和其他属性
// 目的：扁平化后的节点通常不需要 children 字段，且防止循环引用
const { children, ...rest } = node;
// 将处理后的纯净节点推入结果集
result.push(rest);
// 如果存在子节点，将它们推入栈中待后续处理
if (children && children.length > 0) {
// 注意：为了保证顺序（如果需要），可以反转 children 后入栈，或者使用 shift() 做 BFS
// 这里使用 push + pop 实现 DFS
stack.push(...children);
}
}
return result;
}</pre>
</div>
<div>
<div>
<h3 data-id="heading-9">注意点：Immutability (不可变性)</h3>
<p>在上述代码中，const { children, ...rest } = node 是至关重要的一步。</p>
<ol>
<li><strong>断开引用</strong>：我们不希望扁平化后的对象依然保留庞大的 children 树状结构，这会造成不必要的内存占用。</li>
<li><strong>数据安全</strong>：如果直接 delete node.children，会修改原始传入的树数据。在 Vue/React 等响应式框架中，这种副作用（Side Effect）会导致不可预知的视图更新异常。通过解构赋值产生新对象，保证了函数的纯度（Pure Function）。</li>
</ol><hr>
<h2 data-id="heading-10">总结</h2>
<p>在前端工程化开发中，处理复杂数据结构是检验工程师基本功的试金石。</p>
<ol>
<li>
<p><strong>数组转树</strong>：核心在于利用 <strong>Hash Map</strong> 建立索引，将 O(n2)O(n2)的嵌套查找优化为 O(n)O(n)的引用挂载。这是典型的“空间换时间”算法思想。</p>
</li>
<li><strong>树转数组</strong>：核心在于利用 <strong>栈（Stack）</strong> 或 <strong>队列（Queue）</strong> 将递归逻辑转化为迭代循环，避免栈溢出风险，并严格遵守数据不可变原则。</li>
</ol></div>
</div>
</div>
<div>
<div>
<p>理解内存引用（Memory Reference）和算法复杂度，是写出高性能、强健壮性代码的关键。</p>
</div>
<div>
<div>
<h3 id="tid-D8HBxE">如果对您有所帮助，欢迎您点个关注，我会定时更新技术文档，大家一起讨论学习，一起进步。</h3>
</div>
<p><em><img src="https://img2024.cnblogs.com/blog/2149129/202501/2149129-20250122165814748-630765389.png" alt="" loading="lazy"></em></p>
</div>
</div><br><br>
来源：https://www.cnblogs.com/smileZAZ/p/19637193
頁:
[1]