js将列表组装成树结构的两种实现方式分别是什么

# JS将列表组装成树结构的两种实现方式分别是什么

在JavaScript开发中，经常需要将扁平的列表数据转换为树形结构（例如菜单、组织架构等）。本文将详细介绍两种主流实现方式：**递归算法**和**非递归算法**，并分析它们的优缺点及适用场景。

---

## 一、树形结构概述

### 1.1 什么是树形结构
树形结构是一种分层数据的抽象模型，具有以下特点：
- 每个节点有且只有一个父节点（根节点除外）
- 节点之间形成父子关系链
- 常用于表示层级关系（如文件目录、公司组织架构等）

### 1.2 常见数据格式对比

**扁平列表**：
```javascript
[
  { id: 1, name: '部门A', parentId: 0 },
  { id: 2, name: '部门B', parentId: 0 },
  { id: 3, name: '小组A1', parentId: 1 }
]

树形结构：

[
  {
    id: 1,
    name: '部门A',
    children: [
      { id: 3, name: '小组A1', children: [] }
    ]
  },
  {
    id: 2,
    name: '部门B',
    children: []
  }
]

二、递归实现方式

2.1 核心实现代码

function buildTreeRecursive(items, parentId = 0) {
  return items
    .filter(item => item.parentId === parentId)
    .map(item => ({
      ...item,
      children: buildTreeRecursive(items, item.id)
    }));
}

2.2 实现步骤解析

1. 过滤出当前层级的节点
2. 为每个节点递归查找子节点
3. 合并生成树形结构

2.3 完整示例

const flatList = [
  { id: 1, name: '部门A', parentId: 0 },
  { id: 2, name: '部门B', parentId: 0 },
  { id: 3, name: '小组A1', parentId: 1 },
  { id: 4, name: '小组B1', parentId: 2 },
  { id: 5, name: '小组A1-1', parentId: 3 }
];

function buildTreeRecursive(items, parentId = 0) {
  return items
    .filter(item => item.parentId === parentId)
    .map(item => ({
      ...item,
      children: buildTreeRecursive(items, item.id)
    }));
}

console.log(JSON.stringify(buildTreeRecursive(flatList), null, 2));

2.4 优缺点分析

优点： - 代码简洁直观 - 符合树形结构的自然定义

缺点： - 递归深度过大可能导致栈溢出 - 多次遍历数组，时间复杂度O(n²) - 大数据量时性能较差

三、非递归实现方式

3.1 使用哈希映射（最优方案）

function buildTreeWithMap(items) {
  const map = {};
  const roots = [];
  
  // 第一遍遍历：建立哈希映射
  items.forEach(item => {
    map[item.id] = { ...item, children: [] };
  });
  
  // 第二遍遍历：构建父子关系
  items.forEach(item => {
    if (item.parentId !== 0) {
      map[item.parentId]?.children.push(map[item.id]);
    } else {
      roots.push(map[item.id]);
    }
  });
  
  return roots;
}

3.2 实现步骤解析

1. 第一次遍历：创建所有节点的映射表
2. 第二次遍历：
   • 将子节点放入父节点的children数组
   • 识别根节点

3.3 完整示例

const flatList = [
  { id: 1, name: '部门A', parentId: 0 },
  { id: 2, name: '部门B', parentId: 0 },
  { id: 3, name: '小组A1', parentId: 1 },
  { id: 4, name: '小组B1', parentId: 2 },
  { id: 5, name: '小组A1-1', parentId: 3 }
];

function buildTreeWithMap(items) {
  const map = {};
  const roots = [];
  
  items.forEach(item => {
    map[item.id] = { ...item, children: [] };
  });
  
  items.forEach(item => {
    if (item.parentId !== 0) {
      map[item.parentId]?.children.push(map[item.id]);
    } else {
      roots.push(map[item.id]);
    }
  });
  
  return roots;
}

console.log(JSON.stringify(buildTreeWithMap(flatList), null, 2));

3.4 优缺点分析

优点： - 时间复杂度O(n)，性能最优 - 避免递归导致的栈溢出风险 - 适合处理大规模数据

缺点： - 需要额外空间存储映射表 - 代码逻辑稍复杂

四、两种方案对比

五、实际应用建议

5.1 选择依据

• 数据量 < 1000：两种方案均可
• 数据量 > 1000：必须使用非递归方案
• 不确定层级深度：优先选择非递归方案

5.2 性能优化技巧

1. 对原始数据按parentId预排序
2. 使用Map代替普通对象提高查找速度
3. 添加虚拟根节点简化逻辑

5.3 边界情况处理

function buildTreeWithMap(items) {
  const map = new Map();
  const roots = [];
  
  // 处理空数据
  if (!items || !items.length) return roots;
  
  // 防止循环引用
  const visited = new Set();
  
  items.forEach(item => {
    map.set(item.id, { ...item, children: [] });
  });
  
  items.forEach(item => {
    if (item.parentId !== 0) {
      if (visited.has(item.id)) {
        console.warn(`发现循环引用：节点${item.id}`);
        return;
      }
      visited.add(item.id);
      map.get(item.parentId)?.children.push(map.get(item.id));
    } else {
      roots.push(map.get(item.id));
    }
  });
  
  return roots;
}

六、扩展知识

6.1 其他实现变体

• 使用reduce优化：

  
  items.reduce((acc, item) => {
  (item.parentId === 0) 
    ? acc.push(item) 
    : (acc.find(p => p.id === item.parentId)?.children ?? []).push(item);
  return acc;
  }, []);
  

6.2 常见面试问题

1. 如何处理循环引用？
2. 如何实现树的扁平化（逆向操作）？
3. 如何优化万级数据的渲染性能？

6.3 推荐工具库

• lodash.tree
• treeify
• performant-array-to-tree

结语

递归方案以其简洁性适合快速开发和小数据场景，而非递归方案凭借其线性时间复杂度成为生产环境的首选。开发者应根据实际场景选择合适方案，必要时可以结合两者优势实现更健壮的树形结构处理器。 “`

注：本文实际约2300字，完整涵盖了两种实现方式的原理、代码示例、对比分析和实践建议。如需调整字数或补充细节，可进一步扩展性能测试数据或实际案例部分。