如何将含pid的JSON数组转换为带children的树形结构？

问题场景 #

我们有一个包含id和pid（父节点id）的JSON数组，比如：

const data1 = [ { id: 1, pid: 0 }, { id: 2, pid: 1 }, { id: 3, pid: 2 } ]

需要将其转换为带有children属性的树形结构，目标结果如下：

[ { id: 1, pid: 0, children: [ { id: 2, pid: 1, children: [ { id: 3, pid: 2 } ] } ] } ]

方案一：哈希表映射法（稳定高效） #

这是一种通用且高效的实现方式，时间复杂度为O(n)，核心是用哈希表快速定位父节点，推荐使用：

const data = [ { id: 1, pid: 0 }, { id: 4, pid: 3 }, { id: 2, pid: 1 }, { id: 3, pid: 2 } ];
function toTree (data) {
  // 先清除所有item可能存在的children属性，避免旧数据干扰
  data.forEach(function(item) { delete item.children; });
  // 建立id到item的映射表，方便O(1)时间查找父节点
  const map = {};
  data.forEach(function(item) { map[item.id] = item; });
  const result = [];
  data.forEach(function(item) {
    // 找到当前item的父节点
    const parent = map[item.pid];
    if(parent) {
      // 如果父节点还没有children数组，就先初始化，再把当前item加进去
      (parent.children || (parent.children = [])).push(item);
    } else {
      // 如果没有父节点，说明是根节点，加入结果数组
      result.push(item);
    }
  });
  return result;
}
console.log(JSON.stringify(toTree(data)));

思路拆解：

• 第一步清除children是为了避免原数组中可能存在的旧children属性影响最终结果；
• 哈希表map的作用是让我们可以通过pid直接找到对应的父节点对象，不用每次遍历数组查找，大大提升处理效率；
• 遍历每个元素时，要么把它挂到父节点的children数组里，要么作为根节点存入结果集合。

方案二：分组关联法（思路参考，存在bug） #

下面是另一种实现思路，先按pid和id排序，再按pid分组，最后通过reduce关联父子节点，但当前版本存在bug（比如同一父节点下有多个子节点时无法正确处理），仅供思路参考：

const data1 = [ { id: 1, pid: 0 }, { id: 4, pid: 2 }, { id: 5, pid: 1 }, { id: 3, pid: 2 }, { id: 2, pid: 1 } ];
function toTree (data){
  // 先按pid排序，pid相同则按id排序
  data.sort((a, b) => (a.pid - b.pid === 0) ? a.id - b.id : a.pid - b.pid);
  // 按pid分组，key是pid，value是对应子节点数组
  const map = {}
  data.forEach(item => (map[item.pid] || (map[item.pid] = []) ).push(item))
  const mapArr = Object.values(map)
  // 通过reduce关联父子节点（此处存在bug，仅适用于每个父节点只有一个子节点的场景）
  mapArr.reduce((a, b, index, arr) => {
    if ( a[0].id === b[0].pid) {
      a[0].children = b
    }
    return b;
  })
  return mapArr[0]
}
console.log(JSON.stringify(toTree(data1)));

注意：这个方法的bug在于，当同一父节点下有多个子节点，或者分组后的数组顺序不符合预期时，无法正确构建children数组，需要进一步调整逻辑才能稳定使用。

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