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);
  }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。