史上最全二叉查找树详解——带详细图解_Θ花蘿ω的博客-程序员秘密_二叉查找树

技术标签:   java  数据结构  

1、二叉查找树的性质与规则

        若一个结点的左子树不为空,则它左子树上所有的结点都小于该结点;若一个结点的右子树的不为空,则它右子树上所有的结点都大于该结点

2、二叉查找树的创建

a、二叉查找树的结点类

public class Node{
        public Key key;//存储键
        private Value value;//存储值
        
        public Node left;//记录左子结点
        
        public Node right;//记录右子结点
        
        public Node(Key key,Value value,Node left,Node right) {
        	this.key = key;
        	this.value = value;
        	this.left = left;
        	this.right = right;
        }
}

b、二叉查找树实现

插入方法(put)实现思想:

  •         如果当前书中没有任何一个结点,则直接把新节点当做根节点使用
  •         如果当前树不为空,则从根节点开始:
  •         如果新结点的key小于当前结点的key,则继续找当前结点的左子结点
  •         如果新结点的key大于当前结点的key,则继续找当前结点的右子结点
  •         如果新结点的key等于当前结点的key,则树中已经存在这样的结点,替换该结点的value值

流程图如下:

查询(get)实现思想:

        从根节点开始:

  •         如果要查询的key小于当前结点的key,则继续找当前结点的左子结点
  •         如果要查询的key大于当前结点的key,则继续找当前结点的右子结点
  •         如果要查询的key等于当前结点的key,则返回当前结点的value

删除方法delete实现思想:

  •         找到被删除结点
  •         找到被删除结点右子树的最小结点minNode
  •         删除右子树中的最小结点
  •         让被删除结点的左子树称为最小结点minNode的左子树,让被删除结点的右子树称为最小结点minNode的右子树
  •         让被删除结点的父节点指向最小结点minNode

完整代码



