1 import java.util.ArrayList;
  2 import java.util.List;
  3 
  4 public class BinarySearchTree {
  5 
  6     // 树的根结点
  7     private TreeNode root = null;
  8 
  9     // 遍历结点列表
 10     private List<TreeNode> nodelist = new ArrayList<TreeNode>();
 11 
 12     private class TreeNode {
 13 
 14         private int key;
 15         private TreeNode leftChild;
 16         private TreeNode rightChild;
 17         private TreeNode parent;
 18 
 19         public TreeNode(int key, TreeNode leftChild, TreeNode rightChild,
 20                 TreeNode parent) {
 21             this.key = key;
 22             this.leftChild = leftChild;
 23             this.rightChild = rightChild;
 24             this.parent = parent;
 25         }
 26 
 27         public int getKey() {
 28             return key;
 29         }
 30 
 31         public String toString() {
 32             String leftkey = (leftChild == null ? "" : String
 33                     .valueOf(leftChild.key));
 34             String rightkey = (rightChild == null ? "" : String
 35                     .valueOf(rightChild.key));
 36             return "(" + leftkey + " , " + key + " , " + rightkey + ")";
 37         }
 38 
 39     }
 40 
 41     /**
 42      * isEmpty: 判断二叉查找树是否为空；若为空，返回 true ，否则返回 false .
 43      * 
 44      */
 45     public boolean isEmpty() {
 46         if (root == null) {
 47             return true;
 48         } else {
 49             return false;
 50         }
 51     }
 52 
 53     /**
 54      * TreeEmpty: 对于某些二叉查找树操作(比如删除关键字)来说，若树为空，则抛出异常。
 55      */
 56     public void TreeEmpty() throws Exception {
 57         if (isEmpty()) {
 58             throw new Exception("树为空!");
 59         }
 60     }
 61 
 62     /**
 63      * search: 在二叉查找树中查询给定关键字
 64      * 
 65      * @param key
 66      *            给定关键字
 67      * @return 匹配给定关键字的树结点
 68      */
 69     public TreeNode search(int key) {
 70         TreeNode pNode = root;
 71         while (pNode != null && pNode.key != key) {
 72             if (key < pNode.key) {
 73                 pNode = pNode.leftChild;
 74             } else {
 75                 pNode = pNode.rightChild;
 76             }
 77         }
 78         return pNode;
 79     }
 80 
 81     /**
 82      * minElemNode: 获取二叉查找树中的最小关键字结点
 83      * 
 84      * @return 二叉查找树的最小关键字结点
 85      * @throws Exception
 86      *             若树为空，则抛出异常
 87      */
 88     public TreeNode minElemNode(TreeNode node) throws Exception {
 89         if (node == null) {
 90             throw new Exception("树为空！");
 91         }
 92         TreeNode pNode = node;
 93         while (pNode.leftChild != null) {
 94             pNode = pNode.leftChild;
 95         }
 96         return pNode;
 97     }
 98 
 99     /**
100      * maxElemNode: 获取二叉查找树中的最大关键字结点
101      * 
102      * @return 二叉查找树的最大关键字结点
103      * @throws Exception
104      *             若树为空，则抛出异常
105      */
106     public TreeNode maxElemNode(TreeNode node) throws Exception {
107         if (node == null) {
108             throw new Exception("树为空！");
109         }
110         TreeNode pNode = node;
111         while (pNode.rightChild != null) {
112             pNode = pNode.rightChild;
113         }
114         return pNode;
115     }
116 
117     /**
118      * successor: 获取给定结点在中序遍历顺序下的后继结点
119      * 
120      * @param node
121      *            给定树中的结点
122      * @return 若该结点存在中序遍历顺序下的后继结点，则返回其后继结点；否则返回 null
123      * @throws Exception
124      */
125     public TreeNode successor(TreeNode node) throws Exception {
126         if (node == null) {
127             return null;
128         }
129 
130         // 若该结点的右子树不为空，则其后继结点就是右子树中的最小关键字结点
131         if (node.rightChild != null) {
132             return minElemNode(node.rightChild);
133         }
134         // 若该结点右子树为空
135         TreeNode parentNode = node.parent;
136         while (parentNode != null && node == parentNode.rightChild) {
137             node = parentNode;
138             parentNode = parentNode.parent;
139         }
140         return parentNode;
141     }
142 
143     /**
144      * precessor: 获取给定结点在中序遍历顺序下的前趋结点
145      * 
146      * @param node
147      *            给定树中的结点
148      * @return 若该结点存在中序遍历顺序下的前趋结点，则返回其前趋结点；否则返回 null
149      * @throws Exception
150      */
151     public TreeNode precessor(TreeNode node) throws Exception {
152         if (node == null) {
153             return null;
154         }
155 
156         // 若该结点的左子树不为空，则其前趋结点就是左子树中的最大关键字结点
157         if (node.leftChild != null) {
158             return maxElemNode(node.leftChild);
159         }
160         // 若该结点左子树为空
161         TreeNode parentNode = node.parent;
162         while (parentNode != null && node == parentNode.leftChild) {
163             node = parentNode;
164             parentNode = parentNode.parent;
165         }
166         return parentNode;
167     }
168 
169     /**
170      * insert: 将给定关键字插入到二叉查找树中
171      * 
172      * @param key
173      *            给定关键字
174      */
175     public void insert(int key) {
176         TreeNode parentNode = null;
177         TreeNode newNode = new TreeNode(key, null, null, null);
178         TreeNode pNode = root;
179         if (root == null) {
180             root = newNode;
181             return;
182         }
183         while (pNode != null) {
184             parentNode = pNode;
185             if (key < pNode.key) {
186                 pNode = pNode.leftChild;
187             } else if (key > pNode.key) {
188                 pNode = pNode.rightChild;
189             } else {
190                 // 树中已存在匹配给定关键字的结点，则什么都不做直接返回
191                 return;
192             }
193         }
194         if (key < parentNode.key) {
195             parentNode.leftChild = newNode;
196             newNode.parent = parentNode;
197         } else {
198             parentNode.rightChild = newNode;
199             newNode.parent = parentNode;
200         }
201 
202     }
203 
204     /**
205      * insert: 从二叉查找树中删除匹配给定关键字相应的树结点
206      * 
207      * @param key
208      *            给定关键字
209      */
210     public void delete(int key) throws Exception {
211         TreeNode pNode = search(key);
212         if (pNode == null) {
213             throw new Exception("树中不存在要删除的关键字!");
214         }
215         delete(pNode);
216     }
217 
218     /**
219      * delete: 从二叉查找树中删除给定的结点.
220      * 
221      * @param pNode
222      *            要删除的结点
223      * 
224      *            前置条件： 给定结点在二叉查找树中已经存在
225      * @throws Exception
226      */
227     private void delete(TreeNode pNode) throws Exception {
228         if (pNode == null) {
229             return;
230         }
231         if (pNode.leftChild == null && pNode.rightChild == null) { // 该结点既无左孩子结点，也无右孩子结点
232             TreeNode parentNode = pNode.parent;
233             if (pNode == parentNode.leftChild) {
234                 parentNode.leftChild = null;
235             } else {
236                 parentNode.rightChild = null;
237             }
238             return;
239         }
240         if (pNode.leftChild == null && pNode.rightChild != null) { // 该结点左孩子结点为空，右孩子结点非空
241             TreeNode parentNode = pNode.parent;
242             if (pNode == parentNode.leftChild) {
243                 parentNode.leftChild = pNode.rightChild;
244                 pNode.rightChild.parent = parentNode;
245             } else {
246                 parentNode.rightChild = pNode.rightChild;
247                 pNode.rightChild.parent = parentNode;
248             }
249             return;
250         }
251         if (pNode.leftChild != null && pNode.rightChild == null) { // 该结点左孩子结点非空，右孩子结点为空
252             TreeNode parentNode = pNode.parent;
253             if (pNode == parentNode.leftChild) {
254                 parentNode.leftChild = pNode.leftChild;
255                 pNode.rightChild.parent = parentNode;
256             } else {
257                 parentNode.rightChild = pNode.leftChild;
258                 pNode.rightChild.parent = parentNode;
259             }
260             return;
261         }
262         // 该结点左右孩子结点均非空，则删除该结点的后继结点，并用该后继结点取代该结点
263         TreeNode successorNode = successor(pNode);
264         delete(successorNode);
265         pNode.key = successorNode.key;
266     }
267 
268     /**
269      * inOrderTraverseList: 获得二叉查找树的中序遍历结点列表
270      * 
271      * @return 二叉查找树的中序遍历结点列表
272      */
273     public List<TreeNode> inOrderTraverseList() {
274         if (nodelist != null) {
275             nodelist.clear();
276         }
277         inOrderTraverse(root);
278         return nodelist;
279     }
280 
281     /**
282      * inOrderTraverse: 对给定二叉查找树进行中序遍历
283      * 
284      * @param root
285      *            给定二叉查找树的根结点
286      */
287     private void inOrderTraverse(TreeNode root) {
288         if (root != null) {
289             inOrderTraverse(root.leftChild);
290             nodelist.add(root);
291             inOrderTraverse(root.rightChild);
292         }
293     }
294 
295     /**
296      * toStringOfOrderList: 获取二叉查找树中关键字的有序列表
297      * 
298      * @return 二叉查找树中关键字的有序列表
299      */
300     public String toStringOfOrderList() {
301         StringBuilder sbBuilder = new StringBuilder(" [ ");
302         for (TreeNode p : inOrderTraverseList()) {
303             sbBuilder.append(p.key);
304             sbBuilder.append(" ");
305         }
306         sbBuilder.append("]");
307         return sbBuilder.toString();
308     }
309 
310     /**
311      * 获取该二叉查找树的字符串表示
312      */
313     public String toString() {
314         StringBuilder sbBuilder = new StringBuilder(" [ ");
315         for (TreeNode p : inOrderTraverseList()) {
316             sbBuilder.append(p);
317             sbBuilder.append(" ");
318         }
319         sbBuilder.append("]");
320         return sbBuilder.toString();
321     }
322 
323     public TreeNode getRoot() {
324         return root;
325     }
326 
327     public static void testNode(BinarySearchTree bst, TreeNode pNode)
328             throws Exception {
329         System.out.println("本结点: " + pNode);
330         System.out.println("前趋结点: " + bst.precessor(pNode));
331         System.out.println("后继结点: " + bst.successor(pNode));
332     }
333 
334     public static void testTraverse(BinarySearchTree bst) {
335         System.out.println("二叉树遍历：" + bst);
336         System.out.println("二叉查找树转换为有序列表: " + bst.toStringOfOrderList());
337     }
338 
339     public static void main(String[] args) {
340         try {
341             BinarySearchTree bst = new BinarySearchTree();
342             System.out.println("查找树是否为空？ " + (bst.isEmpty() ? "是" : "否"));
343             int[] keys = new int[] { 15, 6, 18, 3, 7, 13, 20, 2, 9, 4 };
344             for (int key : keys) {
345                 bst.insert(key);
346             }
347             System.out.println("查找树是否为空？ " + (bst.isEmpty() ? "是" : "否"));
348             TreeNode minkeyNode = bst.minElemNode(bst.getRoot());
349             System.out.println("最小关键字： " + minkeyNode.getKey());
350             testNode(bst, minkeyNode);
351             TreeNode maxKeyNode = bst.maxElemNode(bst.getRoot());
352             System.out.println("最大关键字： " + maxKeyNode.getKey());
353             testNode(bst, maxKeyNode);
354             System.out.println("根结点关键字： " + bst.getRoot().getKey());
355             testNode(bst, bst.getRoot());
356             testTraverse(bst);
357             System.out.println("****************************** ");
358             testTraverse(bst);
359         } catch (Exception e) {
360             System.out.println(e.getMessage());
361             e.printStackTrace();
362         }
363     }
364 
365 }