扁平树结构转换为嵌套json
-> 题目描述
数据库中存有扁平树结构如下：
| id | pid | label | depth |
|---|---|---|---|
| 1 | 0 | 1 | 1 |
| 2 | 1 | 1-1 | 2 |
| 3 | 1 | 1-2 | 2 |
| 4 | 1 | 1-3 | 2 |
| 5 | 3 | 1-2-1 | 3 |
| 6 | 4 | 1-3-1 | 3 |
| 7 | 5 | 1-2-1-1 | 4 |
| 8 | 4 | 1-3-2 | 3 |
| 9 | 3 | 1-2-2 | 3 |
| 10 | 8 | 1-3-2-1 | 4 |
需要转转为如下数据结构
[
{
"id": 1,
"pid": 0,
"label": "1",
"depth": 1,
"children": [
{"id": 2, "pid": 1, "label": "1-1", "depth": 2, "children": [] },
{"id": 3, "pid": 1, "label": "1-2", "depth": 2,
"children": [{
"id": 5, "pid": 3, "label": "1-2-1", "depth": 3,
"children": [{
"id": 7, "pid": 5, "label": "1-2-1-1", "depth": 4, "children": []
}]
},
{ "id": 9, "pid": 3, "label": "1-2-2", "depth": 3, "children": [] }
]
},
{"id": 4, "pid": 1, "label": "1-3", "depth": 2,
"children": [
{
"id": 6, "pid": 4, "label": "1-3-1", "depth": 3, "children": []
},
{
"id": 8, "pid": 4, "label": "1-3-2", "depth": 3,
"children": [{
"id": 10, "pid": 8, "label": "1-3-2-1", "depth": 4, "children": []
}]
}
]
}
]
}
]
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
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
-> 解法
点击查看
/**
* @param {[object]} list
* @return {[object]}
*
* */
const transListToJsonTree = function(list) {
function Node(node) {
this.id = node.id
this.label = node.label
this.depth = node.depth
this.pid = node.pid
this.left = null
this.right = null
this.parent = null
}
function BinaryTree() {
this.root = null
this.nodes = []
}
BinaryTree.prototype.insert = function(node) {
let curr_node = node
if (node instanceof Node === false) {
curr_node = new Node(node)
}
if (!this.root && curr_node.depth === 1) {
this.root = curr_node
this.nodes.push(curr_node)
return true
} else {
let root = this.nodes[0]
while (true) {
if (curr_node.depth > root.depth) {
if (curr_node.depth - root.depth !== 1) {
root = root.right || root.left //非相邻节点直接直接跨级
} else {
if (curr_node.pid === root.id) {
if (root.right === null) {
root.right = curr_node
curr_node.parent = root
this.nodes.push(curr_node)
return true
}
root = root.right
} else {
if (root.left) { //尝试遍历左节点的下级
root = root.left
} else { //如果不存在左节点说明走错了，返回上级节点左节点继续遍历
while (root.parent.id !== root.pid) {
root = root.parent
}
root = root.parent.left
}
}
}
} else if (curr_node.depth === root.depth) { //同级节点放在最左
if (root.left === null) {
root.left = curr_node
this.nodes.push(curr_node)
curr_node.parent = root
return true
} else {
root = root.left
}
} else {
console.log('invalid node: ', node)
return false
}
}
}
};
BinaryTree.prototype.serialization = function() {
const root = this.root
const ret = [gen_node_data(root)]
const map = {}
right_left_root(root)
return ret
function handler(node) {
let isLeaf = true
if (node.right && map[node.right.id]) {
isLeaf = false
let right_node = map[node.right.id]
const curr_node = gen_node_data(node)
if (node.right.left) {
curr_node.children = map['pid' + node.id]
} else {
curr_node.children.push(right_node)
}
map[node.id] = curr_node
}
if (node.left && map[node.left.id]) {
isLeaf = false
const key = 'pid' + node.pid
const curr_node = map[node.id] ? map[node.id] : gen_node_data(node)
map[node.id] = curr_node
let ret = map[key]
const left_node = map[node.left.id]
if (ret) {
map[key].unshift(curr_node)
} else {
map[key] = [curr_node, left_node]
}
}
if (isLeaf) {
map[node.id] = gen_node_data(node)
}
if (node.depth === 2) {
ret[0].children.unshift(map[node.id])
}
}
function gen_node_data(node) {
return {
id: node.id,
pid: node.pid,
label: node.label,
depth: node.depth,
children: []
}
}
function right_left_root(node) {
if (!node)
return
right_left_root(node.right)
right_left_root(node.left)
handler(node)
}
}
const btree = new BinaryTree()
for (let item of list) {
btree.insert(item)
}
return btree.serialization()
};
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
136
137
138
139
140
141
142
143
144
145
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
136
137
138
139
140
141
142
143
144
145
测试代码
const list = [
{id: 1, pid: 0, label:"1", depth: 1},
{id: 2, pid: 1, label:"1-1", depth: 2},
{id: 3, pid: 1, label:"1-2", depth: 2},
{id: 4, pid: 1, label:"1-3", depth: 2},
{id: 5, pid: 3, label:"1-2-1", depth: 3},
{id: 6, pid: 4, label:"1-3-1", depth: 3},
{id: 7, pid: 5, label:"1-2-1-1", depth: 4},
{id: 8, pid: 4, label:"1-3-2", depth: 3},
{id: 9, pid: 3, label:"1-2-2", depth: 3},
{id: 10, pid: 8, label:"1-3-2-1", depth: 4},
]
const ret = transListToJsonTree(list)
console.log(JSON.stringify(ret, null, 2))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
-> 总结
- 父节点肯定在子节点前面
- 子节点的depth属性表示了嵌套深度
- 从而联想到使用二叉树来解决该问题……
但一个目录节点下会存在多个子节点，因此严格来说其实不属于二叉树的结构。 又不想引进更复杂的 b+树，故强行将其改良成一棵自定义二叉树：
- 左节点表示同级节点，如存在多个同级节点，均顺序左移
- 右节点为下级子节点
按照这个定义就满足二叉树结构了，但插入节点的方法需要重写。遍历的方法不变。
从而把序列化的问题转换为二叉树遍历的问题。
准确点说，这里需要使用 后序遍历 ：从右到左再到根节点，先叶子节点再分支节点。
如果仅仅是序列化的问题，有更简洁的解法如下：
const transListToJsonTree = function(list) {
return list.filter(node => {
node.children = list.filter(child => node.id == child.pid);
return node.pid == 0;
});
}
1
2
3
4
5
6
2
3
4
5
6
用 for循环实现如下:
const transListToJsonTree = function(arr) {
for(let i =0; i<arr.length; i++){
const curr = arr[i]
curr.children = []
for(let j=i+1; j<arr.length;j++){
const node = arr[j]
if(curr.id === node.pid)
curr.children.push(node)
}
}
return arr[0]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
编辑此页 (opens new window)
更新于: 2019-07-08 17:45