伸展树(三)之 Java的实现(三)
reeNode left, SplayTreeNode right) {
23 this.key = key;
24 this.left = left;
25 this.right = right;
26 }
27 }
28
29 public SplayTree() {
30 mRoot=null;
31 }
32
33 /*
34 * 前序遍历"伸展树"
35 */
36 private void preOrder(SplayTreeNode tree) {
37 if(tree != null) {
38 System.out.print(tree.key+" ");
39 preOrder(tree.left);
40 preOrder(tree.right);
41 }
42 }
43
44 public void preOrder() {
45 preOrder(mRoot);
46 }
47
48 /*
49 * 中序遍历"伸展树"
50 */
51 private void inOrder(SplayTreeNode tree) {
52 if(tree != null) {
53 inOrder(tree.left);
54 System.out.print(tree.key+" ");
55 inOrder(tree.right);
56 }
57 }
58
59 public void inOrder() {
60 inOrder(mRoot);
61 }
62
63
64 /*
65 * 后序遍历"伸展树"
66 */
67 private void postOrder(SplayTreeNode tree) {
68 if(tree != null)
69 {
70 postOrder(tree.left);
71 postOrder(tree.right);
72 System.out.print(tree.key+" ");
73 }
74 }
75
76 public void postOrder() {
77 postOrder(mRoot);
78 }
79
80
81 /*
82 * (递归实现)查找"伸展树x"中键值为key的节点
83 */
84 private SplayTreeNode search(SplayTreeNode x, T key) {
85 if (x==null)
86 return x;
87
88 int cmp = key.compareTo(x.key);
89 if (cmp < 0)
90 return search(x.left, key);
91 else if (cmp > 0)
92 return search(x.right, key);
93 else
94 return x;
95 }
96
97 public SplayTreeNode search(T key) {
98 return search(mRoot, key);
99 }
100
101 /*
102 * (非递归实现)查找"伸展树x"中键值为key的节点
103 */
104 private SplayTreeNode iterativeSearch(SplayTreeNode x, T key) {
105 while (x!=null) {
106 int cmp = key.compareTo(x.key);
107
108 if (cmp < 0)
109 x = x.left;
110 else if (cmp > 0)
111 x = x.right;
112 else
113 return x;
114 }
115
116 return x;
117 }
118
119 public SplayTreeNode iterativeSearch(T key) {
120 return iterativeSearch(mRoot, key);
121 }
122
123 /*
124 * 查找最小结点：返回tree为根结点的伸展树的最小结点。
125 */
126 private SplayTreeNode minimum(SplayTreeNode tree) {
127 if (tree == null)
128 return null;
129
130 while(tree.left != null)
131 tree = tree.left;
132 return tree;
133 }
134
135 public T minimum() {
136 SplayTreeNode p = minimum(mRoot);
137 if (p != null)
138 return p.key;
139
140 return null;
141 }
142
143 /*
144 * 查找最大结点：返回tree为根结点的伸展树的最大结点。
145 */
146 private SplayTreeNode maximum(SplayTreeNode tree) {
147 if (tree == null)
148 return null;
149
150 while(tree.right != null)
151 tree = tree.right;
152 return tree;
153 }
154
155 public T maximum() {
156 SplayTreeNode p = maximum(mRoot);
157 if (p != null)
158 return p.key;
159
160 return null;
161 }
162
163 /*
164 * 旋转key对应的节点为根节点，并返回根节点。
165