不用递归生成无限层级的树
发布于 3 年前 作者 niexq 3752 次浏览 来自 分享

偶然间,在技术群里聊到生成无限层级树的老话题,故此记录下,n年前一次生成无限层级树的解决方案

业务场景

处理国家行政区域的树,省市区,最小颗粒到医院,后端回包平铺数据大小1M多,前端处理数据后再渲染,卡顿明显

后端返回的数据结构

[
    {
      "id": 1,
      "name": "中华人民共和国",
      "parentId": 0,
    },
    {
      "id": 1001,
      "name": "浙江省",
      "parentId": 1,
    },
    {
      "id": 2001,
      "name": "杭州市",
      "parentId": 1001,
    },
    {
      "id": 3001,
      "name": "西湖区",
      "parentId": 2001,
    },
    {
      "id": 4001,
      "name": "杭州市第一人民医院",
      "parentId": 3001,
    },
    // 其他略
]

第一版:递归处理树

常规处理方式

// 略,网上一抓一把

时间复杂度:

第二版:非递归处理树

改进版处理方式

const buildTree = (itemArray, { id = 'id', parentId = 'parentId', children = 'children', topLevelId = '0' } = {}) => {
  return itemArray.filter((item) => {
    // 挂载子级
    item[children] = itemArray.filter((child) => String(item[id]) === String(child[parentId]));
    // 返回顶层数据
    return String(item[parentId]) === topLevelId;
  });
};

时间复杂度:O(n^2)

第三版:非递归处理树

import { groupBy } from 'lodash';

const buildTree = (itemArray, { id = 'id', parentId = 'parentId', children = 'children', topLevelId = '0' } = {}) => {
  const parentObj = groupBy(itemArray, parentId)
  return itemArray.filter((item) => {
    // 挂载子级
    item[children] = parentObj[item[id]];
    // 返回顶层数据
    return String(item[parentId]) === topLevelId;
  });
};

时间复杂度:O(2n)

最终版:非递归处理树(根据评论区大佬们评论补充)

const buildTree = (itemArray, { id = 'id', parentId = 'parentId', children = 'children', topLevelId = '0' } = {}) => {
  const parentMap = new Map(); // 临时存储所有父级
  const topLevelResult = [];   // 存储顶层结果
  for(let item of itemArray) {
    if(!parentMap.has(item[id])) {
      item[children] = []
    } else {
      item[children] = parentMap.get(item[id])[children];
    }
	
    parentMap.set(item.id, item)
	
    if(!parentMap.has(item[parentId])) {
      parentMap.set(item[parentId], {
        [children]: []
      });
    }
    parentMap.get(item[parentId])[children].push(item)
    if (String(item[parentId]) === String(topLevelId)) {
      topLevelResult.push(item)
    }
  }
  return topLevelResult;
}

时间复杂度:O(n)

下篇分享不用递归无限层级树取交集

此篇笔记 收录 个人笔记,感谢阅读,欢迎star

15 回复

第二版 O(n^2) 最终版 O(2n)

感觉可以搞到 O(n): 见3楼

O(2n)版,手写未测试 ~

let r = [],  m = new Map();
for(let item of itemArray) {
	item['children'] = [];
	m.set(item.id, item);
}
for(let item of itemArray) {
	if(m.has(item.parentId))
	  m.get(item.parentId)['children'].push(item);
	else
	  r.push(item);
}
return r;

O(n)

function fn(arr) {
  var home = {}
  var dad
  for(let item of arr) {
    if(home[item.id])
      item.children = home[item.id].children
    else
      item.children = []
	
    home[item.id] = item
	
    if(!home[item.pid])
      home[item.pid] = {
        children: []
      }
    home[item.pid].children.push(item)
  }
  return home[0]
}

@daGaiGuanYu 你这个貌似有两个缺陷:

  1. 对顺序有强制要求,父节点必须在子节点前面。
  2. 不支持多个顶层节点

测试样例

递归 x 823,463 ops/sec ±0.74% (65 runs sampled)
最终 x 380,053 ops/sec ±1.11% (65 runs sampled)
Fastest is 递归

我看你是对递归有什么误解

@myy

  • 父节点可以在子节点后面,你可以试试(如果有条件检验,应尽量少用“貌似”,何况检验又不麻烦)
  • 多个顶层节点的情况,只不过需要一个“虚拟顶点”,然后函数最后 return 虚拟顶点.children

@netwjx @myy @daGaiGuanYu 大佬们,时间复杂度,专业,厉害,学习了🚀

@aov2005 这个数据量级测出来的结果意义不大,至少得用kb级的,我们公司加上末级医院,回包有1M多😁

@daGaiGuanYu 大哥,我都不用试,你仔细看过你的代码没有? 如果某个 父节点 出现在数组最后一个呢??

@myy 可是我试了呀兄弟

@daGaiGuanYu 结果打印为underfined, home的结果为C15192D0-099F-46CB-8368-DBE02F25080C.png,是不是没有自测

@TimLiu1 我代码里没有 parentId 只有 pid

🏆🏆🏆 🚀🚀🚀 👍👍👍 学习了,根据大佬们提供的代码及思路,已整理更新最终版本(已测)

@niexq 哈哈哈,现在都要在最后加上“括号已测”了吗

@myy 我看到后立马就想到了这种写法。。。

回到顶部