扁平数组转树结构详解 🌲

1. 问题描述 ❓

在前端开发中，我们经常需要将从后端接收到的扁平数组转换成树状结构，这在处理菜单、组织架构等层级数据时非常常见。

示例数据

const list = [
    { id: 1, name: '司令', pid: 0 },
    { id: 2, name: '军长', pid: 1 },
    { id: 3, name: '副军长', pid: 1 },
    { id: 4, name: '旅长', pid: 3 },
    { id: 5, name: '团长', pid: 4 },
]

2. 解决方案 💡

2.1 双层循环方案

这是最直观的解决方案，但性能较差，时间复杂度 O(n²)。

function toTree(arr) {
  const resArr = []
  arr.forEach(item => {
    if (!item.pid) {
      resArr.push(item) // 添加根节点
    }
    // 查找当前项的子节点
    const children = arr.filter(i => i.pid === item.id)
    if (children.length) {
      item.children = children
    }
  })
  return resArr
}

2.2 递归方案 🔄

递归方案代码简洁，易于理解，适合处理层级较深的数据。

function toTree(arr, pid = 0) {
  return arr
    .filter(item => item.pid === pid)
    .map(item => ({
      ...item,
      children: toTree(arr, item.id)
    }))
    .map(item => item.children.length ? item : { ...item, children: undefined })
}

2.3 Map优化方案 ⚡

使用 Map 存储节点，只需遍历一次数组，时间复杂度 O(n)，是性能最优的解决方案。

function toTree(arr) {
  const map = new Map()
  const result = []

  // 初始化 map
  arr.forEach(item => {
    map.set(item.id, { ...item, children: [] })
  })

  // 构建树结构
  arr.forEach(item => {
    const node = map.get(item.id)
    if (item.pid === 0) {
      result.push(node)
    } else {
      const parent = map.get(item.pid)
      parent?.children.push(node)
    }
  })

  return result
}

3. 性能对比 📊

方案	时间复杂度	空间复杂度	适用场景
双层循环	O(n²)	O(1)	数据量小
递归	O(n·log n)	O(log n)	层级较深
Map	O(n)	O(n)	数据量大

4. 注意事项 ⚠️

1. 确保数据中不存在循环引用
2. 处理异常情况（如 pid 指向不存在的节点）
3. 大数据量场景建议使用 Map 方案
4. 注意内存泄漏问题

5. 实际应用示例 🌟

// 处理菜单数据
const menuList = [
  { id: 1, name: '首页', pid: 0 },
  { id: 2, name: '用户管理', pid: 0 },
  { id: 3, name: '用户列表', pid: 2 },
  { id: 4, name: '权限设置', pid: 2 }
]

const treeMenu = toTree(menuList)
console.log(JSON.stringify(treeMenu, null, 2))

6. 扩展功能 🔧

如果需要在转换过程中进行数据转换，可以使用以下增强版本：

function toTreeEnhanced(arr, options = {}) {
  const {
    idKey = 'id',
    pidKey = 'pid',
    childrenKey = 'children',
    transform = node => node
  } = options

  const map = new Map()
  const result = []

  arr.forEach(item => {
    map.set(item[idKey], { ...item, [childrenKey]: [] })
  })

  arr.forEach(item => {
    const node = transform(map.get(item[idKey]))
    if (item[pidKey] === 0) {
      result.push(node)
    } else {
      const parent = map.get(item[pidKey])
      parent?.[childrenKey].push(node)
    }
  })

  return result
}

7. 总结 📝

扁平数组转树是一个常见的前端数据处理需求，选择合适的方案需要考虑数据量、性能要求等因素。在实际项目中，建议使用 Map 方案，它能够满足大多数场景的需求。

希望这篇文章对你有所帮助！如果有任何问题，欢迎讨论交流~ 🎉