不用递归生成无限层级的树

不用递归生成无限层级的树

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

业务场景

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

后端返回的数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
[
{
"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,
},
// 其他略
]

第一版:递归处理树

常规处理方式

1
// 略,网上一抓一把

第二版:非递归处理树

改进版处理方式

1
2
3
4
5
6
7
8
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)

第三版:非递归处理树

1
2
3
4
5
6
7
8
9
10
11
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)

最终版:非递归处理树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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)

0%