C++进阶 二叉搜索树的讲解

在这里插入图片描述

二叉搜索树的概念

二叉搜索树又称为二叉排序树。

  • 二叉搜索树的性质
    • 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值
    • 若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值
    • 它的左右子树也分别为二叉搜索树
    • 二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值。

二叉搜索树的插入

    1. 树为空，则直接新增结点，赋值给 root 指针
    1. 树不空，按二叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。
    1. 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）

例子:

int a[] = {8, 3, 1, 10, 1 6, 4, 7, 14, 13};

请添加图片描述

代码:

bool Insert(const K &key, const V &value)
{if (_root == nullptr){_root = new Node(key, value);return true;}Node *parent = nullptr;Node *cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key, value);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;
}

二叉搜索树的查找

    1. 从根开始比较，查找 x，x 比根的值大则往右边走查找，x 比根值小则往左边走查找。
    1. 最多查找高度次，走到到空，还没找到，这个值不存在。
    1. 如果不支持插入相等的值，找到 x 即可返回。
    1. 如果支持插入相等的值，意味着有多个 x 存在，一般要求查找中序的第一个 x。

代码:

Node *Find(const K &key)
{Node *cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return cur;}}return nullptr;
}

二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回 false。
如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为 N）

  1. 要删除结点 N 左右孩子均为空
    • 解决方法：把 N 结点的父亲对应孩子指针指向空，直接删除 N 结点
  2. 要删除的结点 N 左孩子位空，右孩子结点不为空
    • 解决方法：把 N 结点的父亲对应孩子指针指向 N 的右孩子，直接删除 N 结点
  3. 要删除的结点 N 右孩子位空，左孩子结点不为空
    • 解决方法：把 N 结点的父亲对应孩子指针指向 N 的左孩子，直接删除 N 结点
  4. 要删除的结点 N 左右孩子结点均不为空
    • 解决方法：无法直接删除 N 结点，因为 N 的两个孩子无处安放，只能用替换法删除。**找 N 左子树的值最大结点 R(最右结点)**或者 N 右子树的值最小结点 R(最左结点)替代 N，因为这两个结点中任意一个，放到 N 的位置，都满足二叉搜索树的规则。替代 N 的意思就是 N 和 R 的两个结点的值交换，转而变成删除 R 结点，R 结点符合情况 2 或情况 3，可以直接删除。

代码:

bool Erase(const K &key)
{Node *parent = nullptr;Node *cur = _root;while (cur)//循环搜索目标节点{if (cur->_key < key)//当前节点的值小于目标值就向右子树{parent = cur;cur = cur->_right;}else if (cur->_key > key)//当前节点的值大于目标值就向左子树{parent = cur;cur = cur->_left;}else{//找到了目标节点,进行删除操作if (cur->_left == nullptr)//左节点为空{if (cur == _root)//如果是根节点，就将根节点的右子节点设置为根节点{_root = cur->_right;}else{if (parent->_left == cur)//如果父节点的左节点是当前节点{parent->_left = cur->_right;//将父节点的左节点连接至当前节点的右子节点。}else//如果父节点的右节点是当前节点{parent->_right = cur->_right;//将父节点的右节点连接至当前节点的右子节点。}}delete cur;//删除当前节点}else if (cur->_right == nullptr)//右节点为空{if (cur == _root)//如果是根节点，就将根节点的左子节点设置为根节点{_root = cur->_left;}else{if (parent->_left == cur)//如果父节点的左节点是当前节点{parent->_left = cur->_left;//将父节点的左节点连接至当前节点的左子节点。}else//如果父节点的右节点是当前节点{parent->_right = cur->_left;//将父节点的右节点连接至当前节点的左子节点。}}delete cur;//删除当前节点}else{// 左右节点都不为空// 这里默认替换右子树最左节点cNode *replaceParent = cur;Node *replace = cur->_right;//进入根节点的右子树while (replace->_left)//迭代左节点，找到右子树的最左节点{replaceParent = replace;//记录父节点replace = replace->_left;//迭代左节点}//此时替换节点（replace）的左节点一定为空cur->_key = replace->_key;//交换值if (replaceParent->_left == replace)//如果替换节点是左节点replaceParent->_left = replace->_right;//将父节点的左赋值为替换节点的右，因为替换节点的左节点一定是空的，因为是按照根节点的右子树的最左节点查找的。else//如果替换节点是右节点replaceParent->_right = replace->_right;//将父节点的右赋值为替换节点的右，因为替换节点的左节点一定是空的，因为是按照根节点的右子树的最左节点查找的。delete replace;//删除替换节点}return true;}}return false;
}

