伸展树(三)之 Java的实现(五)
eNode(key,null,null)) == null)
283 return ;
284
285 // 插入节点
286 mRoot = insert(mRoot, z);
287 // 将节点(key)旋转为根节点
288 mRoot = splay(mRoot, key);
289 }
290
291 /*
292 * 删除结点(z)，并返回被删除的结点
293 *
294 * 参数说明：
295 * bst 伸展树
296 * z 删除的结点
297 */
298 private SplayTreeNode remove(SplayTreeNode tree, T key) {
299 SplayTreeNode x;
300
301 if (tree == null)
302 return null;
303
304 // 查找键值为key的节点，找不到的话直接返回。
305 if (search(tree, key) == null)
306 return tree;
307
308 // 将key对应的节点旋转为根节点。
309 tree = splay(tree, key);
310
311 if (tree.left != null) {
312 // 将"tree的前驱节点"旋转为根节点
313 x = splay(tree.left, key);
314 // 移除tree节点
315 x.right = tree.right;
316 }
317 else
318 x = tree.right;
319
320 tree = null;
321
322 return x;
323 }
324
325 public void remove(T key) {
326 mRoot = remove(mRoot, key);
327 }
328
329 /*
330 * 销毁伸展树
331 */
332 private void destroy(SplayTreeNode tree) {
333 if (tree==null)
334 return ;
335
336 if (tree.left != null)
337 destroy(tree.left);
338 if (tree.right != null)
339 destroy(tree.right);
340
341 tree=null;
342 }
343
344 public void clear() {
345 destroy(mRoot);
346 mRoot = null;
347 }
348
349 /*
350 * 打印"伸展树"
351 *
352 * key -- 节点的键值
353 * direction -- 0，表示该节点是根节点;
354 * -1，表示该节点是它的父结点的左孩子;
355 * 1，表示该节点是它的父结点的右孩子。
356 */
357 private void print(SplayTreeNode tree, T key, int direction) {
358
359 if(tree != null) {
360
361 if(direction==0) // tree是根节点
362 System.out.printf("%2d is root\n", tree.key);
363 else // tree是分支节点
364 System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==1 "right" : "left");
365
366 print(tree.left, tree.key, -1);
367 print(tree.right,tree.key, 1);
368 }
369 }
370
371 public void print() {
372 if (mRoot != null)
373 print(mRoot, mRoot.key, 0);
374 }
375 }
复制代码
伸展树的测试程序(SplayTreeTest.java)
复制代码
1 /**
2 * Java 语言: 伸展树
3 *
4 * @author skywang
5 * @date 2014/02/03
6 */
7 public class SplayTreeTest {
8
9 private static final int arr[] = {10,50,40,30,20,60};
10
11 public static void main(String[] args) {
12 int i, ilen;
13 SplayTree tree=new SplayTree();
14
15 System.out.print("== 依次添加: ");
16 ilen = arr.length;
17 for(i=0; i
18 System.out.print(arr[i]+" ");
19 tree.insert(arr[i]);
20 }
21
22 System.out.print("\n== 前序遍历: ");
23 tree.preOrder();
24
25 System.out.print("\n== 中序遍历: ");
26 tree.inOrder();
27
28 System.out.print("\n== 后序遍历: ");
29 tree.postOrder();
30 System.out.println();
31
32 System.out.println("== 最小值: "+ tree.minimum());
33 System.out.println("== 最大值: "+ tree.maximum());
34 System.out.println("== 树的详细信息: ");
35 tree.print();
36
37 i = 30;
38