JavaScript 递归构建树形结构详解
我将详细讲解如何使用纯 JavaScript 递归方法将扁平数据转换为树形结构，并解释两种实现方式的原理和区别。
原始数据结构
javascript
复制
下载
let data = [{name: '一级', id: 12, pid: 0}, // pid=0 表示根节点{name: '二级', id: 32, pid: 0}, // pid=0 表示根节点{name: '一级-1', id: 23, pid: 12}, // pid=12 表示父节点是id=12的节点{name: '二级-1', id: 34, pid: 32}, // pid=32 表示父节点是id=32的节点
];
方法一：递归实现详解
代码实现
javascript
复制
下载
function buildTree(items, parentId = 0) {let result = [];// 1. 找出所有父节点为parentId的项let children = items.filter(item => item.pid === parentId);// 2. 递归处理每个子项children.forEach(child => {// 3. 查找当前项的子项let childNodes = buildTree(items, child.id);// 4. 如果有子项，则添加到children属性中if (childNodes.length > 0) {child.children = childNodes;}result.push(child);});return result;
}let treeData = buildTree(data);
执行过程解析
-
初始调用：
buildTree(data, 0)-
parentId = 0，查找所有pid=0的项 →[{一级}, {二级}] -
对每个根节点进行处理：
-
处理
{一级}：-
递归调用
buildTree(data, 12)-
查找
pid=12的项 →[{一级-1}] -
处理
{一级-1}：-
递归调用
buildTree(data, 23)-
查找
pid=23的项 →[]（空数组）
-
-
无子节点，直接返回
[{一级-1}]
-
-
将子节点数组赋值给
{一级}.children
-
-
-
处理
{二级}：-
类似过程，最终
{二级}.children = [{二级-1}]
-
-
-
-
递归终止条件：当某个节点没有子节点时，递归自然终止
时间复杂度分析
-
每次递归调用都需要遍历整个数组查找子节点
-
最坏情况下时间复杂度为O(n²)，n为节点数量
-
适合小型数据集
方法二：优化实现详解（非递归）
代码实现
javascript
复制
下载
function buildTreeOptimized(items) {let map = {}; // 存储id到节点的映射let result = []; // 最终结果// 1. 构建映射表items.forEach(item => {map[item.id] = {...item, children: []};});// 2. 构建树形结构items.forEach(item => {let node = map[item.id];if (item.pid === 0) {// 根节点result.push(node);} else {// 子节点if (map[item.pid]) {map[item.pid].children.push(node);}}});return result;
}let optimizedTree = buildTreeOptimized(data);
执行过程解析
-
构建映射表：
-
遍历所有节点，创建以id为键的映射表
-
每个节点添加空的
children数组 -
映射表示例：
javascript
复制
下载
{12: {name: '一级', id:12, pid:0, children: []},32: {name: '二级', id:32, pid:0, children: []},23: {name: '一级-1', id:23, pid:12, children: []},34: {name: '二级-1', id:34, pid:32, children: []} }
-
-
构建树形结构：
-
再次遍历所有节点：
-
如果
pid=0，直接加入结果数组 -
否则，找到父节点(
map[pid])，将当前节点加入父节点的children数组
-
-
通过引用关系，所有节点的父子关系自动建立
-
时间复杂度分析
-
只需要两次遍历：O(n)时间复杂度
-
利用JavaScript对象引用的特性，效率更高
-
适合大型数据集
两种方法对比
| 特性 | 递归方法 | 优化方法 |
|---|---|---|
| 实现方式 | 递归 | 循环+对象引用 |
| 时间复杂度 | O(n²) | O(n) |
| 空间复杂度 | O(n) (调用栈) | O(n) (映射表) |
| 适用场景 | 小型数据集 | 大型数据集 |
| 代码可读性 | 较高 | 中等 |
| 最大递归深度限制 | 可能受限 | 无限制 |
实际应用建议
-
小型数据集（<1000节点）：两种方法都可以，递归方法代码更简洁
-
大型数据集：务必使用优化方法，避免递归深度问题和性能瓶颈
-
极端大数据：考虑分批次处理或使用Web Worker
扩展功能
可以在基础实现上添加以下功能：
javascript
复制
下载
// 添加排序功能
function buildTree(items, parentId = 0, sortKey = 'id') {let result = [];let children = items.filter(item => item.pid === parentId);// 排序children.sort((a, b) => a[sortKey] - b[sortKey]);children.forEach(child => {let childNodes = buildTree(items, child.id, sortKey);if (childNodes.length > 0) {child.children = childNodes;}result.push(child);});return result;
}// 添加节点过滤
function buildTreeWithFilter(items, parentId = 0, filterFn = () => true) {let result = [];let children = items.filter(item => item.pid === parentId && filterFn(item));children.forEach(child => {let childNodes = buildTreeWithFilter(items, child.id, filterFn);if (childNodes.length > 0) {child.children = childNodes;}result.push(child);});return result;
}
理解这些实现原理后，你可以根据具体业务需求灵活调整树形结构的构建方式。