[C++][数据结构]二叉搜索树:介绍和实现

二叉搜索树

概念

二叉搜索树又称二叉排序树,它是一棵空树,或者是具有以下性质的二叉树:

  • 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
  • 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树

模拟实现(非递归)

节点

	template<class K, class V>struct BSTreeNode	//节点{using Node = BSTreeNode<K, V>;Node* _left;	//左节点Node* _right;	//右节点K _key;			//键V _value;		//值BSTreeNode(const K& key, const V& value):_left(nullptr), _right(nullptr), _key(key),_value(value){}				//拷贝构造};

寻找

根据BSTree的特点,

  • 比该节点的值大,就走到该节点右节点
  • 比该节点的值小,就走到该节点左节点

插入

  1. 先寻找,有相同值则return false
  2. 插入,链接父节点和原来的子树

删除

没有孩子/一个孩子

对于这种情况,

  • 当删除节点左边为空,就将该节点右边托付给父亲
  • 右边为空,就将左边托付给父亲
    所以对于删除叶子节点也可以归纳到这里面

两个孩子:替换法

找一个能替换删除节点的节点,交换值,转换删除替换节点
比如:删除图中3这个节点
我们可以将左子树的最大节点或者右子树的最左节点替换掉3
即左子树最右节点或者右子树最左节点

在这里插入图片描述

rightMin的问题

假如rightMinParent为空指针,那下面这句特殊情况会出错

rightMinParent->_left = rightMin->_right;

在这里插入图片描述

这幅图中,当删除根节点时,右子树最左节点为空,不进循环,rightMinParent为空,访问空节点的左子树会出现错误

代码

测试代码

void TestBSTree()
{BSTree<string, string> dict;dict.Insert("insert", "插入");dict.Insert("erase", "删除");dict.Insert("left", "左边");dict.Insert("string", "字符串");string str;while (cin >> str){auto ret = dict.Find(str);if (ret){cout << str << ":" << ret->_value << endl;}else{cout << "单词拼写错误" << endl;}}string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };// 统计水果出现的次BSTree<string, int> countTree;for (auto str : strs){auto ret = countTree.Find(str);if (ret == NULL){countTree.Insert(str, 1);}else{ret->_value++;}}countTree.InOrder();
}

完整代码

namespace key_value
{template<class K, class V>struct BSTreeNode	//节点{using Node = BSTreeNode<K, V>;Node* _left;	//左节点Node* _right;	//右节点K _key;			//键V _value;		//值BSTreeNode(const K& key, const V& value):_left(nullptr), _right(nullptr), _key(key),_value(value){}				//拷贝构造};template<class K, class V>class BSTree{using Node = BSTreeNode<K, V>;public://插入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 != nullptr){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{return false;}}//查找完再判断是父节点的左树还是右数//标记为Acur = new Node(key, value);if (parent->_key > key){parent->_right = cur;}else{parent->_right = cur;}return true;}//查找,并返回这个节点的指针(位置)Node* Find(const K& key){Node* cur = _root;while (cur != nullptr){if (cur->_key > key){cur = cur->_right;}else if (cur->_key < key){cur = cur->_left;}else{return cur;}}return nullptr;}//删除节点bool Erase(const K& key){//并没有在开头判断删除节点是否为根节点//而是在下面Node* parent = nullptr;Node* cur = _root;while (cur != nullptr){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{	//功能Aif (cur == parent->_right){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;return true;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->left;}else{	//功能Aif (cur == parent->_right){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}delete cur;return true;}else{// 采用右树最左节点替换法Node* rightMin = cur->_right;Node* rightMinParent = cur;while (rightMin->_left){rightMinParent = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMin == rightMinParent->_right){rightMinParent->_right = rightMin->_right;}else{rightMinParent->_left = rightMin->_left;}delete rightMin;return true;}}}return false;}void InOrder()//中序打印{_InOrder(_root);}//因为外部取不到_root//所以再套一层private:Node* _root = nullptr;void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);std::cout << root->_key << " ";_InOrder(root->_right);}};
}

结语

