扁平数据列表生成级联树

开发过程中，无论是前端还是后端，经常会有这样的需求：

拿分级菜单来举例，我们存于数据库的数据是扁平的，通过 pid 标识对于类目的父级类目，查出来的结果一般是这个样子：

[
  { "id": 1, "pid": 0, "name": "一级菜单1" },
  { "id": 2, "pid": 0, "name": "一级菜单2" },
  { "id": 3, "pid": 0, "name": "一级菜单3" },
  { "id": 4, "pid": 1, "name": "二级菜单11" },
  { "id": 5, "pid": 1, "name": "二级菜单12" },
  { "id": 6, "pid": 2, "name": "二级菜单21" },
  { "id": 7, "pid": 3, "name": "二级菜单31" },
  { "id": 8, "pid": 4, "name": "三级菜单111" }
]

而前端的级联组件往往需要的是能直观体现父子关系的嵌套结构：

[
  {
    "id": 1,
    "pid": 0,
    "name": "一级菜单1",
    "children": [
      {
        "id": 4,
        "pid": 1,
        "name": "二级菜单11",
        "children": [{ "id": 8, "pid": 4, "name": "三级菜单111" }]
      },
      { "id": 5, "pid": 1, "name": "二级菜单12" }
    ]
  },
  {
    "id": 2,
    "pid": 0,
    "name": "一级菜单2",
    "children": [{ "id": 6, "pid": 2, "name": "二级菜单21" }]
  },
  {
    "id": 3,
    "pid": 0,
    "name": "一级菜单3",
    "children": [{ "id": 7, "pid": 3, "name": "二级菜单31" }]
  }
]

问题抽象来讲，就是如何从扁平的数据结构得到关联的级联数据列表呢？

乍一看，这问题很简单嘛！

再一看，看文章的小伙伴有一半会阵亡，写不出来！

试试？

var arr = [
  { id: 1, pid: 0, name: '一级菜单1' },
  { id: 2, pid: 0, name: '一级菜单2' },
  { id: 3, pid: 0, name: '一级菜单3' },
  { id: 4, pid: 1, name: '二级菜单11' },
  { id: 5, pid: 1, name: '二级菜单12' },
  { id: 6, pid: 2, name: '二级菜单21' },
  { id: 7, pid: 3, name: '二级菜单31' },
  { id: 8, pid: 4, name: '三级菜单111' },
];

function genTree() {
  // C 位留给你花10分钟表演，不然你可能没明白问题在哪里
}

console.log(genTree(arr));

既然都用到了内存引用，那么思路来了，而且可以做到 O(n)：

function genTree(arr) {
  // 以id为key，存一份map数据，可以以O(1)的效率查找到指定id的item
  const map = arr.reduce((acc, cur) => ({ ...acc, [cur.id]: cur }), {});
  const tree = [];

  arr.forEach(item => {
    // 有pid，为非顶级item
    const parentItem = map[item.pid];
    if (parentItem) {
      // 给其父级item添加children属性
      if (!parentItem.children) parentItem.children = [];
      // 将自身以引用形式放入父级item的children
      parentItem.children.push(item);
    } else {
      // 是顶级item则放入返回列表
      tree.push(item);
    }
  });
  // perfect !!!
  return tree;
}

你学会了么？下次碰到该类问题会解决了么？

nitroge / memories

扁平数据列表生成级联树 #9