二叉搜索树的析构

  • 递归析构
public:
~BSTree()
{Destroy(_root);_root = nullptr;
}private:
void Destroy(Node *root)
{if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;
}

二叉搜索树的深拷贝

BSTree(const BSTree &t)
{_root = Copy(t._root);
}Node *Copy(Node *root)
{if (root == nullptr)return nullptr;Node *newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;
}

二叉搜索树的=重载

BSTree &operator=(BSTree tmp)
{swap(_root, tmp._root);//tmp为拷贝，可以直接交换，不影响tmpreturn *this;
}

完整代码

#pragma once
#include <iostream>
using namespace std;template <class K>
struct BSTNode
{K _key;BSTNode<K> *_left;BSTNode<K> *_right;BSTNode(const K &key): _key(key), _left(nullptr), _right(nullptr){}
};namespace key
{template <class K>class BSTree{typedef BSTNode<K> Node;public:bool Insert(const K &key) // 二叉树的插入{if (_root == nullptr){_root = new Node(key);return true;}Node *parent = nullptr;Node *cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}void Inorder() // 中序遍历{_Inorder(_root);}bool find(const K &key) // 查找{Node *cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return true;}}return false;}bool Erase(const K &key){Node *parent = nullptr;Node *cur = _root;while (cur){// 先搜索节点if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{// 找到了要删除的节点// 删除// 左为空if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr) // 右为空{if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{// 左右都不为空// 右子树最左节点Node *replaceParent = cur;Node *replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}cur->_key = replace->_key;if (replaceParent->_left == replace)replaceParent->_left = replace->_right;elsereplaceParent->_right = replace->_right;delete replace;}return true;}}return false;}private:void _Inorder(Node *root){if (root == nullptr){return;}_Inorder(root->_left);cout << root->_key << ' ';_Inorder(root->_right);}private:Node *_root = nullptr;};}

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/424511.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Geneformer AI 模型，有限数据也能解锁基因网络

Geneformer AI 模型，有限数据也能解锁基因网络

目录 类似于 BERT 的单单元数据参考模型 NVIDIA Clara 工具组合用于药物研发 用于疾病建模的基础 AI 模型 Geneformer 是最近推出的 和功能强大的 AI 模型&#xff0c;可以通过从大量单细胞转录组数据中进行迁移学习来学习基因网络动力学和相互作用。借助此工具&#xff0c;…
阅读更多...
尚品汇-订单拆单、支付宝关闭交易、关闭过期订单整合（五十）

尚品汇-订单拆单、支付宝关闭交易、关闭过期订单整合（五十）

目录&#xff1a; &#xff08;1&#xff09;拆单接口 &#xff08;2&#xff09;取消订单业务补充关闭支付记录 &#xff08;3&#xff09;支付宝关闭交易 &#xff08;4&#xff09;查询支付交易记录 &#xff08;5&#xff09;PaymentFeignClient 远程接口 &#xff08…
阅读更多...
探索Python轻量级数据库：TinyDB的奇妙之旅

探索Python轻量级数据库：TinyDB的奇妙之旅

文章目录 探索Python轻量级数据库&#xff1a;TinyDB的奇妙之旅背景&#xff1a;为何选择TinyDB&#xff1f;什么是TinyDB&#xff1f;如何安装TinyDB&#xff1f;简单库函数使用方法场景应用常见Bug及解决方案总结 探索Python轻量级数据库&#xff1a;TinyDB的奇妙之旅 背景&…
阅读更多...
Redis入门2

Redis入门2

在java中操作Redis Redis的Java客户端 Redis 的 Java 客户端很多&#xff0c;常用的几种: Jedis Lettuce Spring Data Redis Spring Data Redis 是 Spring 的一部分&#xff0c;对 Redis 底层开发包进行了高度封装。 在 Spring 项目中&#xff0c;可以使用Spring Data R…
阅读更多...
Vue介绍、窗体内操作、窗体间操作学习

Vue介绍、窗体内操作、窗体间操作学习

系列文章目录 第一章 基础知识、数据类型学习 第二章 万年历项目 第三章 代码逻辑训练习题 第四章 方法、数组学习 第五章 图书管理系统项目 第六章 面向对象编程&#xff1a;封装、继承、多态学习 第七章 封装继承多态习题 第八章 常用类、包装类、异常处理机制学习 第九章 集…
阅读更多...
【Linux】Ubuntu 22.04 shell实现MySQL5.7 tar 一键安装

【Linux】Ubuntu 22.04 shell实现MySQL5.7 tar 一键安装

参考 https://blog.csdn.net/qq_35995514/article/details/134350572?spm1001.2014.3001.5501 源文章是centos 的 教程&#xff0c;这里为了大家的方便&#xff0c;再原作者基础上做了修改&#xff0c;记录了ubuntu的22.04的我的配置&#xff0c;加了一个删除原有mysql 的脚本…
阅读更多...
【诉讼流程-健身房-违约认定-私教课-诉讼书前提材料整理-民事诉讼-自我学习-铺平通往法律的阶梯-讲解（2）】

【诉讼流程-健身房-违约认定-私教课-诉讼书前提材料整理-民事诉讼-自我学习-铺平通往法律的阶梯-讲解（2）】

【诉讼流程-健身房-违约-私教课-前期法律流程-民事诉讼-自我学习-铺平通往法律的阶梯-讲解&#xff08;2&#xff09;】 &#xff08;1&#xff09;前言说明1、目的2、一个小测试1、更换原教练2、频繁更换教练3、上课估计拖课&#xff0c;占用上课时间&#xff0c;抽烟等。4、以…
阅读更多...
Python计算机视觉 第10章-OpenCV

Python计算机视觉 第10章-OpenCV

Python计算机视觉 第10章-OpenCV OpenCV 是一个C 库&#xff0c;用于&#xff08;实时&#xff09;处理计算视觉问题。实时处理计算机视觉的 C 库&#xff0c;最初由英特尔公司开发&#xff0c;现由 Willow Garage 维护。OpenCV 是在 BSD 许可下发布的开源库&#xff0c;这意味…
阅读更多...
2024/9/11学校教的响应式前端能学到什么?

2024/9/11学校教的响应式前端能学到什么?

9.11 1&#xff09;砌砖 确定整体框架&#xff0c;而不是想到一点写一点&#xff0c;类似盖大楼&#xff0c;不是想到哪盖到哪&#xff0c;先砌砖&#xff0c;再装修 砌砖前先划分好砌砖范围(初始化样式) 清除body自带的内外边距 * { margin: 0; padding: 0; }去掉li的小圆点…
阅读更多...
【新片场-注册安全分析报告-无验证方式导致安全隐患】

【新片场-注册安全分析报告-无验证方式导致安全隐患】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 1. 暴力破解密码&#xff0c;造成用户信息泄露 2. 短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉 3. 带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造…
阅读更多...
微信小程序开发第三课

微信小程序开发第三课

1 wxml语法 1.1 模版语法 # 1 在页面 xx.js 的 Page() 方法的 data 对象中进行声明定义 # 2 在xx.wxml 中使用 {{}} 包裹&#xff0c;显示数据 # 3 可以显示如下&#xff0c;不能编写js语句或js方法-变量-算数运算-三元运算-逻辑判断# 4 只是单纯通过赋值&#xff0c;js中…
阅读更多...
快速生成服务器响应json-server的安装和使用

快速生成服务器响应json-server的安装和使用

json-server介绍地址:https://www.geeksforgeeks.org/json-server-setup-and-introduction/ 1.json-server是什么? 基于自定义的json文件,快速生成服务端响应,可用于前端调试接口 2.安装和卸载json-server 2.1 安装: 使用npm命令: npm install -g json-server 2.2 卸载 npm …
阅读更多...
工厂方法模式和抽象工厂模式

工厂方法模式和抽象工厂模式

工厂方法模式 一个工厂只能创建一种产品 工厂方法模式的结构 工厂方法模式包含以下4个角色 Product&#xff08;抽象产品&#xff09; ConcreteProduct&#xff08;具体产品&#xff09; Factory&#xff08;抽象工厂&#xff09; ConcreteFactory&#xff08;具体工厂…
阅读更多...
（论文解读）Visual-Language Prompt Tuning with Knowledge-guided Context Optimization

（论文解读）Visual-Language Prompt Tuning with Knowledge-guided Context Optimization

Comment: accepted by CVPR2023 基于知识引导上下文优化的视觉语言提示学习 摘要 提示调优是利用任务相关的可学习标记将预训练的视觉语言模型&#xff08;VLM&#xff09;适应下游任务的有效方法。基于CoOp的代表性的工作将可学习的文本token与类别token相结合&#xff0c;…
阅读更多...
项目需求 | MySQL增量备份与恢复的完整操作指南

项目需求 | MySQL增量备份与恢复的完整操作指南

目录 一、MySql数据库增量备份的工作原理 1、全量备份与增量备份 2、增量备份原理 二、进行增量备份 步骤1&#xff1a;启用二进制日志 使用 SHOW VARIABLES 命令查看二进制日志状态 步骤2&#xff1a;执行增量备份脚本 三、使用增量备份恢复损坏的数据库 步骤1&#…
阅读更多...
WSL安装Redis

WSL安装Redis

前言 本来一直是在虚拟机的Ubuntu开发 但是 搞着搞着内存不足 导致我某些数据损坏了 然后目前迁移到Wsl开发 运行WSL的相较于虚拟机你不需要很多的性能开销&#xff01; 我只是代码开发和git交互&#xff0c;如果是搞逆向还是虚拟机。 记录一下redis 安装卸载 免得以后又忘了…
阅读更多...
java基于PDF底层内容流的解析对文本内容进行编辑

java基于PDF底层内容流的解析对文本内容进行编辑

本文实现了基于坐标位置对PDF内容的底层修改而非覆盖&#xff0c;因此不会出现在某些高级PDF编辑器中可以移除插入内容或者文件随着编辑次数增多而大幅增大&#xff08;原因是原内容还在文件中&#xff09;的问题&#xff0c;而且使用的pdfbox是一个开源的、免费的PDF处理库&am…
阅读更多...
SSHamble：一款针对SSH技术安全的研究与分析工具

SSHamble：一款针对SSH技术安全的研究与分析工具

关于SSHamble SSHamble是一款功能强大的SSH技术安全分析与研究工具&#xff0c;该工具基于Go语言开发&#xff0c;可以帮助广大研究人员更好地分析SSH相关的安全技术与缺陷问题。 功能介绍 SSHamble 是用于 SSH 实现的研究工具&#xff0c;其中包含下列功能&#xff1a; 1、针…
阅读更多...
ESP01的AT指令连接到阿里云平台

ESP01的AT指令连接到阿里云平台

物联网平台提供安全可靠的设备连接通信能力&#xff0c;支持设备数据采集上云&#xff0c;规则引擎流转数据和云端数据下发设备端。此外&#xff0c;也提供方便快捷的设备管理能力&#xff0c;支持物模型定义&#xff0c;数据结构化存储&#xff0c;和远程调试、监控、运维。总…
阅读更多...
移动UI案例：工具类app整套案例

移动UI案例：工具类app整套案例

工具类App是指提供各种实用工具和功能的手机应用程序。这些工具可以包括但不限于日历、闹钟、备忘录、翻译、计算器、单位转换、天气预报、地图导航、音乐播放器、相机、视频编辑等。这些工具类App能够帮助用户解决日常生活和工作中的各种问题&#xff0c;提高效率和便利性。 …
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023