现在再来写BSTree感觉也不是很困难,希望对你有帮助,我们下次见
(补充一下,代码是不全的,BSTree() 和~BSTree()都没写,用的默认的)

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

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

相关文章

autoware.auto 安装 ROS2

先进行docker安装 sudo apt-get update sudo apt-get install ca-certificates curl gnupg lsb-release curl -fsSL https://download.docker.com/linux/ubuntu/gpg | sudo apt-key add - sudo add-apt-repository "deb [archamd64] https://download.docker.com/linux/u…

Hass哈斯数控数据采集网络IP配置设置

机床数据采集&#xff08;MDC&#xff09;允许你使用Q和E命令通过网络接口或选项无线网络从控制系统提取数据。设置143支持该功能&#xff0c;并且指定控制器使用这个数据端口。MDC是一个需要一台附加计算机发送请求&#xff0c;解释说明和存储机床数据的软件功能。这个远程计算…

SPA模式下的多页面跳转原理及实现——jQuery Mobile为例

jQuery Mobile在SPA模式下的多页面跳转原理及实现案例 文章目录 jQuery Mobile在SPA模式下的多页面跳转原理及实现案例前言一、SPA的实现原理和代码分析1.实现原理说明&#xff08;1&#xff09;index.html&#xff08;2&#xff09;index.js&#xff08;3&#xff09;page2.ht…

快捷回复软件让你告别回复慢

可能自己是个客服的原因&#xff0c;一连几天大数据给我推了一个叫“客服宝聊天助手”的软件。用了几天真心觉得好用&#xff0c;能解决我回客户很慢的困扰。如果大家对快捷回复软件感兴趣&#xff0c;可以接着了解哦&#xff01; 一、减少复制粘贴 传统的客服工作中&#xff…

idea常用知识点随记

idea常用知识点随记 1. 打开idea隐藏的commit窗口2. idea中拉取Git分支代码3. idea提示代码报错&#xff0c;项目编译没有报错4. idea中实体类自动生成序列号5. idea隐藏当前分支未commit代码6. idea拉取新建分支的方法 1. 打开idea隐藏的commit窗口 idea左上角File→Settings…

C语言实现贪吃蛇

目录 前言一 . 游戏背景1. 背景介绍2. 项目目标3. 技术要点 二 . 效果演示三 . 游戏的设计与分析1. 核心逻辑2. 设计与分析游戏开始Gamestart()函数游戏运行Gamerun()函数游戏结束Gameend()函数 四 . 参考代码五 . 总结 前言 本文旨在使用C语言和基础数据结构链表来实现贪吃蛇…

近50亿元国资助阵,全球最大量子独角兽登场!

4月30日&#xff0c;澳大利亚与PsiQuantum公司宣布签订一项近10亿澳元&#xff08;约6.2亿美元、47.24亿人民币&#xff09;的协议&#xff0c;旨在建造世界上第一台商业上“有用”的量子计算机。 仅在一天前&#xff0c;澳大利亚还投资了1840万澳元&#xff0c;在悉尼大学成立…

CTF(Web)中关于执行读取文件命令的相关知识与绕过技巧

在我遇到的题目中&#xff0c;想要读取文件必然是要执行cat /flag这个命令&#xff0c;但是题目当然不会这么轻松。让你直接cat出来&#xff0c;必然会有各种各样的滤过条件&#xff0c;你要做的就是尝试各种方法在cat /flag的基础上进行各种操作构建出最终的payload。 下面我…

[C++基础学习-06]----C++指针详解

前言 指针是一个存储变量地址的变量&#xff0c;可以用来访问内存中的数据。在C中&#xff0c;指针是一种非常有用的数据类型&#xff0c;可以帮助我们在程序中对内存进行操作和管理。 正文 01-指针简介 指针的基本概念如下&#xff1a; 声明指针&#xff1a;使用“*”符…

【考研数学】武忠祥「基础篇」如何衔接进入强化?

如果基础篇已经做完&#xff0c;并且讲义上的例题也都做完了&#xff0c; 那下一步就是该做题了 这个时候&#xff0c;不能盲目做题&#xff0c;做什么题很重要&#xff01;我当初考研之前&#xff0c;基础也很差&#xff0c;所以考研的时候选了错误的题集&#xff0c;做起来就…

