将平铺数组转为树状结构
面试了十几个高级前端,竟然连(扁平数据结构转Tree)都写不出来 - 掘金
递归调用实现
时间复杂度 O(n^2) ,空间复杂度:O(n^2) 缺点: 不适合大规模数据
javascript
const nodes = [
{ id: 1, name: "Node 1", parentId: null },
{ id: 2, name: "Node 2", parentId: 1 },
{ id: 3, name: "Node 3", parentId: 1 },
{ id: 4, name: "Node 4", parentId: 2 },
{ id: 5, name: "Node 5", parentId: 2 },
{ id: 6, name: "Node 6", parentId: null },
];
// 定义一个函数,用于将数组转换为树状结构
function arrayToTree(array, parentId = null) {
const tree = [];
// 如果当前节点的父节点ID等于给定的父节点ID
array.forEach((item) => {
if (item.parentId === parentId) {
// 递归查找当前节点的子节点,并将子节点添加到当前节点的children属性中
// 这里是递归调用,构建子树 将子树赋值给当前节点的 children 属性
item.children = arrayToTree(array, item.id);
// 将当前节点添加到树中
tree.push(item);
}
});
return tree;
}
// 1 6
// 2 3
// 4 5
const res = arrayToTree(nodes);
console.log(res);
递归调用简化版本 filter+map
注意有性能问题
javascript
const arrayToTree = (nodes, parentId = null) => {
return nodes
.filter((node) => node.parentId === parentId)
.map((node) => ({
...node,
children: arrayToTree(nodes, node.id),
}));
};
const tree = arrayToTree(nodes, null);
console.log(tree);
// 1. 使用 filter 方法筛选出所有具有指定父节点 ID 的节点。
// 2. 使用 map 方法对筛选出的节点进行处理。
// 3. 对于每个节点,递归调用 arrayToTree 函数来构建其子树。
// 4. 注意map箭头函数返回一个对象需要加 =>({})括号
使用循环(哈希映射)
时间复杂度:O(n),其中 n 是节点的数量。 空间复杂度:O(n) 适合大规模数据
javascript
const arrayToTree = (array) => {
const map = {};
const tree = [];
// 1. 创建map映射
array.forEach((item) => {
// 构建一个map对象,key为节点id,值为原对象每个加上children属性
map[item.id] = { ...item, children: [] };
});
// map结果如上图
// 2. 遍历节点数组
array.forEach((item) => {
if (item.parentId !== null) {
// 如果当前节点有父节点,将其添加到父节点的子节点数组中
map[item.parentId].children.push(map[item.id]);
} else {
// 否则,将其作为根节点添加到最终的树结构中
tree.push(map[item.id]);
}
});
return tree;
};
const res = arrayToTree(array);
console.log(res);
for of简化一点点
javascript
function arrayToTreeLoop(nodes) {
const map = {};
const tree = [];
for (const node of nodes) {
map[node.id] = { ...node, children: [] };
}
// Object.values获取对象的所有属性值,返回数组
for (const node of Object.values(map)) {
if (node.parentId === null) {
tree.push(node);
} else {
map[node.parentId].children.push(node);
}
}
return tree;
}
const tree = arrayToTreeLoop(nodes);
使用reduce
javascript
function arrayToTreeReduce(nodes) {
// 1. 构建map结构,注意这步的map构建不能放在reduce中写
const map = {};
for (const node of nodes) {
map[node.id] = { ...node, children: [] };
}
// 2. reduce遍历,其实和前面一样的
const tree = nodes.reduce((acc, node) => {
// map[node.id] = { ...node, children: [] };
// 这里写map会有问题,Error
// 如果颠倒pid顺序 map未构建出来,children取不到报错
if (node.parentId === null) {
acc.push(map[node.id]);
} else {
map[node.parentId].children.push(map[node.id]);
}
return acc;
}, []);
return tree;
}
const tree = arrayToTreeReduce(nodes);
console.log(tree);
javascript
// 颠倒顺序是指:
const nodes = [
{ id: 1, name: "Node 1", parentId: null },
// id为4,pid2放在前面,这时候map还未完全构建好
{ id: 4, name: "Node 4", parentId: 2 },
{ id: 2, name: "Node 2", parentId: 1 },
{ id: 3, name: "Node 3", parentId: 1 },
{ id: 5, name: "Node 5", parentId: 2 },
{ id: 6, name: "Node 6", parentId: null },
];
哈希表 new Map 最优解!!
时间复杂度:O(n),其中 n 是节点的数量。 空间复杂度:O(n)。 适合大规模数据,而且由于使用了 Map,能够更方便地进行节点的查找和删除。
javascript
const map = new Map([
['name', '张三'],
['title', 'Author']
]);
// 新建map对象,成员是双元素数组
javascript
function arrayToTreeMap(nodes) {
// 将数组转为map对象
const map = new Map(nodes.map((node) => [node.id, { ...node, children: [] }]));
const tree = [];
// map.values()返回键值
// map.get(key) 读取key对应的键值
for (const node of map.values()) {
if (node.parentId === null) {
tree.push(node);
} else {
map.get(node.parentId).children.push(node);
}
}
return tree;
}
const tree = arrayToTreeMap(nodes);
使用深度优先搜索
时间复杂度:O(n),其中 n 是节点的数量。 空间复杂度:O(n)。 优缺点:相比于方法二、方法三和方法四,可以更方便地进行深度优先搜索。
javascript
function arrayToTreeDFS(nodes) {
const map = new Map(nodes.map((node) => [node.id, { ...node, children: [] }]));
const tree = [];
for (const node of map.values()) {
if (node.parentId === null) {
dfs(node, tree);
}
}
function dfs(node, parent) {
if (parent) {
parent.children.push(node);
}
for (const child of node.children) {
dfs(map.get(child.id), node);
}
}
return tree;
}
const tree = arrayToTreeDFS(nodes);
使用深度优先搜索(DFS)的方式来实现数组转换为树的方法。它基于递归地遍历树的节点,将每个节点添加到其父节点的 children 数组中。 下面是简要说明:
- 首先,通过 nodes.map() 方法创建一个 Map 对象,其中键是节点的 id,值是节点对象,包括 children 属性,初始为空数组。
- 然后,遍历 Map 中的每个节点对象。对于每个节点,如果它是树的根节点(即 parentId 为 null),则调用 dfs() 函数进行深度优先搜索。
- 在 dfs() 函数中,将当前节点添加到其父节点的 children 数组中,并递归调用 dfs() 函数处理当前节点的子节点。
- 最后,返回树结构。
这种实现方式利用了深度优先搜索的特性,在遍历树的过程中直接进行了节点的组织,从而构建出树状结构。 如果nodes 数组是事先按照节点的父子关系顺序排列的,那么这种方式会是一个非常高效的方法。
树形结构扁平化
要将树形结构扁平化,可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来遍历树的节点,并将每个节点添加到一个数组中。
深度优先搜索(DFS)
javascript
function treeToArray(tree) {
let res = []
for (const item of tree) {
// 使用解构将children属性剔除
const { children, ...i } = item
if (children && children.length) {
// 递归调用
res = res.concat(treeToArray(children))
}
res.push(i)
}
return res
}
- 定义了一个 treeToArray 函数,它接受一个树形结构作为参数,并返回一个数组。
- 使用 for...of 循环遍历树中的每个节点。
- 对于每个节点,使用解构赋值将其 children 属性剔除,因为我们只需要节点本身的数据,而不需要子节点的信息。
- 如果当前节点有子节点(即 children 存在且不为空数组),则递归调用 treeToArray 函数来处理子节点,并将结果与当前节点的数据合并。
- 将处理后的当前节点数据添加到结果数组中。
- 最后返回结果数组。
reduce实现,简洁一点
javascript
function treeToArray(tree) {
return tree.reduce((res, item) => {
const { children, ...i } = item
return res.concat(i, children && children.length ? treeToArray(children) : [])
}, [])
}
广度优先搜索(BFS)
我们使用一个队列来按层级顺序迭代树的节点。对于每个节点,我们首先将其从队列中取出并添加到结果数组中,然后将其子节点依次添加到队列中。
javascript
function flattenTreeBFS(tree) {
const flattened = [];
const queue = [...tree];
while (queue.length > 0) {
const node = queue.shift();
// 剔除当前节点的 children 属性,只保留节点数据
const { children, ...data } = node;
// 将节点数据添加到结果数组中
flattened.push(data);
if (children && children.length) {
queue.push(...children); // 将子节点依次添加到队列末尾中
}
}
return flattened;
}
// 当然用栈结构也可以实现
按照层级顺序依次处理每个节点及其子节点。 在每次循环迭代中,我们从队列中取出一个节点,将其数据(不包含子节点)添加到结果数组中。然后,如果当前节点有子节点,就将子节点依次添加到队列末尾。这样,通过不断地从队列中取出节点并处理,直到队列为空,我们就完成了树形结构的扁平化。
typescript
// 使用哈希表 最优解!
const arrayToTree = (array) => {
const tree = [];
// 将原数组转为map对象,key为id,value为对象
const map = new Map(
array.map((item) => [item.id, { ...item, children: [] }])
);
for (const item of map.values()) {
// 根节点
if (item.parentId === null) {
tree.push(item);
} else {
map.get(item.parentId).children.push(item);
}
}
return tree;
};