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

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

# java  # 二叉查找树  # Java 实现二叉搜索树的查找、插入、删除、遍历  # 二叉搜索树实例练习  # Java创建二叉搜索树  # 实现搜索  # 插入  # 删除的操作实例  # 子树  # 才会  # 出现在  # 设为  # 则在  # 键值  # 也要  # 没有任何  # 上一  # 并将  # 很重要  # 不存在  # 将被  # 它会  # 大家分享  # 具体内容  # 大家多多  # 以该  # 有两个  # 收集器 

相关文章： 齐河建站公司：营销型网站建设与SEO优化双核驱动策略  北京营销型网站制作公司,可以用python做一个营销推广网站吗？  清除minerd进程的简单方法  桂林网站制作公司有哪些,桂林马拉松怎么报名？  seo网站制作优化,网站SEO优化步骤有哪些？  购物网站制作公司有哪些,哪个购物网站比较好？  高防服务器租用指南：配置选择与快速部署攻略  建站一年半SEO优化实战指南：核心词挖掘与长尾流量提升策略  建站之星后台搭建步骤解析：模板选择与产品管理实操指南  用v-html解决Vue.js渲染中html标签不被解析的问题  建站之星上传入口如何快速找到？  北京专业网站制作设计师招聘,北京白云观官方网站？  江苏网站制作公司有哪些,江苏书法考级官方网站？  如何快速辨别茅台真假？关键步骤解析  矢量图网站制作软件,用千图网的一张矢量图做公司app首页，该网站并未说明版权等问题，这样做算不算侵权？应该如何解决？  小视频制作网站有哪些,有什么看国内小视频的网站，求推荐？  创业网站制作流程,创业网站可靠吗？  赚钱网站制作软件,建一个网站怎样才能赚钱?是如何盈利的？  建站之星官网登录失败？如何快速解决？  ,有什么在线背英语单词效率比较高的网站？  如何获取免费开源的自助建站系统源码？  购物网站制作费用多少,开办网上购物网站，需要办理哪些手续？  已有域名和空间，如何快速搭建网站？  如何快速搭建虚拟主机网站？新手必看指南  javascript中的try catch异常捕获机制用法分析  如何在宝塔面板创建新站点？  公司网站制作费用多少,为公司建立一个网站需要哪些费用？  c# 服务器GC和工作站GC的区别和设置  如何通过商城自助建站源码实现零基础高效建站？  香港服务器网站生成指南：免费资源整合与高速稳定配置方案  平台云上自助建站如何快速打造专业网站？  新网站制作渠道有哪些,跪求一个无线渠道比较强的小说网站，我要发表小说？  潍坊网站制作公司有哪些,潍坊哪家招聘网站好？  无锡制作网站公司有哪些,无锡优八网络科技有限公司介绍？  零服务器AI建站解决方案：快速部署与云端平台低成本实践  c# F# 的 MailboxProcessor 和 C# 的 Actor 模型  云南网站制作公司有哪些,云南最好的招聘网站是哪个？  制作宣传网站的软件,小红书可以宣传网站吗？  电商网站制作价格怎么算,网上拍卖流程以及规则？  如何快速搭建响应式可视化网站？  网站专业制作公司,网站编辑是做什么的？好做吗？工作前景如何？  盐城做公司网站,江苏电子版退休证办理流程？  我的世界制作壁纸网站下载,手机怎么换我的世界壁纸？  详解免费开源的DotNet二维码操作组件ThoughtWorks.QRCode（.NET组件介绍之四）  如何选择域名并搭建高效网站？  交易网站制作流程,我想开通一个网站，注册一个交易网址，需要那些手续？  北京制作网站的公司,北京铁路集团官方网站？  ,交易猫的商品怎么发布到网站上去？  广州网站制作的公司,现在专门做网站的公司有没有哪几家是比较好的，性价比高，模板也多的？  如何基于PHP生成高效IDC网络公司建站源码？