1+ // 定义节点
2+ function Node ( key , value ) {
3+ this . key = key ;
4+ this . value = value ;
5+ this . left = null ;
6+ this . right = null ;
7+ }
8+
9+ /*
10+ * 定义二分搜索树
11+ */
12+ module . exports . BST = class BST {
13+ constructor ( ) {
14+ this . root = null ; // 根节点
15+ this . count = 0 ; // 节点个数
16+ }
17+
18+ // 向二分搜索树种插入一个新的数据对
19+ insert ( key , value ) {
20+ this . root = this . __insert ( this . root , key , value ) ;
21+ }
22+ // 向以node为根的二分搜索树中，插入节点(key, value),使用递归算法
23+ // 返回插入新节点后的二分搜索树的根
24+ __insert ( node , key , value ) {
25+ if ( node === null ) {
26+ this . count ++ ;
27+ return new Node ( key , value ) ;
28+ }
29+ // 如果key在树中已经存在，则更新value
30+ if ( key === node . key ) node . value = value ;
31+ else if ( key < node . key )
32+ node . left = this . __insert ( node . left , key , value ) ;
33+ else
34+ node . right = this . __insert ( node . right , key , value ) ;
35+ return node ; // 返回原来的节点
36+ }
37+
38+ // 查看二分搜索树种是否存在键key
39+ contain ( key ) {
40+ return this . __contain ( this . root , key ) ;
41+ }
42+ // 查看node为根的二分搜索树种是否包含键值为key的节点，使用递归算法
43+ __contain ( node , key ) {
44+ if ( node === null ) return false ;
45+ if ( key === node . key ) return true ;
46+ else if ( key < node . key ) return this . __contain ( node . left , key ) ;
47+ else return this . __contain ( node . right , key ) ;
48+ }
49+
50+ // 在二分搜索树种搜索键key所对应的值。如果这个值不存在返回null
51+ search ( key ) {
52+ return this . __search ( this . root , key ) ;
53+ }
54+ // 在以node为根的二分搜索树种中查找key所对应的value，使用递归算法
55+ __search ( node , key ) {
56+ if ( node === null ) return null ;
57+ if ( key === node . key ) return node . value ;
58+ else if ( key < node . key ) return this . __search ( node . left , key ) ;
59+ else return this . __search ( node . right , key ) ;
60+ }
61+
62+ // 二分搜索树的前序遍历,深度优先遍历
63+ preOrder ( ) {
64+ let str = "" ;
65+ this . __preOrder ( this . root , ( node ) => {
66+ str += node . key + " " ;
67+ } ) ;
68+ console . log ( str ) ;
69+ }
70+ // 对以node为根的二叉搜索树进行前序遍历，递归算法
71+ // 传入handle函数用于输出数据
72+ __preOrder ( node , handle ) {
73+ if ( node !== null ) {
74+ handle ( node ) ;
75+ this . __preOrder ( node . left , handle ) ;
76+ this . __preOrder ( node . right , handle ) ;
77+ }
78+ }
79+
80+ // 二分搜索树的中序遍历,深度优先遍历
81+ inOrder ( ) {
82+ let str = "" ;
83+ this . __inOrder ( this . root , ( node ) => {
84+ str += node . key + " " ;
85+ } ) ;
86+ console . log ( str ) ;
87+ }
88+ // 对以node为根的二叉搜索树进行中序遍历，递归算法
89+ // 传入handle函数用于输出数据
90+ __inOrder ( node , handle ) {
91+ if ( node !== null ) {
92+ this . __inOrder ( node . left , handle ) ;
93+ handle ( node ) ;
94+ this . __inOrder ( node . right , handle ) ;
95+ }
96+ }
97+
98+ // 二分搜索树的后序遍历,深度优先遍历
99+ postOrder ( ) {
100+ let str = "" ;
101+ this . __postOrder ( this . root , ( node ) => {
102+ str += node . key + " " ;
103+ } ) ;
104+ console . log ( str ) ;
105+ }
106+ // 对以node为根的二叉搜索树进行后序遍历，递归算法
107+ // 传入handle函数用于输出数据
108+ __postOrder ( node , handle ) {
109+ if ( node !== null ) {
110+ this . __postOrder ( node . left , handle ) ;
111+ this . __postOrder ( node . right , handle ) ;
112+ handle ( node ) ;
113+ }
114+ }
115+
116+ // 二分搜索树的层序遍历,广度优先遍历
117+ levelOrder ( ) {
118+ let queue = [ ] ;
119+ let str = "" ;
120+ queue . push ( this . root ) ;
121+ while ( queue . length > 0 ) {
122+ let node = queue . shift ( ) ;
123+ str += node . key + " " ;
124+ if ( node . left ) queue . push ( node . left ) ;
125+ if ( node . right ) queue . push ( node . right ) ;
126+ }
127+ console . log ( str ) ;
128+ }
129+
130+ // 寻找二分搜索树的最小的值
131+ minimun ( ) {
132+ let node = this . __minimum ( this . root ) ;
133+ return node . key ;
134+ }
135+ // 返回以node为根的二分搜索树的最小键值所在的节点，递归算法
136+ __minimum ( node ) {
137+ if ( node . left === null ) return node ;
138+ return this . __minimum ( node . left ) ;
139+ }
140+
141+ // 寻找二分搜索树的最大的值
142+ maximun ( ) {
143+ let node = this . __maximum ( this . root ) ;
144+ return node . key ;
145+ }
146+ // 返回以node为根的二分搜索树的最小键值所在的节点，递归算法
147+ __maximum ( node ) {
148+ if ( node . right === null ) return node ;
149+ return this . __maximum ( node . right ) ;
150+ }
151+
152+ // 删除二分搜索树中最小值所在的节点
153+ removeMin ( ) {
154+ if ( this . root ) this . root = this . __removeMin ( this . root ) ;
155+ }
156+ // 删除掉以node为根的二分搜索树中的最小节点
157+ // 返回删除节点后的二分搜索树的根
158+ __removeMin ( node ) {
159+ if ( node . left === null ) {
160+ let rightNode = node . right ;
161+ this . count -- ;
162+ return rightNode ;
163+ }
164+ node . left = this . __removeMin ( node . left ) ;
165+ return node ;
166+ }
167+
168+ // 删除二分搜索树中最小值所在的节点
169+ removeMax ( ) {
170+ if ( this . root ) this . root = this . __removeMax ( this . root ) ;
171+ }
172+ // 删除掉以node为根的二分搜索树中的最大节点
173+ // 返回删除节点后的二分搜索树的根
174+ __removeMax ( node ) {
175+ if ( node . right === null ) {
176+ let leftNode = node . left ;
177+ this . count -- ;
178+ return leftNode ;
179+ }
180+ node . right = this . __removeMax ( node . right ) ;
181+ return node ;
182+ }
183+
184+ // 从二分搜索树种删除键值为key的节点
185+ remove ( key ) {
186+ this . root = this . __remove ( this . root , key ) ;
187+ }
188+ // 删除掉以node为根的二分搜索树种键值为key的节点
189+ // 返回删除节点后新的二分搜索树的根
190+ __remove ( node , key ) {
191+ if ( node === null ) return null ;
192+ if ( key < node . key ) {
193+ node . left = this . __remove ( node . left , key ) ;
194+ return node ;
195+ } else if ( key > node . key ) {
196+ node . right = this . __remove ( node . right , key ) ;
197+ return node ;
198+ }
199+ else {
200+ // 待删除节点左子树为空的情况
201+ if ( node . left === null ) {
202+ let rightNode = node . right ;
203+ this . count -- ;
204+ return rightNode ;
205+ }
206+ // 待删除节点右子树为空的情况
207+ if ( node . right === null ) {
208+ let leftNode = node . left ;
209+ this . count -- ;
210+ return leftNode ;
211+ }
212+ // 待删除节点左右子树均不为空的情况
213+ // 找到比待删除节点大的最小节点，即待删除节点右子树的最小节点
214+ // 用这个节点替代删除节点的位置
215+ // 获得待删除节点右子树的最小节点
216+ let getRMinNode = this . __minimum ( node . right ) ;
217+ // 创建新的节点
218+ let successor = new Node ( getRMinNode . key , getRMinNode . value ) ;
219+ this . count ++ ;
220+ successor . right = this . __removeMin ( node . right ) ;
221+ successor . left = node . left ;
222+ this . count -- ;
223+ return successor ;
224+ }
225+ }
226+
227+ // 返回二分搜索树的节点个数
228+ size ( ) {
229+ return this . count ;
230+ }
231+ // 判断二分搜索树是否为空
232+ isEmpty ( ) {
233+ return this . count === 0 ;
234+ }
235+ }
0 commit comments