设计网页用什么软件

在设计网页时&#xff0c;可以使用多种软件来完成不同的任务。以下是一些常用的网页设计软件&#xff0c;以及它们的特点和用途。 1. Adobe Photoshop&#xff1a; Adobe Photoshop 是一款功能强大的图像编辑软件。在网页设计中&#xff0c;它常用于创建和编辑网页所需的图像、…

5-在Linux上部署各类软件

1. MySQL 数据库安装部署 1.1 MySQL 5.7 版本在 CentOS 系统安装 注意&#xff1a;安装操作需要 root 权限 MySQL 的安装我们可以通过前面学习的 yum 命令进行。 1.1.1 安装 配置 yum 仓库 # 更新密钥 rpm --import https://repo.mysql.com/RPM-GPG-KEY-mysql-2022# 安装Mysql…

C/C++ BM33 二叉树的镜像

文章目录 前言题目解决方案一1.1 思路阐述1.2 源码 总结 前言 镜像说的好听&#xff0c;无非就是换下节点。 题目 操作给定的二叉树&#xff0c;将其变换为源二叉树的镜像。 数据范围&#xff1a;二叉树的节点数 0 ≤ n ≤ 1000 0≤n≤1000 0≤n≤1000&#xff0c; 二叉树每…

分享几个副业,一天搞100~200不成问题,一不小心收益比你主业还多

每次家庭聚会&#xff0c;总是那些老掉牙的话题在耳边萦绕&#xff1a;“孩子&#xff0c;你工资多少啊&#xff1f;买车买房了吗&#xff1f;”仿佛只有按部就班地上班、结婚生子&#xff0c;才是人生的唯一出路。 然而&#xff0c;在这个充满机遇的时代&#xff0c;谁说“不上…

【Pytorch】2.TensorBoard的运用

什么是TensorBoard 是一个可视化和理解深度爵溪模型的工具。它可以通过显示模型结构、训练过程中的指标和图形化展示训练的效果来帮助用户更好地理解和调试他们的模型 TensorBoard的使用 安装tensorboard环境 在终端使用 conda install tensorboard通过anaconda安装 导入类Sum…

华为ensp中USG6000V防火墙双机热备VRRP+HRP原理及配置

作者主页&#xff1a;点击&#xff01; ENSP专栏&#xff1a;点击&#xff01; 创作时间&#xff1a;2024年5月6日20点26分 华为防火墙双机热备是一种高可用性解决方案&#xff0c;可以将两台防火墙设备组成一个双机热备组&#xff0c;实现主备切换。当主用防火墙出现故障时&…

零基础入门学习Python第二阶01生成式(推导式),数据结构

Python语言进阶 重要知识点 生成式&#xff08;推导式&#xff09;的用法 prices {AAPL: 191.88,GOOG: 1186.96,IBM: 149.24,ORCL: 48.44,ACN: 166.89,FB: 208.09,SYMC: 21.29}# 用股票价格大于100元的股票构造一个新的字典prices2 {key: value for key, value in prices.i…

【强训笔记】day7

NO.1 思路&#xff1a;双指针模拟&#xff0c;begin表示最长数字字符串最后一个字符&#xff0c;而len表示数字字符串的长度&#xff0c;i用来遍历&#xff0c;如果为数字&#xff0c;那么定义j变量继续遍历&#xff0c;直到不为数字&#xff0c;i-j如果大于len&#xff0c;就…

优惠券样式案例

优惠券样式案例 <template><view class"box"><view class"boxItem"><img src"../../../static/come.png" alt"" class"img"/><span class"icon">&#xffe5;</span><s…

cmake进阶:文件操作

一. 简介 前面几篇文章学习了 cmake的文件操作&#xff0c;写文件&#xff0c;读文件。文章如下&#xff1a; cmake进阶&#xff1a;文件操作之写文件-CSDN博客 cmake进阶&#xff1a;文件操作之读文件-CSDN博客 本文继续学习文件操作。主要学习 文件重命名&#xff0c;删…