二叉查找树 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

  • 1
  • 2
  • 下一页

相关内容