对象数组列表转成树形结构（处理菜单）

问题

在前端开发中，后端经常返回扁平化的菜单数据列表，每个节点包含 id 和 parentId 字段。我们需要将这种扁平结构转换为树形结构，以便在页面中渲染多级菜单或树形组件。

例如，将以下扁平数据：

[
  { id: 1, name: '首页', parentId: null },
  { id: 2, name: '系统管理', parentId: null },
  { id: 3, name: '用户管理', parentId: 2 },
  { id: 4, name: '角色管理', parentId: 2 }
]

转换为树形结构：

[
  { id: 1, name: '首页', parentId: null, children: [] },
  { 
    id: 2, 
    name: '系统管理', 
    parentId: null, 
    children: [
      { id: 3, name: '用户管理', parentId: 2, children: [] },
      { id: 4, name: '角色管理', parentId: 2, children: [] }
    ] 
  }
]

解答

方法一：双层循环（简单直观）

/**
 * 将扁平数组转换为树形结构（双层循环）
 * @param {Array} list - 扁平数组
 * @param {string} idKey - id 字段名
 * @param {string} parentIdKey - 父 id 字段名
 * @param {string} childrenKey - 子节点字段名
 * @returns {Array} 树形结构数组
 */
function arrayToTree(list, idKey = 'id', parentIdKey = 'parentId', childrenKey = 'children') {
  // 深拷贝，避免修改原数组
  const data = JSON.parse(JSON.stringify(list));
  const result = [];
  
  // 遍历所有节点
  data.forEach(item => {
    // 为每个节点添加 children 属性
    item[childrenKey] = [];
    
    // 查找父节点
    const parent = data.find(node => node[idKey] === item[parentIdKey]);
    
    if (parent) {
      // 如果找到父节点，将当前节点添加到父节点的 children 中
      parent[childrenKey].push(item);
    } else {
      // 如果没有父节点，说明是根节点
      result.push(item);
    }
  });
  
  return result;
}

方法二：Map 优化（推荐，性能更好）

/**
 * 将扁平数组转换为树形结构（Map 优化版）
 * @param {Array} list - 扁平数组
 * @param {string} idKey - id 字段名
 * @param {string} parentIdKey - 父 id 字段名
 * @param {string} childrenKey - 子节点字段名
 * @returns {Array} 树形结构数组
 */
function arrayToTreeOptimized(list, idKey = 'id', parentIdKey = 'parentId', childrenKey = 'children') {
  const result = [];
  const map = new Map();
  
  // 第一次遍历：创建 Map，以 id 为 key
  list.forEach(item => {
    map.set(item[idKey], { ...item, [childrenKey]: [] });
  });
  
  // 第二次遍历：建立父子关系
  map.forEach(item => {
    const parentId = item[parentIdKey];
    
    if (parentId === null || parentId === undefined || parentId === 0) {
      // 根节点
      result.push(item);
    } else {
      // 找到父节点并添加到其 children 中
      const parent = map.get(parentId);
      if (parent) {
        parent[childrenKey].push(item);
      } else {
        // 如果找不到父节点，也作为根节点处理
        result.push(item);
      }
    }
  });
  
  return result;
}

方法三：递归实现

/**
 * 将扁平数组转换为树形结构（递归版）
 * @param {Array} list - 扁平数组
 * @param {*} parentId - 父节点 id
 * @param {string} idKey - id 字段名
 * @param {string} parentIdKey - 父 id 字段名
 * @param {string} childrenKey - 子节点字段名
 * @returns {Array} 树形结构数组
 */
function arrayToTreeRecursive(list, parentId = null, idKey = 'id', parentIdKey = 'parentId', childrenKey = 'children') {
  return list
    .filter(item => item[parentIdKey] === parentId)
    .map(item => ({
      ...item,
      [childrenKey]: arrayToTreeRecursive(list, item[idKey], idKey, parentIdKey, childrenKey)
    }));
}

使用示例

// 测试数据
const menuList = [
  { id: 1, name: '首页', parentId: null, path: '/home' },
  { id: 2, name: '系统管理', parentId: null, path: '/system' },
  { id: 3, name: '用户管理', parentId: 2, path: '/system/user' },
  { id: 4, name: '角色管理', parentId: 2, path: '/system/role' },
  { id: 5, name: '权限管理', parentId: 2, path: '/system/permission' },
  { id: 6, name: '用户列表', parentId: 3, path: '/system/user/list' },
  { id: 7, name: '用户详情', parentId: 3, path: '/system/user/detail' },
  { id: 8, name: '内容管理', parentId: null, path: '/content' },
  { id: 9, name: '文章管理', parentId: 8, path: '/content/article' }
];

// 方法一：双层循环
const tree1 = arrayToTree(menuList);
console.log('方法一结果：', JSON.stringify(tree1, null, 2));

// 方法二：Map 优化（推荐）
const tree2 = arrayToTreeOptimized(menuList);
console.log('方法二结果：', JSON.stringify(tree2, null, 2));

// 方法三：递归实现
const tree3 = arrayToTreeRecursive(menuList);
console.log('方法三结果：', JSON.stringify(tree3, null, 2));

// 自定义字段名
const customList = [
  { key: 1, title: '节点1', pid: 0 },
  { key: 2, title: '节点1-1', pid: 1 },
  { key: 3, title: '节点1-2', pid: 1 }
];

const customTree = arrayToTreeOptimized(customList, 'key', 'pid', 'items');
console.log('自定义字段结果：', JSON.stringify(customTree, null, 2));

关键点

• 时间复杂度对比：

  • 方法一（双层循环）：O(n²)，适合小数据量
  • 方法二（Map 优化）：O(n)，推荐使用，性能最优
  • 方法三（递归）：O(n²)，代码简洁但性能较差

• Map 优化的思想：通过 Map 数据结构将查找父节点的时间复杂度从 O(n) 降低到 O(1)

• 根节点判断：通常 parentId 为 null、undefined、0 或不存在时，视为根节点

• 深拷贝处理：避免修改原始数据，保证数据不可变性

• 灵活性设计：支持自定义字段名（id、parentId、children），适应不同的数据结构

• 边界情况处理：

  • 空数组返回空数组
  • 找不到父节点的孤立节点可作为根节点处理
  • 避免循环引用导致的死循环

• 实际应用场景：菜单渲染、组织架构、评论系统、文件目录等