概要
在前面分别介绍了"二叉查找树的相关理论知识，然后给出了二叉查找树的C和C++实现版本"。这一章写一写二叉查找树的Java实现版本。
目录
1. 二叉树查找树
2. 二叉查找树的Java实现
3. 二叉查找树的Java测试程序
转载请注明出处：http://www.cnblogs.com/skywang12345/p/3576452.html
更多内容: 数据结构与算法系列 目录
(01) 二叉查找树(一)之 图文解析 和 C语言的实现
(02) 二叉查找树(二)之 C++的实现
(03) 二叉查找树(三)之 Java的实现
二叉查找树简介
二叉查找树(Binary Search Tree)，又被称为二叉搜索树。
它是特殊的二叉树：对于二叉树，假设x为二叉树中的任意一个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y] <= key[x]；如果y是x的右子树的一个结点，则key[y] >= key[x]。那么，这棵树就是二叉查找树。如下图所示：
在二叉查找树中：
(01) 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
(02) 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
(03) 任意节点的左、右子树也分别为二叉查找树。
(04) 没有键值相等的节点（no duplicate nodes）。
二叉查找树的Java实现
1. 二叉查找树节点的定义
public class BSTree<T extends Comparable<T>> {
private BSTNode<T> mRoot; // 根结点
public class BSTNode<T extends Comparable<T>> {
T key; // 关键字(键值)
BSTNode<T> left; // 左孩子
BSTNode<T> right; // 右孩子
BSTNode<T> parent; // 父结点
public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {
this.key = key;
this.parent = parent;
this.left = left;
this.right = right;
}
}
......
}
BSTree是二叉树，它保护了二叉树的根节点mRoot；mRoot是BSTNode类型，而BSTNode是二叉查找树的节点，它是BSTree的内部类。BSTNode包含二叉查找树的几个基本信息：
(01) key -- 它是关键字，是用来对二叉查找树的节点进行排序的。
(02) left -- 它指向当前节点的左孩子。
(03) right -- 它指向当前节点的右孩子。
(04) parent -- 它指向当前节点的父结点。
2 遍历
这里讲解前序遍历、中序遍历、后序遍历3种方式。
2.1 前序遍历
若二叉树非空，则执行以下操作：
(01) 访问根结点；
(02) 先序遍历左子树；
(03) 先序遍历右子树。
前序遍历代码
private void preOrder(BSTNode<T> tree) {
if(tree != null) {
System.out.print(tree.key+" ");
preOrder(tree.left);
preOrder(tree.right);
}
}
public void preOrder() {
preOrder(mRoot);
}
2.2 中序遍历
若二叉树非空，则执行以下操作：
(01) 中序遍历左子树；
(02) 访问根结点；
(03) 中序遍历右子树。
中序遍历代码
private void inOrder(BSTNode<T> tree) {
if(tree != null) {
inOrder(tree.left);
System.out.print(tree.key+" ");
inOrder(tree.right);
}
}
public void inOrder() {
inOrder(mRoot);
}
2.3 后序遍历
若二叉树非空，则执行以下操作：
(01) 后序遍历左子树；
(02) 后序遍历右子树；
(03) 访问根结点。
后序遍历代码
private void postOrder(BSTNode<T> tree) {
if(tree != null)
{
postOrder(tree.left);
postOrder(tree.right);
System.out.print(tree.key+" ");
}
}
public void postOrder() {
postOrder(mRoot);
}
看看下面这颗树的各种遍历方式：
对于上面的二叉树而言，
(01) 前序遍历结果： 3 1 2 5 4 6
(02) 中序遍历结果： 1 2 3 4 5 6
(03) 后序遍历结果： 2 1 4 6 5 3
3. 查找
递归版本的代码
/*
* (递归实现)查找"二叉树x"中键值为key的节点
*/
private BSTNode<T> search(BSTNode<T> x, T key) {
if (x==null)
return x;
int cmp = key.compareTo(x.key);
if (cmp < 0)
return search(x.left, key);
else if (cmp > 0)
return search(x.right, key);
else
return x;
}
public BSTNode<T> search(T key) {
return search(mRoot, key);
}
非递归版本的代码
/*
* (非递归实现)查找"二叉树x"中键值为key的节点
*/
private BSTNode<T> iterativeSearch(BSTNode<T> x, T key) {
while (x!=null) {
int cmp = key.compareTo(x.key);
if (cmp < 0)
x = x.left;
else if (cmp > 0)
x = x.right;
else
return x;
}
return x;
}
public BSTNode<T> iterativeSearch(T key) {
return iterativeSearch(mRoot, key);
}
4. 最大值和最小值
查找最大值的代码
/*
* 查找最大结点：返回tree为根结点的二叉树的最大结点。
*/
private BSTNode<T> maximum(BSTNode<T> tree) {
if (tree == null)
return null;
while(tree.right != null)
tree = tree.right;
return tree;
}
public T maximum() {
BSTNode<T> p = maximum(mRoot);
if (p != null)
return p.key;
return null;
}
查找最小值的代码
/*
* 查找最小结点：返回tree为根结点的二叉树的最小结点。
*/
private BSTNode<T> minimum(BSTNode<T> tree) {
if (tree == null)
return null;
while(tree.left != null)
tree = tree.left;
return tree;
}
public T minimum() {
BSTNode<T> p = minimum(mRoot);
if (p != null)
return p.key;
return null;
}
5. 前驱和后继
节点的前驱：是该节点的左子树中的最大节点。
节点的后继：是该节点的右子树中的最小节点。
查找前驱节点的代码
/*
* 找结点(x)的前驱结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。
*/
public BSTNode<T> predecessor(BSTNode<T> x) {
// 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
if (x.left != null)
return maximum(x.left);
// 如果x没有左孩子。则x有以下两种可能：
// (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
// (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
BSTNode<T> y = x.parent;
while ((y!=null) && (x==y.left)) {
x = y;
y = y.parent;
}
return y;
}
查找后继节点的代码
/*
* 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。
*/
public BSTNode<T> successor(BSTNode<T> x) {
// 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
if (x.right != null)
return minimum(x.right);
// 如果x没有右孩子。则x有以下两种可能：
// (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
// (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
BSTNode<T> y = x.parent;
while ((y!=null) && (x==y.right)) {
x = y;
y = y.parent;
}
return y;
}
6. 插入
插入节点的代码
/*
* 将结点插入到二叉树中
*
* 参数说明：
* tree 二叉树的
* z 插入的结点
*/
private void insert(BSTree<T> bst, BSTNode<T> z) {
int cmp;
BSTNode<T> y = null;
BSTNode<T> x = bst.mRoot;
// 查找z的插入位置
while (x != null) {
y = x;
cmp = z.key.compareTo(x.key);
if (cmp < 0)
x = x.left;
else
x = x.right;
}
z.parent = y;
if (y==null)
bst.mRoot = z;
else {
cmp = z.key.compareTo(y.key);
if (cmp < 0)
y.left = z;
else
y.right = z;
}
}
/*
* 新建结点(key)，并将其插入到二叉树中
*
* 参数说明：
* tree 二叉树的根结点
* key 插入结点的键值
*/
public void insert(T key) {
BSTNode<T> z=new BSTNode<T>(key,null,null,null);
// 如果新建结点失败，则返回。
if (z != null)
insert(this, z);
}
注：本文实现的二叉查找树是允许插入相同键值的节点的。若想禁止二叉查找树中插入相同键值的节点，可以参考"二叉查找树(一)之 图文解析 和 C语言的实现"中的插入函数进行修改。
7. 删除
删除节点的代码
/*
* 删除结点(z)，并返回被删除的结点
*
* 参数说明：
* bst 二叉树
* z 删除的结点
*/
private BSTNode<T> remove(BSTree<T> bst, BSTNode<T> z) {
BSTNode<T> x=null;
BSTNode<T> y=null;
if ((z.left == null) || (z.right == null) )
y = z;
else
y = successor(z);
if (y.left != null)
x = y.left;
else
x = y.right;
if (x != null)
x.parent = y.parent;
if (y.parent == null)
bst.mRoot = x;
else if (y == y.parent.left)
y.parent.left = x;
else
y.parent.right = x;
if (y != z)
z.key = y.key;
return y;
}
/*
* 删除结点(z)，并返回被删除的结点
*
* 参数说明：
* tree 二叉树的根结点
* z 删除的结点
*/
public void remove(T key) {
BSTNode<T> z, node;
if ((z = search(mRoot, key)) != null)
if ( (node = remove(this, z)) != null)
node = null;
}
8. 打印
打印二叉查找树的代码
/*
* 打印"二叉查找树"
*
* key -- 节点的键值
* direction -- 0，表示该节点是根节点;
* -1，表示该节点是它的父结点的左孩子;
* 1，表示该节点是它的父结点的右孩子。
*/
private void print(BSTNode<T> tree, T key, int direction) {
if(tree != null) {
if(direction==0) // tree是根节点
System.out.printf("%2d is root\n", tree.key);
else // tree是分支节点
System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==1?"right" : "left");
print(tree.left, tree.key, -1);
print(tree.right,tree.key, 1);
}
}
public void print() {
if (mRoot != null)
print(mRoot, mRoot.key, 0);
}
9. 销毁
销毁二叉查找树的代码
/*
* 销毁二叉树
*/
private void destroy(BSTNode<T> tree) {
if (tree==null)
return ;
if (tree.left != null)
destroy(tree.left);
if (tree.right != null)
destroy(tree.right);
tree=null;
}
public void clear() {
destroy(mRoot);
mRoot = null;
}
完整的实现代码
二叉查找树的Java实现文件(BSTree.java)
1 /**View Code
2 * Java 语言: 二叉查找树
3 *
4 * @author skywang
5 * @date 2013/11/07
6 */
7
8 public class BSTree<T extends Comparable<T>> {
9
10 private BSTNode<T> mRoot; // 根结点
11
12 public class BSTNode<T extends Comparable<T>> {
13 T key; // 关键字(键值)
14 BSTNode<T> left; // 左孩子
15 BSTNode<T> right; // 右孩子
16 BSTNode<T> parent; // 父结点
17
18 public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {
19 this.key = key;
20 this.parent = parent;
21 this.left = left;
22 this.right = right;
23 }
24
25 public T getKey() {
26 return key;
27 }
28
29 public String toString() {
30 return "key:"+key;
31 }
32 }
33
34 public BSTree() {
35 mRoot=null;
36 }
37
38 /*
39 * 前序遍历"二叉树"
40 */
41 private void preOrder(BSTNode<T> tree) {
42 if(tree != null) {
43 System.out.print(tree.key+" ");
44 preOrder(tree.left);
45 preOrder(tree.right);
46 }
47 }
48
49 public void preOrder() {
50 preOrder(mRoot);
51 }
52
53 /*
54 * 中序遍历"二叉树"
55 */
56 private void inOrder(BSTNode<T> tree) {
57 if(tree != null) {
58 inOrder(tree.left);
59 System.out.print(tree.key+" ");
60 inOrder(tree.right);
61 }
62 }
63
64 public void inOrder() {
65 inOrder(mRoot);
66 }
67
68
69 /*
70 * 后序遍历"二叉树"
71 */
72 private void postOrder(BSTNode<T> tree) {
73 if(tree != null)
74 {
75 postOrder(tree.left);
76 postOrder(tree.right);
77 System.out.print(tree.key+" ");
78 }
79 }
80
81 public void postOrder() {
82 postOrder(mRoot);
83 }
84
85
86 /*
87 * (递归实现)查找"二叉树x"中键值为key的节点
88 */
89 private BSTNode<T> search(BSTNode<T> x, T key) {
90 if (x==null)
91 return x;
92
93 int cmp = key.compareTo(x.key);
94 if (cmp < 0)
95 return search(x.left, key);
96 else if (cmp > 0)
97 return search(x.right, key);
98 else
99 return x;
100 }
101
102 public BSTNode<T> search(T key) {
103 return search(mRoot, key);
104 }
105
106 /*
107 * (非递归实现)查找"二叉树x"中键值为key的节点
108 */
109 private BSTNode<T> iterativeSearch(BSTNode<T> x, T key) {
110 while (x!=null) {
111 int cmp = key.compareTo(x.key);
112
113 if (cmp < 0)
114 x = x.left;
115 else if (cmp > 0)
116 x = x.right;
117 else
118 return x;
119 }
120
121 return x;
122 }
123
124 public BSTNode<T> iterativeSearch(T key) {
125 return iterativeSearch(mRoot, key);
126 }
127
128 /*
129 * 查找最小结点：返回tree为根结点的二叉树的最小结点。
130 */
131 private BSTNode<T> minimum(BSTNode<T> tree) {
132 if (tree == null)
133 return null;
134
135 while(tree.left != null)
136 tree = tree.left;
137 return tree;
138 }
139
140 public T minimum() {
141 BSTNode<T> p = minimum(mRoot);
142 if (p != null)
143 return p.key;
144
145 return null;
146 }
147
148 /*
149 * 查找最大结点：返回tree为根结点的二叉树的最大结点。
150 */
151 private BSTNode<T> maximum(BSTNode<T> tree) {
152 if (tree == null)
153 return null;
154
155 while(tree.right != null)
156 tree = tree.right;
157 return tree;
158 }
159
160 public T maximum() {
161 BSTNode<T> p = maximum(mRoot);
162 if (p != null)
163 return p.key;
164
165 return null;
166 }
167
168 /*
169 * 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。
170 */
171 public BSTNode<T> successor(BSTNode<T> x) {
172 // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
173 if (x.right != null)
174 return minimum(x.right);
175
176 // 如果x没有右孩子。则x有以下两种可能：
177 // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
178 // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
179 BSTNode<T> y = x.parent;
180 while ((y!=null) && (x==y.right)) {
181 x = y;
182 y = y.parent;
183 }
184
185 return y;
186 }
187
188 /*
189 * 找结点(x)的前驱结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。
190 */
191 public BSTNode<T> predecessor(BSTNode<T> x) {
192 // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
193 if (x.left != null)
194 return maximum(x.left);
195
196 // 如果x没有左孩子。则x有以下两种可能：
197 // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
198 // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
199 BSTNode<T> y = x.parent;
200 while ((y!=null) && (x==y.left)) {
201 x = y;
202 y = y.parent;
203 }
204
205 return y;
206 }
207
208 /*
209 * 将结点插入到二叉树中
210 *
211 * 参数说明：
212 * tree 二叉树的
213 * z 插入的结点
214 */
215 private void insert(BSTree<T> bst, BSTNode<T> z) {
216 int cmp;
217 BSTNode<T> y = null;
218 BSTNode<T> x = bst.mRoot;
219
220 // 查找z的插入位置
221 while (x != null) {
222 y = x;
223 cmp = z.key.compareTo(x.key);
224 if (cmp < 0)
225 x = x.left;
226 else
227 x = x.right;
228 }
229
230 z.parent = y;
231 if (y==null)
232 bst.mRoot = z;
233 else {
234 cmp = z.key.compareTo(y.key);
235 if (cmp < 0)
236 y.left = z;
237 else
238 y.right = z;
239 }
240 }
241
242 /*
243 * 新建结点(key)，并将其插入到二叉树中
244 *
245 * 参数说明：
246 * tree 二叉树的根结点
247 * key 插入结点的键值
248 */
249 public void insert(T key) {
250 BSTNode<T> z=new BSTNode<T>(key,null,null,null);
251
252 // 如果新建结点失败，则返回。
253 if (z != null)
254 insert(this, z);
255 }
256
257 /*
258 * 删除结点(z)，并返回被删除的结点
259 *
260 * 参数说明：
261 * bst 二叉树
262 * z 删除的结点
263 */
264 private BSTNode<T> remove(BSTree<T> bst, BSTNode<T> z) {
265 BSTNode<T> x=null;
266 BSTNode<T> y=null;
267
268 if ((z.left == null) || (z.right == null) )
269 y = z;
270 else
271 y = successor(z);
272
273 if (y.left != null)
274 x = y.left;
275 else
276 x = y.right;
277
278 if (x != null)
279 x.parent = y.parent;
280
281 if (y.parent == null)
282 bst.mRoot = x;
283 else if (y == y.parent.left)
284 y.parent.left = x;
285 else
286 y.parent.right = x;
287
288 if (y != z)
289 z.key = y.key;
290
291 return y;
292 }
293
294 /*
295 * 删除结点(z)，并返回被删除的结点
296 *
297 * 参数说明：
298 * tree 二叉树的根结点
299 * z 删除的结点
300 */
301 public void remove(T key) {
302 BSTNode<T> z, node;
303
304 if ((z = search(mRoot, key)) != null)
305 if ( (node = remove(this, z)) != null)
306 node = null;
307 }
308
309 /*
310 * 销毁二叉树
311 */
312 private void destroy(BSTNode<T> tree) {
313 if (tree==null)
314 return ;
315
316 if (tree.left != null)
317 destroy(tree.left);
318 if (tree.right != null)
319 destroy(tree.right);
320
321 tree=null;
322 }
323
324 public void clear() {
325 destroy(mRoot);
326 mRoot = null;
327 }
328
329 /*
330 * 打印"二叉查找树"
331 *
332 * key -- 节点的键值
333 * direction -- 0，表示该节点是根节点;
334 * -1，表示该节点是它的父结点的左孩子;
335 * 1，表示该节点是它的父结点的右孩子。
336 */
337 private void print(BSTNode<T> tree, T key, int direction) {
338
339 if(tree != null) {
340
341 if(direction==0) // tree是根节点
342 System.out.printf("%2d is root\n", tree.key);
343 else // tree是分支节点
344 System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==1?"right" : "left");
345
346 print(tree.left, tree.key, -1);
347 print(tree.right,tree.key, 1);
348 }
349 }
350
351 public void print() {
352 if (mRoot != null)
353 print(mRoot, mRoot.key, 0);
354 }
355 }
二叉查找树的C++测试程序(BSTreeTest.java)
1 /**View Code
2 * Java 语言: 二叉查找树
3 *
4 * @author skywang
5 * @date 2013/11/07
6 */
7 public class BSTreeTest {
8
9 private static final int arr[] = {1,5,4,3,2,6};
10
11 public static void main(String[] args) {
12 int i, ilen;
13 BSTree<Integer> tree=new BSTree<Integer>();
14
15 System.out.print("== 依次添加: ");
16 ilen = arr.length;
17 for(i=0; i<ilen; i++) {
18 System.out.print(arr[i]+" ");
19 tree.insert(arr[i]);
20 }
21
22 System.out.print("\n== 前序遍历: ");
23 tree.preOrder();
24
25 System.out.print("\n== 中序遍历: ");
26 tree.inOrder();
27
28 System.out.print("\n== 后序遍历: ");
29 tree.postOrder();
30 System.out.println();
31
32 System.out.println("== 最小值: "+ tree.minimum());
33 System.out.println("== 最大值: "+ tree.maximum());
34 System.out.println("== 树的详细信息: ");
35 tree.print();
36
37 System.out.print("\n== 删除根节点: "+ arr[3]);
38 tree.remove(arr[3]);
39
40 System.out.print("\n== 中序遍历: ");
41 tree.inOrder();
42 System.out.println();
43
44 // 销毁二叉树
45 tree.clear();
46 }
47 }
在二叉查找树的Java实现中，使用了泛型，也就意味着支持任意类型； 但是该类型必须要实现Comparable接口。
二叉查找树的Java测试程序
上面的BSTreeTest.java是二叉查找树树的测试程序，运行结果如下：
== 依次添加: 1 5 4 3 2 6
== 前序遍历: 1 5 4 3 2 6
== 中序遍历: 1 2 3 4 5 6
== 后序遍历: 2 3 4 6 5 1
== 最小值: 1
== 最大值: 6
== 树的详细信息:
1 is root
5 is 1's right child
4 is 5's left child
3 is 4's left child
2 is 3's left child
6 is 5's right child
== 删除根节点: 3
== 中序遍历: 1 2 4 5 6
下面对测试程序的流程进行分析！
(01) 新建"二叉查找树"root。
(02) 向二叉查找树中依次插入1,5,4,3,2,6 。如下图所示：
(03) 遍历和查找
插入1,5,4,3,2,6之后，得到的二叉查找树如下：
前序遍历结果: 1 5 4 3 2 6
中序遍历结果: 1 2 3 4 5 6
后序遍历结果: 2 3 4 6 5 1
最小值是1，而最大值是6。
(04) 删除节点4。如下图所示：
(05) 重新遍历该二叉查找树。
中序遍历结果: 1 2 4 5 6