二叉查找樹 Java實現

1. package ctgu.sugite.content.character12;
3. import ctgu.sugite.content.character10.LinkedStack;
5. public class BinarySearchTree<E> {
7. private static class TreeNode<E> {
8. E key;
9. TreeNode<E> lChild;
10. TreeNode<E> rChild;
11. TreeNode<E> parent;
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. }
22. private TreeNode<E> root = new TreeNode<E>(null, null, null, null);
24. public BinarySearchTree() {
25. root.parent = root.lChild = root.rChild = root;
26. }
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. }
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. }
54. public TreeNode<E> treeMinimum(TreeNode<E> tn) {// 樹中最小值
55. while (tn.lChild != null)
56. tn = tn.lChild;
57. return tn;
58. }
60. public TreeNode<E> treeMaximum(TreeNode<E> tn) {// 樹中最大值
61. while (tn.rChild != null)
62. tn = tn.rChild;
63. return tn;
64. }
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. }
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. }
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. }
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. }
137. public TreeNode<E> getRoot() {
138. return this.root;
139. }
141. public void setRoot(TreeNode<E> root) {
142. this.root = root;
143. }
145. @SuppressWarnings({ "unchecked" })
146. private int compare(E a, E b) {
147. return ((Comparable<E>) a).compareTo(b);
148. }
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