如何从带id、parentid的扁平数组生成树形结构？

问题背景 #

现有包含id、parentid关联关系的扁平数组，示例如下：

let e = [
  {
    "id": 1,
    "descr": "Те",
    "moddate": "2023-02-09T13:37:46.366961",
    "isgroup": true
  },  
  {
    "id": 2,
    "descr": "Те",
    "moddate": "2023-02-09T13:37:46.366961",
    "parentid": 1
  },
  {
    "id": 3,
    "descr": "Те",
    "moddate": "2023-02-09T13:37:46.366961",
    "parentid": 2
  }
];

原代码仅能处理一级子节点，无法生成多层嵌套的树形结构，期望输出如下：

let res = [
  {
        "id": 1,
        "descr": "Те",
        "moddate": "2023-02-09T13:37:46.366961",
        "isgroup": true,
        "children": [{
          "id": 2,
          "descr": "Те",
          "moddate": "2023-02-09T13:37:46.366961",
          "parentid": 1,
          "children": [{
            "id": 3,
            "descr": "Те",
            "moddate": "2023-02-09T13:37:46.366961",
            "parentid": 2
          }]
        }]
   }
];

解决方案 #

方法1：递归挂载子节点 #

通过递归函数，为每个节点查找并挂载其所有层级的子节点：

function buildTree(arr) {
  // 筛选根节点并初始化children属性
  const roots = arr.filter(item => !item?.parentid).map(item => ({...item, children: []}));

  // 递归函数：给指定父节点挂载所有子节点
  function attachChildren(parentNode) {
    const children = arr.filter(item => item.parentid === parentNode.id);
    parentNode.children = children.map(child => {
      const childNode = {...child, children: []};
      // 递归处理子节点的后代
      attachChildren(childNode);
      return childNode;
    });
  }

  // 遍历根节点，触发递归
  roots.forEach(root => attachChildren(root));
  return roots;
}

// 调用示例
const tree = buildTree(e);
console.log(tree);

方法2：Map映射优化（推荐） #

对于数据量较大的场景，使用Map存储节点映射，通过O(1)查找效率快速构建树形结构，无需递归：

function buildTree(arr) {
  // 构建id到节点的映射，每个节点初始化children为空数组
  const nodeMap = new Map();
  arr.forEach(item => {
    nodeMap.set(item.id, {...item, children: []});
  });

  const roots = [];

  arr.forEach(item => {
    const currentNode = nodeMap.get(item.id);
    if (!item.parentid) {
      // 根节点加入结果集合
      roots.push(currentNode);
    } else {
      // 找到父节点并挂载当前节点
      const parentNode = nodeMap.get(item.parentid);
      if (parentNode) {
        parentNode.children.push(currentNode);
      }
    }
  });

  return roots;
}

// 调用示例
const tree = buildTree(e);
console.log(tree);

方案说明 #

• 方法1逻辑直观，适合小规模数据；方法2时间复杂度为O(n)，性能更优，适合处理大量数据。
• 两种方案都会给每个节点添加children属性，无后代时children为空数组，保证结构统一。

内容的提问来源于stack exchange，提问作者user13314476