//二叉树代码
class BinaryTree<Key extends Comparable<Key>, Value> {
  //记录根结点
  private Node root;
  //记录树中元素的个数
  private int N;
  //获取树中元素的个数
  public int size() {
      return N;
  }
  //向树中添加元素key-value
  public void put(Key key, Value value) {
      root = put(root, key, value);
  }
  //向指定的树x中添加key-value,并返回添加元素后新的树
  private Node put(Node x, Key key, Value value) {
      if (x == null) {
          //个数+1
          N++;
          return new Node(key, value, null, null);
      }
      int cmp = key.compareTo(x.key);
      if (cmp > 0) {
          //新结点的key大于当前结点的key,继续找当前结点的右子结点
          x.right = put(x.right, key, value);
      } else if (cmp < 0) {
          //新结点的key小于当前结点的key,继续找当前结点的左子结点
          x.left = put(x.left, key, value);
      } else {
          //新结点的key等于当前结点的key,把当前结点的value进行替换
          x.value = value;
      }
      return x;
  }
  //查询树中指定key对应的value
  public Value get(Key key) {
      return get(root, key);
  }
  //从指定的树x中,查找key对应的值
  public Value get(Node x, Key key) {
      if (x == null) {
          return null;
      }
      int cmp = key.compareTo(x.key);
      if (cmp > 0) {
          //如果要查询的key大于当前结点的key,则继续找当前结点的右子结点;
          return get(x.right, key);
      } else if (cmp < 0) {
          //如果要查询的key小于当前结点的key,则继续找当前结点的左子结点;
          return get(x.left, key);
      } else {
          //如果要查询的key等于当前结点的key,则树中返回当前结点的value。
          return x.value;
      }
  }
  //删除树中key对应的value
  public void delete(Key key) {
      root = delete(root, key);
  }
  //删除指定树x中的key对应的value,并返回删除后的新树
  public Node delete(Node x, Key key) {
      if (x == null) {
          return null;
      }
      int cmp = key.compareTo(x.key);
      if (cmp > 0) {
          //新结点的key大于当前结点的key,继续找当前结点的右子结点
          x.right = delete(x.right, key);
      } else if (cmp < 0) {
          //新结点的key小于当前结点的key,继续找当前结点的左子结点
          x.left = delete(x.left, key);
      } else {
          //新结点的key等于当前结点的key,当前x就是要删除的结点
          //1.如果当前结点的右子树不存在,则直接返回当前结点的左子结点
          if (x.right == null) {
              return x.left;
          }
          //2.如果当前结点的左子树不存在,则直接返回当前结点的右子结点
          if (x.left == null) {
              return x.right;
          }
          //3.当前结点的左右子树都存在
          //3.1找到右子树中最小的结点
          Node minNode = x.right;
          while (minNode.left != null) {
              minNode = minNode.left;
          }
          //3.2删除右子树中最小的结点
          Node n = x.right;
          while (n.left != null) {
              if (n.left.left == null) {
                  n.left = null;
              } else {
                  n = n.left;
              }
          }
          //3.3让被删除结点的左子树称为最小结点minNode的左子树,让被删除结点的右子树称为最小结点minNode的右子树
          minNode.left = x.left;
          minNode.right = x.right;
          //3.4让被删除结点的父节点指向最小结点minNode
          x = minNode;
          //个数-1
          N--;
      }
      return x;
  }
  private class Node {
      //存储键
      public Key key;
      //存储值
      private Value value;
      //记录左子结点
      public Node left;
      //记录右子结点
      public Node right;
      public Node(Key key, Value value, Node left, Node right) {
          this.key = key;
          this.value = value;
          this.left = left;
          this.right = right;
      }
  }
}
//测试代码
public class Test {
  public static void main(String[] args) throws Exception {
      BinaryTree<Integer, String> bt = new BinaryTree<>();
      bt.put(4, "二哈");
      bt.put(1, "张三");
      bt.put(3, "李四");
      bt.put(5, "王五");
      System.out.println(bt.size());
      bt.put(1,"老三");
      System.out.println(bt.get(4));
      bt.put(2, "小屋");
      System.out.println(bt.size());
      bt.delete(2);
      System.out.println(bt.size());
  }
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/CSDN_little_H/article/details/125696347

智能推荐

jQuery日期选择插件WdatePicker的使用方法_Emotional_p的博客-程序员秘密_jquery wdate

1.跨无限级框架显示无论你把日期控件放在哪里,你都不需要担心会被外层的iframe所遮挡进而影响客户体验,因为My97日期控件是可以跨无限级框架显示的示例2-7 跨无限级框架演示可无限跨越框架iframe,无论怎么嵌套框架都不必担心了,即使有滚动条也不怕2.民国年日历和其他特殊日历当年份格式设置为yyy格式时,利用年份差量属性yearOffset(默认值1911民国元年),可实现民国年日历和其他特殊日历示例2-8 民国年演示&lt;input type=”text” id=”..

VUE 脚手架 cli4 npm install -g @vue/cli 安装报错 常见踩坑_杰森% 玉儿的博客-程序员秘密

VUE脚手架安装踩坑全局模式下npm install -g @vue/cli可能出现的错误如果报出npm不是内部命令的话,证明没有安装node.js需要在nodejs的官网去下载它用vue -V查看vue的版本时报错,此时要注意后面的V是大写如果错误的提示为 ERR:path:‘某个文件的路径’,说明在安装这个脚手架之前,有其他跟这个脚手架有关的东西被安装了;只需要将path下面指定的文件删掉重新安装即可例如以下错误解决方法用管理员身份打开cmd,输入命令npm clean cache –for

前馈神经网络(Feedforward neural network)_zhangzzqliumin的博客-程序员秘密_前馈网络

前馈神经网络,是一种最简单的神经网络,各神经元分层排列,每个神经元只与前一层的神经元相连。接收前一层的输出,并输出给下一层,各层间没有反馈。是应用最广泛、发展最迅速的人工神经网络之一。研究从20世纪60年代开始,理论研究和实际应用达到了很高的水平。

QEMU+gdb调试Linux内核全过程_jasonLee_lijiaqi的博客-程序员秘密_qemu调试内核

1、编译源码(Linux kernel 4.6.2)make menuconfig执行make menuconfig时报错缺少库文件需要安装依赖库sudo aptitab instab libncurses5-dev首先编译内核,编译内核时注意要选两个选项。(注意:除此之外kernel hacking选项下其他的选项都不要选,否则会出现断点无法拦截的情况。这个说法有待验证)...

vue3.0踩坑记录_PinkSir的博客-程序员秘密_vue3.0 坑

1.vue3需注意model与ref不能同名,在使用elementplus时发现el-input无法输入,查看后发现由于同名导致2.vue3 中不再支持 extend 方法,可使用vue3中createApp挂载未挂载的组件,未挂载组件中如有使用第三方插件,需重新导入(暂不清楚其他方式)const components = [ElDropdown, ElDropdownItem, ElDropdownMenu];const app = createApp(speedcom);components.f

随便推点

目标5000万日活,Pwnk欲打造下一代年轻人的“迪士尼乐园”_AImatters的博客-程序员秘密

头部出海游戏厂商FunPlus正在孵化一种视频流游戏新物种。

时间的加减运算_zhx0114的博客-程序员秘密_时间加减

package com.zhx;import java.text.ParseException;import java.text.SimpleDateFormat;import java.util.Calendar;import java.util.Date;public class TimeMathematical{ public static void main(Str...

proteus中 基于STC89C51的HDG12864F-3显示器仿真_Raymond垒垒的博客-程序员秘密

最近接了个项目涉及到使用HDG12864F-3 即128*64分辨率显示屏的使用.抽时间顺便谢谢博客吧~- first step: 分析篇百度显示屏技术手册:https://wenku.baidu.com/view/049ff3c5da38376bae1fae0d.html(百度仅有的技术手册…有点老,凑合着用吧)教大家一下芯片手册正确的打开步骤:1.查看芯片结构及引脚图:2.查...

activeMQ消息队列详细配置_ip15988的博客-程序员秘密

Spring整合activeMQ方法 1.导入坐标&amp;lt;dependency&amp;gt; &amp;lt;groupId&amp;gt;org.apache.activemq&amp;lt;/groupId&amp;gt; &amp;lt;artifactId&amp;gt;activemq-all&amp;lt;/artifactId&amp;gt; &amp;lt;version&amp;gt;5.14.0&amp;lt;/...

【吃鸡】毒圈展示_weixin_30538029的博客-程序员秘密

&lt;1&gt;2种圈,1个场景,1个UI&lt;2&gt;场景毒圈美术制作圆柱形网格,上下剔除,圆柱侧面面越多越好(内存渲染会多占用点)shader实现:UV动画(写得不好)Shader "wk/Particles/AdditiveGas" {Properties { _TintColor ("Tint Color", Color) = (0.5,0.5,0.5,0...

ArcGIS API For JS实现动态点扩散_hpugisers的博客-程序员秘密

在博客中分享的关于Openlayer实现点动态扩散,今天分享一下关于ArcGIS API实现点动态扩散的效果,主要还用canvas写,这中间用一个rasterLayer的扩展图层。先来看看效果: 一、完整demo代码:&amp;lt;!DOCTYPE html&amp;gt;&amp;lt;html&amp;gt;&amp;lt;head&amp;gt; &amp;lt;title&amp;gt;arcgis map fla...

推荐文章

热门文章

相关标签