一、 通用性树形结构数据转换

1. 数据示例

数据特点：无序、混乱，仅能看出id,pid有那么一个关联关系

[
    {id:5,pid:11,name:'创建管理员'},
    {id:6,pid:11,name:'管理员列表'},
    {id:7,pid:11,name:'修改管理员'},
    {id:9,pid:0,name:'角色管理'},
    {id:10,pid:9,name:'创建角色'},
    {id:8,pid:11,name:'删除管理员'},
    {id:11,pid:0,name:'管理员管理'},
    ...
]

2. 转换后的需求

写一个通用方法，将数据转换成树形结构，其中id、pid作为默认关联关系，children作为默认子节点，新增默认层级level从0开始，最后希望得到的效果：

[
  {
    id: 9,
    pid: 0,
    name: '角色管理',
    level: 0,
    children: [
      {
        id: 10,
        pid: 9,
        name: '创建角色',
        level: 1,
        children: []
      }
    ]
  },
  {
    id: 11,
    pid: 0,
    name: '管理员管理',
    level: 0,
    children: [
      // 包含多个 level=1 的子节点...
    ]
  }
]

3. 方法

以eggjs项目为例，将方法写在app/extend/context.js中，具体代码如下：

// app/extend/context.js
module.exports = {
  /**
   * 通用数据转树形结构方法
   * @param {Array} data - 原始数据列表
   * @param {Object} options - 配置项
   * @param {string} [options.idKey='id'] - 节点唯一标识字段名
   * @param {string} [options.pidKey='pid'] - 父节点标识字段名
   * @param {string} [options.childrenKey='children'] - 子节点属性名
   * @param {number} [options.initialLevel=0] - 初始层级
   * @returns {Array} 树形结构数据
   */
  treeify(data, {
    idKey = 'id',
    pidKey = 'pid',
    childrenKey = 'children',
    initialLevel = 0
  } = {}) {
    const nodeMap = new Map(); // 节点映射表
    const roots = [];          // 根节点集合

    // 创建节点副本并初始化子节点
    data.forEach(item => {
      const node = {
        ...item,
        [childrenKey]: [],
        level: initialLevel // 初始化层级，后续会修正
      };
      nodeMap.set(node[idKey], node);
    });

    // 构建父子关系
    data.forEach(item => {
      const node = nodeMap.get(item[idKey]);
      const parent = nodeMap.get(item[pidKey]);

      if (parent) {
        parent[childrenKey].push(node);
      } else {
        roots.push(node);
      }
    });

    // 使用队列进行层级计算（BFS）
    const queue = [];
    roots.forEach(root => {
      root.level = initialLevel; // 设置根节点层级
      queue.push(root);
    });

    while (queue.length > 0) {
      const node = queue.shift();
      node[childrenKey].forEach(child => {
        child.level = node.level + 1; // 子节点层级 = 父节点层级 + 1
        queue.push(child);
      });
    }

    return roots;
  }
};

4. 使用示例

// 在控制器中使用
async function index() {
  const { ctx } = this;
  const flatData = [
    { id: 5, pid: 11, name: '创建管理员' },
    { id: 6, pid: 11, name: '管理员列表' },
    { id: 11, pid: 0, name: '管理员管理' },
    // ...其他数据
  ];

  // 使用默认配置转换
  const treeData = ctx.treeify(flatData);
  
  // 自定义字段示例（假设字段不同）
  // const tree = ctx.treeify(data, {
  //   idKey: 'userId',
  //   pidKey: 'parentId',
  //   childrenKey: 'items',
  //   initialLevel: 1
  // });

  ctx.body = treeData;
}

5.方法特点

1. 高性能处理：使用 Map 结构实现 O(1) 查找复杂度，采用 BFS 广度优先遍历进行层级计算，避免递归栈溢出

2. 完全无副作用：创建数据副本进行操作，不会修改原始数据

3. 灵活配置：支持自定义字段映射，适应不同数据结构

4. 层级计算：自动计算每个节点的层级深度，从 0 开始递增

5. 循环检测：虽然未内置循环检测，但通过 Map 结构能快速定位父子关系问题

6. 输出结构示例

转换后的数据结构如下（包含 level 层级属性）：

[
  {
    id: 9,
    pid: 0,
    name: '角色管理',
    level: 0,
    children: [
      {
        id: 10,
        pid: 9,
        name: '创建角色',
        level: 1,
        children: []
      }
    ]
  },
  {
    id: 11,
    pid: 0,
    name: '管理员管理',
    level: 0,
    children: [
      // 包含多个 level=1 的子节点...
    ]
  }
]