如何基于预定义顶级父节点值生成任意层级嵌套的分类树结构

需求 #

需要从扁平的分类列表中生成对应的树形结构，支持无限层级嵌套。

输入数据 #

[
  { "parent_id": -1, "name": "Toothpaste", "id": 99 },
  {
    "parent_id": -1,
    "name": "Cake",
    "id": 3
  },
  {
    "parent_id": 3,
    "name": "Chocolate  Cake",
    "id": 4
  },
  {
    "parent_id": 3,
    "name": "Walnut Cake",
    "id": 5
  },
  {
    "parent_id": 4,
    "name": "Chocolate Cake mixin 1",
    "id": 6
  }
]

期望输出 #

[
  { "parent_id": -1, "name": "Toothpaste", "id": 99, "children": [] },
  {
    "parent_id": -1,
    "name": "Cake",
    "id": 3,
    "children":[
      {
        "parent_id": 3,
        "name": "Chocolate  Cake",
        "id": 4,
        "children":[
          {
            "parent_id": 4,
            "name": "Chocolate Cake mixin 1",
            "id": 6,
            "children": []
          }
        ]
      },
      {
        "parent_id": 3,
        "name": "Walnut Cake",
        "id": 5,
        "children": []
      }
    ]
  }
]

问题原因 #

原有代码仅将根节点（parent_id=-1）存入映射表并初始化children属性，二级及更深层级的节点没有存入映射表，所以处理三级节点时找不到对应的父节点，无法插入到二级节点的children数组中。

修复后代码 #

function getChildrenTree(childList){
  // 1、创建id到节点的映射表，给所有节点初始化children属性
  const nodeMap = {};
  childList.forEach(node => {
    // 浅拷贝节点避免修改原数据，不需要的话可以直接 node.children = [] 赋值
    nodeMap[node.id] = {...node, children: []};
  });
  // 2、遍历所有节点，将子节点挂到对应父节点的children下
  const rootNodes = [];
  childList.forEach(node => {
    const currentNode = nodeMap[node.id];
    if (node.parent_id === -1) {
      rootNodes.push(currentNode);
      return;
    }
    // 找到父节点，把当前节点插入父节点的children
    const parentNode = nodeMap[node.parent_id];
    if (parentNode) {
      parentNode.children.push(currentNode);
    }
  });
  return rootNodes;
}

// 测试
console.log(getChildrenTree([ 
  { "parent_id": -1, "name": "Toothpaste", "id": 99 },
  { "parent_id": -1, "name": "Cake", "id": 3 }, 
  { "parent_id": 3, "name": "Chocolate  Cake", "id": 4 }, 
  { "parent_id": 3, "name": "Walnut Cake", "id": 5 }, 
  { "parent_id": 4, "name": "Chocolate Cake mixin 1", "id": 6 } 
]))

该方案支持任意层级的嵌套，不管有多少级子分类都能正确生成树形结构。

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