【转】java实现二叉查找树

转自：http://blog.csdn.net/zyj8170/article/details/7045226

1. /**???*?@author?zyj8170??2011-2-13??
2. ?*????*?此程序实现一个二叉查找树的功能，可以进行动态插入、删除关键字；??
3. ?*?查询给定关键字、最小关键字、最大关键字；转换为有序列表(用于排序)???*???
4. ?*????*/??
5. ??import?java.util.ArrayList;??
6. import?java.util.List;????
7. public?class?BinarySearchTree?{????
8. ????//?树的根结点??????private?TreeNode?root?=?null;??
9. ??????//?遍历结点列表??
10. ????private?List<TreeNode>?nodelist?=?new?ArrayList<TreeNode>();????
11. ????private?class?TreeNode?{????
12. ????????private?int?key;??????????private?TreeNode?leftChild;??
13. ????????private?TreeNode?rightChild;??????????private?TreeNode?parent;??
14. ??????????public?TreeNode(int?key,?TreeNode?leftChild,?TreeNode?rightChild,??
15. ????????????????TreeNode?parent)?{??????????????this.key?=?key;??
16. ????????????this.leftChild?=?leftChild;??????????????this.rightChild?=?rightChild;??
17. ????????????this.parent?=?parent;??????????}??
18. ??????????public?int?getKey()?{??
19. ????????????return?key;??????????}??
20. ??????????public?String?toString()?{??
21. ????????????String?leftkey?=?(leftChild?==?null???""?:?String??????????????????????.valueOf(leftChild.key));??
22. ????????????String?rightkey?=?(rightChild?==?null???""?:?String??????????????????????.valueOf(rightChild.key));??
23. ????????????return?"("?+?leftkey?+?"?,?"?+?key?+?"?,?"?+?rightkey?+?")";??????????}??
24. ??????}??
25. ??????/**?
26. ?????*?isEmpty:?判断二叉查找树是否为空；若为空，返回?true?，否则返回?false?.??????*??
27. ?????*/??????public?boolean?isEmpty()?{??
28. ????????if?(root?==?null)?{??????????????return?true;??
29. ????????}?else?{??????????????return?false;??
30. ????????}??????}??
31. ??????/**?
32. ?????*?TreeEmpty:?对于某些二叉查找树操作(比如删除关键字)来说，若树为空，则抛出异常。??????*/??
33. ????public?void?TreeEmpty()?throws?Exception?{??????????if?(isEmpty())?{??
34. ????????????throw?new?Exception("树为空!");??????????}??
35. ????}????
36. ????/**??????*?search:?在二叉查找树中查询给定关键字?
37. ?????*???????*?@param?key?
38. ?????*????????????给定关键字??????*?@return?匹配给定关键字的树结点?
39. ?????*/??????public?TreeNode?search(int?key)?{??
40. ????????TreeNode?pNode?=?root;??????????while?(pNode?!=?null?&&?pNode.key?!=?key)?{??
41. ????????????if?(key?<?pNode.key)?{??????????????????pNode?=?pNode.leftChild;??
42. ????????????}?else?{??????????????????pNode?=?pNode.rightChild;??
43. ????????????}??????????}??
44. ????????return?pNode;??????}??
45. ??????/**?
46. ?????*?minElemNode:?获取二叉查找树中的最小关键字结点??????*??
47. ?????*?@return?二叉查找树的最小关键字结点??????*?@throws?Exception?
48. ?????*?????????????若树为空，则抛出异常??????*/??
49. ????public?TreeNode?minElemNode(TreeNode?node)?throws?Exception?{??????????if?(node?==?null)?{??
50. ????????????throw?new?Exception("树为空！");??????????}??
51. ????????TreeNode?pNode?=?node;??????????while?(pNode.leftChild?!=?null)?{??
52. ????????????pNode?=?pNode.leftChild;??????????}??
53. ????????return?pNode;??????}??
54. ??????/**?
55. ?????*?maxElemNode:?获取二叉查找树中的最大关键字结点??????*??
56. ?????*?@return?二叉查找树的最大关键字结点??????*?@throws?Exception?
57. ?????*?????????????若树为空，则抛出异常??????*/??
58. ????public?TreeNode?maxElemNode(TreeNode?node)?throws?Exception?{??????????if?(node?==?null)?{??
59. ????????????throw?new?Exception("树为空！");??????????}??
60. ????????TreeNode?pNode?=?node;??????????while?(pNode.rightChild?!=?null)?{??
61. ????????????pNode?=?pNode.rightChild;??????????}??
62. ????????return?pNode;??????}??
63. ??????/**?
64. ?????*?successor:?获取给定结点在中序遍历顺序下的后继结点??????*??
65. ?????*?@param?node??????*????????????给定树中的结点?
66. ?????*?@return?若该结点存在中序遍历顺序下的后继结点，则返回其后继结点；否则返回?null??????*?@throws?Exception?
67. ?????*/??????public?TreeNode?successor(TreeNode?node)?throws?Exception?{??
68. ????????if?(node?==?null)?{??????????????return?null;??
69. ????????}????
70. ????????//?若该结点的右子树不为空，则其后继结点就是右子树中的最小关键字结点??????????if?(node.rightChild?!=?null)?{??
71. ????????????return?minElemNode(node.rightChild);??????????}??
72. ????????//?若该结点右子树为空??????????TreeNode?parentNode?=?node.parent;??
73. ????????while?(parentNode?!=?null?&&?node?==?parentNode.rightChild)?{??????????????node?=?parentNode;??
74. ????????????parentNode?=?parentNode.parent;??????????}??
75. ????????return?parentNode;??????}??
76. ??????/**?
77. ?????*?precessor:?获取给定结点在中序遍历顺序下的前趋结点??????*??
78. ?????*?@param?node??????*????????????给定树中的结点?
79. ?????*?@return?若该结点存在中序遍历顺序下的前趋结点，则返回其前趋结点；否则返回?null??????*?@throws?Exception?
80. ?????*/??????public?TreeNode?precessor(TreeNode?node)?throws?Exception?{??
81. ????????if?(node?==?null)?{??????????????return?null;??
82. ????????}????
83. ????????//?若该结点的左子树不为空，则其前趋结点就是左子树中的最大关键字结点??????????if?(node.leftChild?!=?null)?{??
84. ????????????return?maxElemNode(node.leftChild);??????????}??
85. ????????//?若该结点左子树为空??????????TreeNode?parentNode?=?node.parent;??
86. ????????while?(parentNode?!=?null?&&?node?==?parentNode.leftChild)?{??????????????node?=?parentNode;??
87. ????????????parentNode?=?parentNode.parent;??????????}??
88. ????????return?parentNode;??????}??
89. ??????/**?
90. ?????*?insert:?将给定关键字插入到二叉查找树中??????*??
91. ?????*?@param?key??????*????????????给定关键字?
92. ?????*/??????public?void?insert(int?key)?{??
93. ????????TreeNode?parentNode?=?null;??????????TreeNode?newNode?=?new?TreeNode(key,?null,?null,?null);??
94. ????????TreeNode?pNode?=?root;??????????if?(root?==?null)?{??
95. ????????????root?=?newNode;??????????????return;??
96. ????????}??????????while?(pNode?!=?null)?{??
97. ????????????parentNode?=?pNode;??????????????if?(key?<?pNode.key)?{??
98. ????????????????pNode?=?pNode.leftChild;??????????????}?else?if?(key?>?pNode.key)?{??
99. ????????????????pNode?=?pNode.rightChild;??????????????}?else?{??
100. ????????????????//?树中已存在匹配给定关键字的结点，则什么都不做直接返回??????????????????return;??
101. ????????????}??????????}??
102. ????????if?(key?<?parentNode.key)?{??????????????parentNode.leftChild?=?newNode;??
103. ????????????newNode.parent?=?parentNode;??????????}?else?{??
104. ????????????parentNode.rightChild?=?newNode;??????????????newNode.parent?=?parentNode;??
105. ????????}????
106. ????}????
107. ????/**??????*?insert:?从二叉查找树中删除匹配给定关键字相应的树结点?
108. ?????*???????*?@param?key?
109. ?????*????????????给定关键字??????*/??
110. ????public?void?delete(int?key)?throws?Exception?{??????????TreeNode?pNode?=?search(key);??
111. ????????if?(pNode?==?null)?{??????????????throw?new?Exception("树中不存在要删除的关键字!");??
112. ????????}??????????delete(pNode);??
113. ????}????
114. ????/**??????*?delete:?从二叉查找树中删除给定的结点.?
115. ?????*???????*?@param?pNode?
116. ?????*????????????要删除的结点??????*??
117. ?????*????????????前置条件：?给定结点在二叉查找树中已经存在??????*?@throws?Exception?
118. ?????*/??????private?void?delete(TreeNode?pNode)?throws?Exception?{??
119. ????????if?(pNode?==?null)?{??????????????return;??
120. ????????}??????????if?(pNode.leftChild?==?null?&&?pNode.rightChild?==?null)?{?//?该结点既无左孩子结点，也无右孩子结点??
121. ????????????TreeNode?parentNode?=?pNode.parent;??????????????if?(pNode?==?parentNode.leftChild)?{??
122. ????????????????parentNode.leftChild?=?null;??????????????}?else?{??
123. ????????????????parentNode.rightChild?=?null;??????????????}??
124. ????????????return;??????????}??
125. ????????if?(pNode.leftChild?==?null?&&?pNode.rightChild?!=?null)?{?//?该结点左孩子结点为空，右孩子结点非空??????????????TreeNode?parentNode?=?pNode.parent;??
126. ????????????if?(pNode?==?parentNode.leftChild)?{??????????????????parentNode.leftChild?=?pNode.rightChild;??
127. ????????????????pNode.rightChild.parent?=?parentNode;??????????????}?else?{??
128. ????????????????parentNode.rightChild?=?pNode.rightChild;??????????????????pNode.rightChild.parent?=?parentNode;??
129. ????????????}??????????????return;??
130. ????????}??????????if?(pNode.leftChild?!=?null?&&?pNode.rightChild?==?null)?{?//?该结点左孩子结点非空，右孩子结点为空??
131. ????????????TreeNode?parentNode?=?pNode.parent;??????????????if?(pNode?==?parentNode.leftChild)?{??
132. ????????????????parentNode.leftChild?=?pNode.leftChild;??????????????????pNode.rightChild.parent?=?parentNode;??
133. ????????????}?else?{??????????????????parentNode.rightChild?=?pNode.leftChild;??
134. ????????????????pNode.rightChild.parent?=?parentNode;??????????????}??
135. ????????????return;??????????}??
136. ????????//?该结点左右孩子结点均非空，则删除该结点的后继结点，并用该后继结点取代该结点??????????TreeNode?successorNode?=?successor(pNode);??
137. ????????delete(successorNode);??????????pNode.key?=?successorNode.key;??
138. ????}????
139. ????/**??????*?inOrderTraverseList:?获得二叉查找树的中序遍历结点列表?
140. ?????*???????*?@return?二叉查找树的中序遍历结点列表?
141. ?????*/??????public?List<TreeNode>?inOrderTraverseList()?{??
142. ????????if?(nodelist?!=?null)?{??????????????nodelist.clear();??
143. ????????}??????????inOrderTraverse(root);??
144. ????????return?nodelist;??????}??
145. ??????/**?
146. ?????*?inOrderTraverse:?对给定二叉查找树进行中序遍历??????*??
147. ?????*?@param?root??????*????????????给定二叉查找树的根结点?
148. ?????*/??????private?void?inOrderTraverse(TreeNode?root)?{??
149. ????????if?(root?!=?null)?{??????????????inOrderTraverse(root.leftChild);??
150. ????????????nodelist.add(root);??????????????inOrderTraverse(root.rightChild);??
151. ????????}??????}??
152. ??????/**?
153. ?????*?toStringOfOrderList:?获取二叉查找树中关键字的有序列表??????*??
154. ?????*?@return?二叉查找树中关键字的有序列表??????*/??
155. ????public?String?toStringOfOrderList()?{??????????StringBuilder?sbBuilder?=?new?StringBuilder("?[?");??
156. ????????for?(TreeNode?p?:?inOrderTraverseList())?{??????????????sbBuilder.append(p.key);??
157. ????????????sbBuilder.append("?");??????????}??
158. ????????sbBuilder.append("]");??????????return?sbBuilder.toString();??
159. ????}????
160. ????/**??????*?获取该二叉查找树的字符串表示?
161. ?????*/??????public?String?toString()?{??
162. ????????StringBuilder?sbBuilder?=?new?StringBuilder("?[?");??????????for?(TreeNode?p?:?inOrderTraverseList())?{??
163. ????????????sbBuilder.append(p);??????????????sbBuilder.append("?");??
164. ????????}??????????sbBuilder.append("]");??
165. ????????return?sbBuilder.toString();??????}??
166. ??????public?TreeNode?getRoot()?{??
167. ????????return?root;??????}??
168. ??????public?static?void?testNode(BinarySearchTree?bst,?TreeNode?pNode)??
169. ????????????throws?Exception?{??????????System.out.println("本结点:?"?+?pNode);??
170. ????????System.out.println("前趋结点:?"?+?bst.precessor(pNode));??????????System.out.println("后继结点:?"?+?bst.successor(pNode));??
171. ????}????
172. ????public?static?void?testTraverse(BinarySearchTree?bst)?{??????????System.out.println("二叉树遍历："?+?bst);??
173. ????????System.out.println("二叉查找树转换为有序列表:?"?+?bst.toStringOfOrderList());??????}??
174. ??????public?static?void?main(String[]?args)?{??
175. ????????try?{??????????????BinarySearchTree?bst?=?new?BinarySearchTree();??
176. ????????????System.out.println("查找树是否为空？?"?+?(bst.isEmpty()???"是"?:?"否"));??????????????int[]?keys?=?new?int[]?{?15,?6,?18,?3,?7,?13,?20,?2,?9,?4?};??
177. ????????????for?(int?key?:?keys)?{??????????????????bst.insert(key);??
178. ????????????}??????????????System.out.println("查找树是否为空？?"?+?(bst.isEmpty()???"是"?:?"否"));??
179. ????????????TreeNode?minkeyNode?=?bst.minElemNode(bst.getRoot());??????????????System.out.println("最小关键字：?"?+?minkeyNode.getKey());??
180. ????????????testNode(bst,?minkeyNode);??????????????TreeNode?maxKeyNode?=?bst.maxElemNode(bst.getRoot());??
181. ????????????System.out.println("最大关键字：?"?+?maxKeyNode.getKey());??????????????testNode(bst,?maxKeyNode);??
182. ????????????System.out.println("根结点关键字：?"?+?bst.getRoot().getKey());??????????????testNode(bst,?bst.getRoot());??
183. ????????????testTraverse(bst);??????????????System.out.println("******************************?");??
184. ????????????testTraverse(bst);??????????}?catch?(Exception?e)?{??
185. ????????????System.out.println(e.getMessage());??????????????e.printStackTrace();??
186. ????????}??????}??
187. ??}?