# javascript list转tree，怎么优化

• 368
``````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 多，有没有什么办法从算法层面优化一下的

5 个回答

// 原始 list 如下

``````let list =[
{id:1,name:'部门A',parentId:0},
{id:2,name:'部门B',parentId:0},
{id:3,name:'部门C',parentId:1},
{id:4,name:'部门D',parentId:1},
{id:5,name:'部门E',parentId:2},
{id:6,name:'部门F',parentId:3},
{id:7,name:'部门G',parentId:2},
{id:8,name:'部门H',parentId:4}
];
const result = convert(list, ...);``````

// 转换后的结果如下

``````let result = [
{
id: 1,
name: '部门A',
parentId: 0,
children: [
{
id: 3,
name: '部门C',
parentId: 1,
children: [
{
id: 6,
name: '部门F',
parentId: 3
}, {
id: 16,
name: '部门L',
parentId: 3
}
]
},
{
id: 4,
name: '部门D',
parentId: 1,
children: [
{
id: 8,
name: '部门H',
parentId: 4
}
]
}
]
},
···
];``````

``````function convert(list) {
const res = []
const map = list.reduce((res, v) => (res[v.id] = v, res), {})
for (const item of list) {
if (item.parentId === 0) {
res.push(item)
continue
}
if (item.parentId in map) {
const parent = map[item.parentId]
parent.children = parent.children || []
parent.children.push(item)
}
}
return res
}``````

``````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(parentId))) {
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
}, [])
}``````

## 先看结果

### 6,000 条

``````make tree by list2tree: 318.529ms
make tree by makeTree: 7.566ms``````

### 60,000 条

``````make tree by list2tree: 17.498s
make tree by makeTree: 106.406ms``````

## 再看代码

• `generate` 用来生成数据
• `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 个节点一次性渲染出来……要不考虑一下动态加载（动态渲染），展开一层渲染一层

``````/**
* 树形数据生成配置
* */
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
}``````

###### 你尚未登录，登录后可以
• 和开发者交流问题的细节
• 关注并接收问题和回答的更新提醒
• 参与内容的编辑和改进，让解决方法与时俱进