一维数组的数据结构,如下
const flatArray = [
{ id: 1, parent_id: null, name: ‘root1’ },
{ id: 2, parent_id: null, name: ‘root2’ },
{ id: 3, parent_id: 1, name: ‘child1’ },
{ id: 4, parent_id: 2, name: ‘child2’ },
{ id: 5, parent_id: 3, name: ‘grandchild1’ },
{ id: 6, parent_id: 4, name: ‘grandchild2’ },
];
方式1:使用map 结构,for循环查找,推荐,性能比较好
function arrayToTree(items) {
const map = new Map();
const result = [];
//创建映射,方便查找
items.forEach((item) => {
map.set(item.id, { ...item, children: [] });
});
//遍历全部节点,构建tree
items.forEach((item) => {
const node = map.get(item.id);
if (item.parent_id) {
//存在父级节点
const parent_node = map.get(item.id);
parent_node.children.push(node);
} else {
//根节点
result.push(node);
}
});
return result;
}
方式2:使用递归的方式,从根节点开始,查找每个节点的子节点
//递归,从根节点开始,查找每个节点的子节点
function arrayToTree2(items, parent_id) {
//第一次,全部根节点
return items
.filter((item) => {
return item.parent_id == parent_id;
})
.map((item) => {
//查找根节点下面的子节点
return {
...item,
children: arrayToTree2(items, item.id),
};
});
}
方式3:将上面两种方式结合起来,使用map做映射,同时使用递归(先筛选出根节点,再递归查找子节点)
function arrayToTree3(items) {
const map = new Map();
//创建映射,方便查找
items.forEach((item) => {
map.set(item.id, { ...item, children: [] });
});
//递归函数
function buildTree(node) {
items.filter((item) => {
if (item.parent_id == node.id) {
//是查找节点的子节点
const child = map.get(item.id);
//查找子节点的子节点
node.children.push(buildTree(child));
}
});
return node;
}
//先筛选出根节点数组,用递归查找根节点的子节点
return items.filter((item) => item.parent_id === null).map((item) => buildTree(map.get(item.id)));
}