export function list2Tree(data, parentId, children = "children", depth = 0) {
let res = [];
Array.isArray(data) &&
data.forEach(item => {
if (item.parentId === parentId) {
let itemChildren = list2Tree(data, item.id, children, depth + 1);
if (itemChildren.length) item[children] = itemChildren;
res.push({
...item,
depth
});
}
});
return res;
}
6000条数据时候需要 6350.08ms 多，有没有什么办法从算法层面优化一下的
这里用递归确实效率会有问题; 而且，你的代码对像不复用，很浪费
可以换个思路，两个循环解决树的问题。再加上遍历一次树算deep;
function array2Tree(arr) {
let map = new Map();
let _temp = arr.map((item) => {
_item = { ...item };
map.set(item.id, _item);
return _item;
});
for (let i = 0; i < _temp.length; ) {
let item = _temp[i];
let { id, parentId } = item;
let parent;
if (parentId && (parent = map.get(id))) {
parent.children ? parent.children.push(item) : (parent.children = [item]);
_temp.splice(i, 1);
continue;
}
i++;
}
function setDeep(arr, deep = 0) {
arr.map((item) => {
if (item.deep === undefined) {
item.deep = deep;
item.children && setDeep(item.children, deep + 1);
}
});
}
setDeep(_temp);
return _temp;
}
function getArr(max) {
let arr = [];
for (let i = 0; i < max; i++) {
arr.push({
id: `id_${i}`,
parentId:
Math.random() > 0.1 ? "id_" + ((Math.random() * max) >> 0) : undefined,
});
}
// return arr;
return arr.sort(() => (Math.random() > 0.5 ? 1 : -1));
}
var arr = getArr(5000);
// console.log(arr);
console.time("list2Tree");
var _arr = list2Tree(arr);
console.timeEnd("list2Tree");
console.log(_arr);
console.time("array2Tree");
var __arr = array2Tree(arr);
console.timeEnd("array2Tree");
console.log(__arr);
function toMap(arr) {
const result = arr.reduce((acc, current) => {
acc[current.id] = current
return acc
}, {})
return result
}
function formatListToTree(arr) {
const map = toMap(arr)
return arr.reduce((acc, current) => {
const { id, parentId } = current
if (map[parentId]) {
map[parentId].children = map[parentId].children || []
map[parentId].children.push(current)
} else {
acc.push(current)
}
return acc
}, [])
}
make tree by list2tree: 318.529ms
make tree by makeTree: 7.566msmake tree by list2tree: 17.498s
make tree by makeTree: 106.406msgenerate 用来生成数据list2tree 是题主的，用的递归makeTree 是我写的 ，用的 HashMap 缓存节点function generate(count = 6000) {
return Array.from(Array(count), (_, i) => ({
id: i + 1,
parentId: Math.floor(Math.random() * (i + 1))
}));
}
export function list2Tree(data, parentId, children = "children", depth = 0) {
let res = [];
Array.isArray(data) &&
data.forEach(item => {
if (item.parentId === parentId) {
let itemChildren = list2Tree(data, item.id, children, depth + 1);
if (itemChildren.length) item[children] = itemChildren;
res.push({
...item,
depth
});
}
});
return res;
}
function makeTree(data, children = "children") {
const root = { depth: -1, [children]: [] };
const nodeMap = {};
data.forEach(it => {
const { id, parentId } = it;
const parent = nodeMap[parentId] ?? root;
const node = { ...it, depth: parent.depth + 1 };
parent.children ??= [];
parent.children.push(node);
nodeMap[id] = node;
});
return root;
}
const data = generate(60000);
console.time("make tree by list2tree");
list2Tree(data, 0);
console.timeEnd("make tree by list2tree");
console.time("make tree by makeTree");
makeTree(data);
console.timeEnd("make tree by makeTree");
// console.log(JSON.stringify(tree1, null, 2));
// console.log(JSON.stringify(tree2, null, 2));6000 个节点一次性渲染出来……要不考虑一下动态加载（动态渲染），展开一层渲染一层
已参与了 SegmentFault 思否「问答」打卡，欢迎正在阅读的你也加入。
你的代码里最大的问题在于，每次都是循环全部数据，并在其中，找到指定pid的数据
这样循环的次数会非常非常多，所以代码的时间消耗会很大
比较好的方式，可以通过两次循环搞定
第一次循环的目的是构建主键和数据的映射
第二次根据pid，在映射中查找数据，找到则为子节点，未找到或pid为null/""，则为根节点
/**
* 树形数据生成配置
* */
interface GenerateTreeOption {
/**
* 返回对象中的父节点属性key，locales,null,"" 则不设置父节点属性
* */
parentNodeKey?: string;
/**
* 数组转map对象，生成树节点时，可同时，将列表数据放入map中
* */
mapCache?: any;
/**
* 对象id属性key 默认为 id
* */
idKey?: string;
/**
* 对象父节点id属性key，默认为 parent
* */
parentKey?: string;
/**
* 子节点属性key，默认为 children
* */
childrenKey?: string;
/**
* 结果写入对象
* */
result?: any[];
/**
* 遍历时，每个对象调用，设置对象使用
* */
loop?: (item: any) => void;
}
/**
* 生成树型数据
* @param data 列表数据
* @param config 生成配置
* */
function generateTree (data: any[], config?: GenerateTreeOption): any[] {
const parentNodeKey = config ? config.parentNodeKey : null
const result = config ? config.result || [] : []
const mapCache = config ? config.mapCache || {} : {}
const idKey = config ? config.idKey || 'id' : 'id'
const parentKey = config ? config.parentKey || 'parent' : 'parent'
const childrenKey = config ? config.childrenKey || 'children' : 'children'
const itemLoop = config ? config.loop || (() => undefined) : () => undefined
data.forEach((item) => {
mapCache[item[idKey]] = item
})
data.forEach((item) => {
itemLoop(item)
const cacheParentKey = item[parentKey]
if (cacheParentKey) {
if (mapCache[cacheParentKey]) {
if (!mapCache[cacheParentKey][childrenKey]) {
mapCache[cacheParentKey][childrenKey] = []
}
mapCache[cacheParentKey][childrenKey].push(item)
if (parentNodeKey) {
item[parentNodeKey] = mapCache[cacheParentKey]
}
} else { // 如果当前节点的父节点id未找到指定对象，则当前对象作为根节点的自己节点
result.push(item)
}
} else {
result.push(item)
}
})
return result
}
以下数据结构中，id 代表部门编号，name 是部门名称，parentId 是父部门编号，为 0 代表一级部门，现在要求实现一个 convert 方法，把原始 list 转换成树形结构，parentId 为多少就挂载在该 id 的属性 children 数组下，结构如下：
// 原始 list 如下
// 转换后的结果如下
转换方法如下：