JavaScript实现扁平数组与树结构的相互转换
扁平数组转为树结构
题目描述：
给定以下数据格式的扁平数组：
1const flatArray = [
2 { id: 1, parentId: null, name: 'root1' },
3 { id: 2, parentId: 1, name: 'child1' },
4 { id: 3, parentId: 1, name: 'child2' },
5 { id: 4, parentId: 2, name: 'grandchild1' },
6 { id: 5, parentId: 3, name: 'grandchild2' },
7];
8
你需要将其转换为以下树状结构：
1const tree = [
2 {
3 "id": 1,
4 "parentId": null,
5 "name": "root1",
6 "children": [
7 {
8 "id": 2,
9 "parentId": 1,
10 "name": "child1",
11 "children": [
12 {
13 "id": 4,
14 "parentId": 2,
15 "name": "grandchild1",
16 "children": []
17 }
18 ]
19 },
20 {
21 "id": 3,
22 "parentId": 1,
23 "name": "child2",
24 "children": [
25 {
26 "id": 5,
27 "parentId": 3,
28 "name": "grandchild2",
29 "children": []
30 }
31 ]
32 }
33 ]
34 }
35];
36
请编写一个名为 flatArrayToTree 的函数，接受上述类型的扁平数组作为参数，并返回相应的树状结构数组。
方案一：使用Map和递归
1function flatArrayToTree(flatArray) {
2 // 创建一个映射，方便通过id查找节点
3 const map = new Map();
4 flatArray.forEach(item => {
5 map.set(item.id, { ...item, children: [] });
6 });
7
8 // 定义一个递归函数，用于构建每个节点的子树
9 function buildTree(node) {
10 flatArray.forEach(item => {
11 if (item.parentId === node.id) {
12 const childNode = map.get(item.id);
13 // 递归构建子树，并添加到当前节点的children中
14 node.children.push(buildTree(childNode));
15 }
16 });
17 return node;
18 }
19
20 // 过滤出根节点并递归构建整棵树
21 return flatArray
22 .filter(item => item.parentId === null)
23 .map(rootNode => buildTree(map.get(rootNode.id)));
24}
25
26const tree = flatArrayToTree(flatArray);
27
方案一解释
首先，我们创建一个 Map 来存储每个节点及其子节点列表。
接着定义一个递归函数 buildTree 用于构建父子关系。遍历扁平数组时，对于每个节点，将其添加到 Map 中并初始化其 children 属性为空数组。对于有 parentId 的节点，将其添加到相应父节点的 children 数组中。
最后从 Map 中提取 parentId 为 null 的节点形成结果数组。
方案二：使用对象作为索引和循环
1function flatArrayToTree(flatData) {
2 const result = [];
3 const map = {};
4
5 // 先构建一个id映射表
6 flatData.forEach(item => {
7 map[item.id] = { ...item, children: [] };
8 });
9
10 // 然后根据parentId将子节点添加到父节点的children属性下
11 flatData.forEach(item => {
12 if (item.parentId !== null) {
13 map[item.parentId].children.push(map[item.id]);
14 } else {
15 result.push(map[item.id]);
16 }
17 });
18
19 return result;
20}
21
22const tree = flatArrayToTree(flatArray);
23
方案二解释
首先遍历扁平数组，创建一个键值对形式的哈希表，键是每个元素的 id，值是该元素本身。这样我们可以快速通过 id 找到对应的节点。
再次遍历扁平数组，对于每个元素，检查其 parentId 是否存在于哈希表中。如果存在，说明找到了其父节点，将当前元素添加到其父节点的 children 数组中。若不存在 parentId（即为根节点），则直接添加到结果数组中。
最终得到的结果数组就是所求的树形结构。
最深层级
在构建树结构的时候，如果需要记录最深层级，应该怎么做呢？下面是可以记录最深层级的方案：
1function flatArrayToTree(flatData) {
2 let maxDepth = 0;
3
4 const result = [];
5 const map = {};
6
7 // 先构建一个id映射表
8 flatData.forEach(item => {
9 map[item.id] = { ...item, children: [], depth: 0 };
10 });
11
12 // 然后根据parentId将子节点添加到父节点的children属性下，并计算深度
13 flatData.forEach(item => {
14 if (item.parentId !== null) {
15 const parent = map[item.parentId];
16 parent.children.push(map[item.id]);
17
18 // 更新当前节点及其父节点的深度
19 let currentDepth = parent.depth + 1;
20 map[item.id].depth = currentDepth;
21
22 // 更新最大深度
23 maxDepth = Math.max(maxDepth, currentDepth);
24 } else {
25 result.push(map[item.id]);
26 }
27 });
28
29 return { tree: result, maxDepth };
30}
31
32const { tree, maxDepth } = flatArrayToTree(flatArray);
33console.log('Tree:', tree);
34console.log('Max Depth:', maxDepth);
35
增加 maxDepth 变量记录最大深度，在每次将子节点添加到父节点的 children 属性下时，记录层级，计算深度。
树结构转扁平数组
以上是扁平数组转为树结构的情况，下面来看针对已有的树形结构，将其转换回扁平数组的情况。
实现
1function treeToArray(treeNodes) {
2 let result = [];
3
4 //递归函数 traverse，用于处理单个节点
5 function traverse(node) {
6 const newNode = { ...node };
7 delete newNode.children;
8 // 将没有子节点的新节点添加到结果数组中
9 result.push(newNode);
10
11 // 如果当前节点包含 children 属性（即有子节点）
12 if (node.children) {
13 node.children.forEach(traverse);
14 }
15 }
16
17 treeNodes.forEach(traverse);
18
19 return result;
20}
21
22const flatArray = treeToArray(tree);
23
解释
首先定义了一个 treeToArray 函数，该函数内部定义了一个名为 traverse 的递归函数，用于遍历树形结构的每一个节点并将节点添加到扁平数组中。
然后遍历输入的树形结构，对每个节点调用 traverse 函数。在 traverse 函数内部，如果当前节点有子节点，则对其每个子节点进行同样的遍历操作。
最后返回扁平数组。
总结
在解决扁平数组与树结构之间的转换问题时，关键在于识别父子关系并通过建立索引或映射结构进行层次遍历，以实现数据的转换。
在实际业务中，扁平数组与树结构的转化，常见在目录树组件，级联选择组件等情况。