js 数组转为树形(tree)结构
数组转树结构采取递归和非递归两种方式，树结构转扁平化数组采取深度优先遍历（递归和非递归两种方式）和广度优先遍历实现。
let arr =[
{id:2,name:'部门B',parentId:0},
{id:3,name:'部门C',parentId:1},
{id:1,name:'部门A',parentId:2},
{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}
];
/**
* 数组转树 非递归求解
* 利用数组和对象相互引用 时间复杂度O(n)
* @param {Object} list
*/
function totree(list,parId) {
let obj = {};
let result = [];
//将数组中数据转为键值对结构 (这里的数组和obj会相互引用)
list.map(el => {
obj[el.id] = el;
})
for(let i=0, len = list.length; i < len; i++) {
let id = list[i].parentId;
if(id == parId) {
result.push(list[i]);
continue;
}
if(obj[id].children) {
obj[id].children.push(list[i]);
} else {
obj[id].children = [list[i]];
}
}
return result;
}
let res1 = totree(arr,0)
/**
* 数组转树 递归求解
*/
function toTree(list,parId){
let len = list.length
function loop(parId){
let res = [];
for(let i = 0; i < len; i++){
let item = list[i]
if(item.parentId === parId){
item.children = loop(item.id)
res.push(item)
}
}
return res
}
return loop(parId)
}
let result = toTree(arr,0)
/**
* 树转数组扁平化结构
* 深度优先遍历 堆栈 后进先出
*/
function deep(node){
let stack = node,
data = [];
while(stack.length != 0){
let pop = stack.pop();
data.push({
id: pop.id,
name: pop.name,
parentId: pop.parentId
})
let children = pop.children
if(children){
for(let i = children.length-1; i >=0; i--){
stack.push(children[i])
}
}
}
return data
}
//console.log(deep(res1))
/**
* 树转数组扁平化结构
* 深度优先遍历 递归
*/
function deepTraversal(data) {
const result = [];
data.forEach(item => {
const loop = data => {
result.push({
id: data.id,
name: data.name,
parentId: data.parentId
});
let child = data.children
if(child){
for(let i = 0; i < child.length; i++){
loop(child[i])
}
}
}
loop(item);
})
return result;
}
//console.log(deepTraversal(res1))
/**
* 广度优先
* 队列 先进先出
*/
function wideTraversal(node){
let stack = node,
data = [];
while(stack.length != 0){
let shift = stack.shift();
data.push({
id: shift.id,
name: shift.name,
parentId: shift.parentId
})
let children = shift.children
if(children){
for(let i = 0; i < children.length; i++){
stack.push(children[i])
}
}
}
return data
}
//console.log(wideTraversal(res1))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
# 代码示例
// 将如下数组：
[
{
id: 1,
pid: 0,
name: "body",
},
{
id: 2,
pid: 1,
name: "title",
},
{
id: 3,
pid: 2,
name: "div",
},
];
// 转化成：
[
{
id: 1,
pid: 0,
name: "body",
children: [
{
id: 2,
pid: 1,
name: "title",
children: [
{
id: 3,
pid: 1,
name: "div",
},
],
},
],
},
];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
代码实现：
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=`, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>toTree</title>
</head>
<body>
<script>
var source = [{
id: 1,
pid: 0,
name: 'body'
}, {
id: 2,
pid: 1,
name: 'title'
}, {
id: 3,
pid: 1,
name: 'div'
}, {
id: 4,
pid: 3,
name: 'span'
}, {
id: 5,
pid: 3,
name: 'icon'
}, {
id: 6,
pid: 4,
name: 'subspan'
}]
function toTree(data) {
let result = []
if(!Array.isArray(data)) {
return result
}
data.forEach(item => {
delete item.children;
});
let map = {};
data.forEach(item => {
map[item.id] = item;
});
data.forEach(item => {
let parent = map[item.pid];
if(parent) {
(parent.children || (parent.children = [])).push(item);
} else {
result.push(item);
}
});
return result;
}
console.log(toTree(source))
</script>
</body>
</html>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
上次更新: 2024/01/30, 00:35:17