java二叉查找树的实现代码

本文实例为大家分享了java二叉查找树的具体代码，供大家参考，具体内容如下

package 查找;

import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.StdOut;

public class BST<Key extends Comparable<Key>, Value> {
 private class Node {
   private Key key; // 键
   private Value value;// 值
   private Node left, right; // 指向子树的链接
   private int n; // 以该节点为根的子树中的节点总数

public Node(Key key, Value val, int n) {
     this.key = key;
     this.value = val;
     this.n = n;
   }
 }

private Node root;

public int size() {
   return size(root);
 }

private int size(Node x) {
   if (x == null)
     return 0;
   else
     return x.n;
 }

/**
  * 如果树是空的，则查找未命中 如果被查找的键小于根节点，则在左子树中继续查找 如果被查找的键大于根节点，则在右子树中继续查找
  * 如果被查找的键和根节点的键相等，查找命中
  *
  * @param key
  * @return
  */
 public Value get(Key key) {
   return get(root, key);
 }

private Value get(Node x, Key key) {
   if (x == null)
     return null;
   int cmp = key.compareTo(x.key);
   if (cmp < 0)
     return get(x.left, key);
   else if (cmp > 0)
     return get(x.right, key);
   else
     return x.value;
 }

/**
  * 二叉查找树的一个很重要的特性就是插入的实现难度和查找差不多。 当查找到一个不存在与树中的节点（null）时，new 新节点，并将上一路径指向该节点
  *
  * @param key
  * @param val
  */
 public void put(Key key, Value val) {
   root = put(root, key, val);
 }

private Node put(Node x, Key key, Value val) {
   if (x == null)
     return new Node(key, val, 1);
   int cmp = key.compareTo(x.key);
   if (cmp < 0)
     x.left = put(x.left, key, val);
   else if (cmp > 0)
     x.right = put(x.right, key, val);
   else
     x.value = val;
   x.n = size(x.left) + size(x.right); // 要及时更新节点的子树数量
   return x;
 }

public Key min() {
   return min(root).key;
 }

private Node min(Node x) {
   if (x.left == null)
     return x;
   return min(x.left);
 }

public Key max() {
   return max(root).key;
 }

private Node max(Node x) {
   if (x.right == null)
     return x;
   return min(x.right);
 }

/**
  * 向下取整：找出小于等于该键的最大键
  *
  * @param key
  * @return
  */
 public Key floor(Key key) {
   Node x = floor(root, key);
   if (x == null)
     return null;
   else
     return x.key;
 }

/**
  * 如果给定的键key小于二叉查找树的根节点的键，那么小于等于key的最大键一定出现在根节点的左子树中
  * 如果给定的键key大于二叉查找树的根节点，那么只有当根节点右子树中存在大于等于key的节点时，
  * 小于等于key的最大键才会出现在右子树中，否则根节点就是小于等于key的最大键
  *
  * @param x
  * @param key
  * @return
  */
 private Node floor(Node x, Key key) {
   if (x == null)
     return null;
   int cmp = key.compareTo(x.key);
   if (cmp == 0)
     return x;
   else if (cmp < 0)
     return floor(x.left, key);
   else {
     Node t = floor(x.right, key);
     if (t == null)
       return x;
     else
       return t;
   }
 }

/**
  * 向上取整：找出大于等于该键的最小键
  *
  * @param key
  * @return
  */
 public Key ceiling(Key key) {
   Node x = ceiling(root, key);
   if (x == null)
     return null;
   else
     return x.key;
 }

/**
  * 如果给定的键key大于二叉查找树的根节点的键，那么大于等于key的最小键一定出现在根节点的右子树中
  * 如果给定的键key小于二叉查找树的根节点，那么只有当根节点左子树中存在大于等于key的节点时，
  * 大于等于key的最小键才会出现在左子树中，否则根节点就是大于等于key的最小键
  *
  * @param x
  * @param key
  * @return
  */
 private Node ceiling(Node x, Key key) {
   if (x == null)
     return null;
   int cmp = key.compareTo(x.key);
   if (cmp == 0)
     return x;
   else if (cmp > 0) {
     return ceiling(x.right, key);
   } else {
     Node t = floor(x.left, key);
     if (t == null)
       return x;
     else
       return t;
   }
 }

/**
  * 选择排名为k的节点
  *
  * @param k
  * @return
  */
 public Key select(int k) {
   return select(root, k).key;
 }

private Node select(Node x, int k) {
   if (x == null)
     return null;
   int t = size(x.left);
   if (t > k)
     return select(x.left, k);
   else if (t < k)
     return select(x.right, k - t - 1);// 根节点也要排除掉
   else
     return x;
 }

/**
  * 查找给定键值的排名
  *
  * @param key
  * @return
  */
 public int rank(Key key) {
   return rank(key, root);
 }

private int rank(Key key, Node x) {
   if (x == null)
     return 0;
   int cmp = key.compareTo(x.key);
   if (cmp < 0)
     return rank(key, x.left);
   else if (cmp > 0)
     return 1 + size(x.left) + rank(key, x.right);
   else
     return size(x.left);
 }
 /**
  * 删除最小键值对
  */
 public void deleteMin(){
   root = deleteMin(root);
 }
 /**
  * 不断深入根节点的左子树直到遇见一个空链接，然后将指向该节点的链接指向该结点的右子树
  * 此时已经没有任何链接指向要被删除的结点，因此它会被垃圾收集器清理掉
  * @param x
  * @return
  */
 private Node deleteMin(Node x){
   if(x.left == null) return x.right;
   x.left = deleteMin(x.left);
   x.n = size(x.left)+size(x.right) + 1;
   return x;
 }

public void deleteMax(){
   root = deleteMax(root);
 }
 private Node deleteMax(Node x){
   if(x.right == null ) return x.left;
   x.right = deleteMax(x.right);
   x.n = size(x.left)+size(x.right) + 1;
   return x;
 }

public void delete(Key key){
   root = delete(root,key);
 }
 private Node delete(Node x, Key key){
   if(x == null) return null;
   int cmp = key.compareTo(x.key);
   if(cmp < 0) x.left = delete(x.left,key);
   else if(cmp > 0) x.right = delete(x.right,key);
   else{
     if(x.right == null) return x.left;
     if(x.left == null ) return x.right;
     /**
      * 如果被删除节点有两个子树，将被删除节点暂记为t
      * 从t的右子树中选取最小的节点x，将这个节点x的左子树设为t的左子树
      * 这个节点x的右子树设为t的右子树中删除了最小节点的子树，这样就成功替换了t的位置
      */
     Node t = x;
     x = min(t.right);
     x.left = t.left;
     x.right = deleteMin(t.right);
   }
   x.n = size(x.left) + size(x.right) +1;
   return x;
 }

public void print(){
   print(root);
 }
 private void print(Node x){
   if(x == null ) return;
   print(x.left);
   StdOut.println(x.key);
   print(x.right);
 }

public Iterable<Key> keys(){
   return keys(min(),max());
 }
 public Iterable<Key> keys(Key lo, Key hi){
   Queue<Key> queue = new Queue<Key>();
   keys(root, queue, lo, hi);
   return queue;
 }
 private void keys(Node x, Queue<Key> queue, Key lo, Key hi){
   if(x == null) return;
   int cmplo = lo.compareTo(x.key);
   int cmphi = lo.compareTo(x.key);
   if(cmplo < 0 ) keys(x.left,queue,lo,hi);
   if(cmplo <= 0 && cmphi >= 0) queue.enqueue(x.key);
   if(cmphi > 0 ) keys(x.right,queue,lo,hi);
 }
}

来源：http://www.cnblogs.com/evasean/p/7327278.html