curTain

api 设计

实现

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
class BinaryTree {
root = null
n = 0
size(){
return this.n
}
putNode( key, value ){
this.root = this.put( this.root, key, value )
}
put( node, key, value ){
if( node === null ){
this.n ++
return new TreeNode( key, value, null, null )
}
// 如果 node 子树不为空
// 比较 node 节点的键和 key 的大小

if( key > node.key ){
// 如果 key 大于 node 节点的键,则继续找 node 的右子节点
node.right = this.put( node.right, key, value )
} else if( key < node.key ){
// 如果小于 node 节点的键,继续寻找左子节点
node.left = this.put( node.left, key, value )
} else {
// 相等,替换当前节点的值
node.value = value
}
return node
}
getValue( key ){
return this.get( this.root, key )
}
get( node, key ){
if( node === null ){
return null
}

// 比较 key 和 x 节点的键的大小
if( key > node.key ){
// key 大于当前节点,继续寻找右节点
return get( node.right, key )
} else if( key < node.key ){
return get( node.left, key )
} else {
return node.value
}
}

// 删除树中 key 对应的节点,并返回删除后的新树
deleteNode( key ){
this.delete( this.root, key )
}
delete( node, key ){
if( node === null ){
return null
}
if( key > node.key ){
node.right = this.delete( node.right, key )
} else if( key < node.key ){
node.left = this.delete( node.left, key )
} else {
// 如果 key 相等,删除当前节点
this.n --

// 判定当前节点是否只有一个子节点,只有一个子节点,就把那个子节点接到父节点
if( !node.left ){
return node.right
}
if( !node.right ){
return node.left
}

// 如果两个子节点都在,获取右子节点最小的子节点,
// 为什么获取右边的,因为这样的交换操作次数可以最小
// 如果是取左边最大值的话,需要不断的创建节点,交换顺序

// 得到右子树中最小的节点
let minNode = node.right
while( minNode.left !== null ){
if( minNode.left.left === null ){
let temp = minNode.left
// 删除右子树中最小的节点
minNode.left = null
minNode = temp
} else {
minNode = minNode.left
}
}

// 让 node 节点的左子树成为 minNode 的左子树
minNode.left = node.left
// 让 node 节点的左子树成为 minNode 的右子树
minNode.right = node.right
// 让 node 节点的父节点指向 minNode 节点
node = minNode
}
return node
}
// 在整颗树中查找最小的键
getTreeMin(){
return this.getNodeMin( this.root )
}

getNodeMin( node ){
if( node.left ){
return this.getNodeMin( node.left )
} else {
return node
}
}

// 在整颗树中找最大的值
getTreeMax(){
return this.getNodeMax( this.root )
}

getNodeMax( node ){
if( node.right ){
return this.getNodeMax( node.right )
} else {
return node
}
}

// 获取指定树中的所有节点,并将节点的 key 放入到队列中
// 先序遍历
preMap( node, queue=[] ){
if( !node ) return
queue.push( node.key )
// 递归左子节点
node.left && this.preMap( node.left, queue )
// 递归右子节点
node.right && this.preMap( node.right, queue )
}

// 中序遍历
midMap( node, queue=[] ){
if( !node ) return
node.left && this.midMap( node.left, queue )
queue.push( node.key )
node.right && this.midMap( node.right, queue )
}

// 后序遍历
afterMap( node, queue=[] ){
if( !node ) return
node.left && this.midMap( node.left, queue )
node.right && this.midMap( node.right, queue )
queue.push( node.key )
}

// 层序遍历
layerMap(){
// 定义两个队列,一个存储 key,另一个存储节点
let keys = []
let queue = [ this.root ]
while( queue.length ){
let item = queue.shift()
keys.push( item.key )
item.left && queue.push( item.left )
item.right && queue.push( item.right )
}
return keys
}

// 返回整个树的高度
getTreeDepth(){
return this.getNodeDepth( this.root )
}
// 返回指定树的高度
getNodeDepth( node ){
if( !node ) return 0

let max = 0
let maxL = 0
let maxR = 0
// 左子树的最大深度
if( !node.left ){
maxL = this.getNodeDepth( node.left )
}
// 右子树的最大深度
if( !node.right ){
maxR = this.getNodeDepth( node.right )
}

max = maxL > maxR ? maxL+1 : maxR+1
return max
}
}


// 测试

let binaryTree = new BinaryTree()

binaryTree.putNode( 1, 1 )
binaryTree.putNode( 9, 9 )
binaryTree.putNode( 2, 2 )
binaryTree.putNode( 8, 8 )
binaryTree.putNode( 3, 3 )
binaryTree.putNode( 7, 7 )
binaryTree.putNode( 4, 4 )

console.log( "搜索树:", binaryTree )

let min = binaryTree.getTreeMin()
console.log( "最小值:", min )
let max = binaryTree.getTreeMax()
console.log( "最小值:", max )

// 层序遍历
let premap = binaryTree.layerMap()
console.log( "前序:", premap )

 评论