二叉查找樹 Java實現

1. package ctgu.sugite.content.character12;  
2.   
3. import ctgu.sugite.content.character10.LinkedStack;  
4.   
5. public class BinarySearchTree<E> {  
6.   
7.     private static class TreeNode<E> {  
8.         E key;  
9.         TreeNode<E> lChild;  
10.         TreeNode<E> rChild;  
11.         TreeNode<E> parent;  
12.   
13.         public TreeNode(E e, TreeNode<E> left, TreeNode<E> right,  
14.                 TreeNode<E> parent) {  
15.             this.key = e;  
16.             this.lChild = left;  
17.             this.rChild = right;  
18.             this.parent = parent;  
19.         }  
20.     }  
21.   
22.     private TreeNode<E> root = new TreeNode<E>(null, null, null, null);  
23.   
24.     public BinarySearchTree() {  
25.         root.parent = root.lChild = root.rChild = root;  
26.     }  
27.   
28.     public void treeInorder(TreeNode<E> tn) {// 非遞歸的中序遍歷   
29.         LinkedStack<TreeNode<E>> stack = new LinkedStack<TreeNode<E>>();  
30.         TreeNode<E> p = tn;  
31.         while (p != null || !stack.isEmpty()) {  
32.             if (p != null) {  
33.                 stack.push(p);  
34.                 p = p.lChild;  
35.             } else {  
36.                 p = stack.pop();  
37.                 System.out.print(p.key + " ");  
38.                 p = p.rChild;  
39.             }  
40.         }  
41.         System.out.println();  
42.     }  
43.   
44.     public TreeNode<E> treeSearch(TreeNode<E> tn, E e) {// 二叉查找   
45.         int result = compare(e, tn.key);  
46.         if (result == 0 || tn == null)  
47.             return tn;  
48.         if (result < 0)  
49.             return treeSearch(tn.lChild, e);  
50.         else  
51.             return treeSearch(tn.rChild, e);  
52.     }  
53.   
54.     public TreeNode<E> treeMinimum(TreeNode<E> tn) {// 樹中最小值   
55.         while (tn.lChild != null)  
56.             tn = tn.lChild;  
57.         return tn;  
58.     }  
59.   
60.     public TreeNode<E> treeMaximum(TreeNode<E> tn) {// 樹中最大值   
61.         while (tn.rChild != null)  
62.             tn = tn.rChild;  
63.         return tn;  
64.     }  
65.   
66.     public TreeNode<E> treeSuccessor(TreeNode<E> tn) {// 結點後繼   
67.         if (tn.rChild != null)  
68.             return treeMinimum(tn.rChild);  
69.         TreeNode<E> p = tn.parent;  
70.         while (p != null && tn == p.rChild) {  
71.             tn = p;  
72.             p = p.parent;  
73.         }  
74.         return p;  
75.     }  
76.   
77.     public TreeNode<E> treePredecessor(TreeNode<E> tn) {// 結點前趨   
78.         if (tn.lChild != null)  
79.             return treeMaximum(tn.lChild);  
80.         TreeNode<E> p = tn.parent;  
81.         while (p != null && tn == p.lChild) {  
82.             tn = p;  
83.             p = p.parent;  
84.         }  
85.         return p;  
86.     }  
87.   
88.     public void treeInsert(BinarySearchTree<E> tree, E e) {// 插入結點   
89.         TreeNode<E> z = new TreeNode<E>(e, null, null, null);  
90.         TreeNode<E> y = new TreeNode<E>(null, null, null, null);  
91.         TreeNode<E> x = tree.getRoot();  
92.         while (x.key != null) {  
93.             y = x;  
94.             if (compare(e, x.key) < 0)  
95.                 x = x.lChild;  
96.             else  
97.                 x = x.rChild;  
98.             if (x == null) {  
99.                 x = new TreeNode<E>(null, null, null, null);  
100.             }  
101.         }  
102.         z.parent = y;  
103.         if (y.key == null) {  
104.             tree.setRoot(z);  
105.         } else {  
106.             if (compare(e, y.key) < 0)  
107.                 y.lChild = z;  
108.             else  
109.                 y.rChild = z;  
110.         }  
111.     }  
112.   
113.     public TreeNode<E> treeDelete(BinarySearchTree<E> tree, E e) {// 刪除結點   
114.         TreeNode<E> z = treeSearch(tree.getRoot(), e);  
115.         TreeNode<E> y = new TreeNode<E>(null, null, null, null);  
116.         TreeNode<E> x = new TreeNode<E>(null, null, null, null);  
117.         if (z.lChild == null || z.rChild == null)  
118.             y = z;  
119.         else  
120.             y = treeSuccessor(z);  
121.         x = (y.lChild == null) ? y.rChild : y.lChild;  
122.         if (x != null)  
123.             x.parent = y.parent;  
124.         if (y.parent == null)  
125.             tree.setRoot(x);  
126.         else {  
127.             if (y == y.parent.lChild)  
128.                 y.parent.lChild = x;  
129.             else  
130.                 y.parent.rChild = x;  
131.         }  
132.         if (y != z)  
133.             z.key = y.key;  
134.         return y;  
135.     }  
136.   
137.     public TreeNode<E> getRoot() {  
138.         return this.root;  
139.     }  
140.   
141.     public void setRoot(TreeNode<E> root) {  
142.         this.root = root;  
143.     }  
144.   
145.     @SuppressWarnings({ "unchecked" })  
146.     private int compare(E a, E b) {  
147.         return ((Comparable<E>) a).compareTo(b);  
148.     }  
149.   
150.     public static void main(String[] args) {  
151.         BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();  
152.         int[] a = { 50, 9, 3, 78, 23, 0, 2, 4, 6, 6 };  
153.         for (int i = 0; i < a.length; i++) {  
154.             bst.treeInsert(bst, new Integer(a[i]));  
155.         }  
156.         bst.treeInorder(bst.getRoot());  
157.         bst.treeDelete(bst, new Integer(6));  
158.         bst.treeInorder(bst.getRoot());  
159.         bst.treeDelete(bst, new Integer(0));  
160.         bst.treeInorder(bst.getRoot());  
161.         System.out.println("root is :" + bst.getRoot().key);  
162.         System.out.println("root's successor is :"  
163.                 + bst.treeSuccessor(bst.getRoot()).key);  
164.         System.out.println("root's predecessor is :"  
165.                 + bst.treePredecessor(bst.getRoot()).key);  
166.         System.out.println("max value is :"  
167.                 + bst.treeMaximum(bst.getRoot()).key);  
168.         System.out.println("min value is :"  
169.                 + bst.treeMinimum(bst.getRoot()).key);  
170.     }  
171. }  

運行結果：

0 2 3 4 6 6 9 23 50 78 
0 2 3 4 6 9 23 50 78 
2 3 4 6 9 23 50 78 
root is :50
root's successor is :78
root's predecessor is :23
max value is :78
min value is :2