C++深入细致探究二叉搜索树
作者:Suk-god 发布时间:2021-12-31 00:09:24
1、二叉搜索树的概念
 二叉搜索树又称二叉排序树,它可以是一颗空树,亦可以是一颗具有如下性质的二叉树:
  ①若根节点的左子树不为空,则左子树上的所有节点的值域都小于根节点的值
  ②若根节点的右子树不为空,则右子树上的所有节点的值域都大于根节点的值
  ③根节点的左右子树分别也是一颗二叉搜索树
例如下面的这棵二叉树就是一棵二叉搜索树:
注意:判定一棵二叉树是否为二叉搜索树一定要紧扣二叉搜索树的概念~
2、二叉搜索树的操作
声明:该文章讨论的是二叉搜索树中节点值唯一的情况。
二叉搜索树的查找
对于查找部分,充分利用二叉搜索树的特性,即右子树的value 大于根节点,左子树的value小于根节点。
例如:查找下图中的红色方框中的节点
以6对应的节点为列,查找过程主要经历如下几个步骤:
  ①6与根节点5比较,6 > 5,因此到5的右子树查找
  ①6与根节点7比较,6 < 7,因此到7的左子树查找
  ①6与根节点6比较,6 == 6,此时查找成功!
总结基本步骤:
若根节点不为空:
  如果根节点的key == 查找的key----->返回true
  如果根节点的key > 查找的key----->转到根节点的右子树查找
  如果根节点的key < 查找的key----->转到根节点的左子树查找
否则(根节点为空了),直接返回false,表示树中不存在要查找的key
二叉搜索树的插入
主要分两大类的情况进行讨论:
1、树为空,直接插入
如下图所示:
2、树不空
①按照二叉搜索树的性质查找插入的位置
②插入新的节点
e.g:在下面的二叉搜索树中插入-1
第一步,查找插入位置:
 注意:要标记当前访问的节点的双亲,否则,就算找到了插入位置,由于无法访问其双亲,也是无法进行插入的。这里使用parent来标记当前访问节点的双亲节点。
具体过程如下图:
第二步,插入新节点
判断待插入节点(node)的值与parent标记的节点值的大小关系
if(node->value < parent->value)//新节点作为parent的左孩子
{
parent->left = node;
}
else//新节点作为parent的右孩子
{
parent->right = node;
}
来源:https://blog.csdn.net/Suk_god/article/details/124906501
猜你喜欢
- C#调用c++dll文件是一件很麻烦的事情,首先面临的是数据类型转换的问题,相信经常做c#开发的都和我一样把学校的那点c++底子都忘光了吧(
- 一. spring配置文件:application.xml<?xml version="1.0" encoding
- 前言:反射(Reflection)是.NET提供给开发者的一个强大工具,尽管作为.NET框架的使用者,很多时候不会用到反射。但在一些情况下,
- 这个工具叫“InstallShield”,可以自己去网上下一个,有绿色版本 也有安装版的。 &
- 本文实例讲述了C++实现的O(n)复杂度内查找第K大数算法。分享给大家供大家参考,具体如下:题目:是在一组数组(数组元素为整数,可正可负可为
- DataBindings属性是很多控件都有的属性,作用有2方面。一方面是用于与数据库的数据进行绑定,进行数据显示。另一方面用于与控件或类的对
- CXF简介CXF是一个开源的WebService框架。Apache CXF = Celtix + XFire,开始叫 Apache Celt
- 问题:使用getServletContext().getRealPath()得到的是临时文件的路径。每次重启服务,这个临时文件的路径还会变更
- 前言:封装、继承和多态是面向对象编程的三大特征。1.封装1.1.封装概念封装就是把抽象出的数据(属性)和对数据的操作(方法)封装在一起,数据
- 泛型泛型的语法定义class 类名 <泛型标识,泛型标识,…>{ private 泛型标识1,变量名;常用
- 引言当我们通过@ConfigurationProperties注解实现配置 bean的时候,如果默认的配置属性转换无法满足我们的需求的时候,
- 一、前期准备1、申请好微信商户号appid,拿到商户id和商户秘钥,退款的话需要商户证书2、申请好支付宝商户号appid,商户公钥和秘钥(需
- 今天是圣诞节平安夜,为此特别制作了一个雪花飘落的场景,我们的雪花渲染方式不同于网上流行的使用Camera Filter,需要将脚本挂接到相机
- 使用可以绑定数据源的控件我们需要有实现了IList接口的类作为数据源,我们有很多的方法,比如使用ArrayList或者List的泛型类都是很
- Android N 可以同时显示多个应用窗口。 在手机上,两个应用可以在“分屏”模式中左右并排或上下并排显示。例如,用户可以 在上面窗口聊Q
- springmvc 使用map接收参数开发过程中有时候我们并不知道前端都会传递哪些参数给到后端. 为方便扩展接口功能, 在请求参数不改变的情
- 比如在窗体中显示时间:错误思路一:我在窗体结构函数中写入一个死循环,每隔一秒显示一次当前时间public Form6() &n
- 完整代码已上传到GitHub。Web端体验地址:http://47.116.72.33/(只剩一个月有效期)apk下载地址:https://
- JAVAWEB dbutils执行sql命令并遍历结果集时不能查到内容的原因及处理方法如下所示:遍历结果集时只遍历bean对象才会只输出第一
- 概述在Winform中从后台添加控件相对比较容易,但是在WPF中,我们知道界面是通过XAML编写的,如何把后台写好的控件动态添加到前台呢?本