【数据结构高阶】二叉搜索树

接下来我们来开始使用C++来详细讲解数据结构的一些高阶的知识点

本期讲解的是二叉搜索树,对于初阶二叉树有所遗忘的同学可以看到这里:

【精选】【数据结构初阶】链式二叉树的解析及一些基本操作

讲解二叉搜索树主要是为了后面的map和set做铺垫,废话不多说我们直接上干货:


目录

一、二叉搜索树的概念

二、模拟实现二叉搜索树

2.1 插入数据

2.1.1 插入数据的非递归实现

2.2 遍历数据

2.3 查找数据

2.4 删除数据

2.4.1 删除数据的非递归实现

2.5 模拟实现二叉搜索树的全部代码


一、二叉搜索树的概念

二叉搜索树又称二叉排序树(BST, Binary Search Tree),它可以是一棵空树,或者是具有以下性质的二叉树:

若它的左子树不为空,则左子树上所有节点的值都小于根节点的值

若它的右子树不为空,则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

 例如:

 

我们可以发现的一点:无论是什么样的二叉搜索树,使用中序遍历,遍历出的值都是升序排列的

二、模拟实现二叉搜索树

下面又到了我们最激动人心的代码实现环节,本次代码实现我们还是要基于链式二叉树的实现:

template<class K>
struct BSTreeNode//节点
{BSTreeNode<K>* _lchild;BSTreeNode<K>* _rchild;K _key;BSTreeNode(const K& key):_lchild(nullptr),_rchild(nullptr),_key(key){}
};

2.1 插入数据

我们可以根据二叉搜索树的规律来向其中插入数据,但是插入数据时需要注意一点:要记录插入节点的上一个父节点,将插入的节点连接上二叉树:

template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);_root->_key = key;return true;}Node* cur = _root;//使用cur遍历二叉树找到合适的插入位置Node* parent = cur;//记录cur的父节点while (cur){parent = cur;if (key < cur->_key){cur = cur->_lchild;}else if (key > cur->_key){cur = cur->_rchild;}else{return false;//这里创建的二叉搜索树不允许出现值的冗余}}cur = new Node(key);//创建//将创建的节点链接到二叉树上if (key < parent->_key){parent->_lchild = cur;}else{parent->_rchild = cur;}return true;}private:Node* _root = nullptr;//根节点
};

2.1.1 插入数据的非递归实现

递归的效率并没有循环高,那为什么要说一下插入数据的非递归实现呢

主要是非递归的数据插入的传值方法值得一说:

template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool InsertR(const K& key)//插入数据(递归){return _InsertR(_root, key);}bool _InsertR(Node*& root,const K& key)//这里使用指针的引用用来直接修改其父节点指针的指向{if (root == nullptr){root = new Node(key);return true;}if (root->_key > key){_InsertR(root->_lchild, key);}else if (root->_key < key){_InsertR(root->_rchild, key);}else{return false;}}
private:Node* _root = nullptr;//根节点
};

我们可以看到在递归时,传入的形参类型为Node*&,这样可以直接在其函数内部习惯其父节点孩子指针的指向

那为什么要写两个插入函数呢?因为如果我们直接使用_InsertR函数,无法直接使用对象对_InsertR函数进行传参

2.2 遍历数据

因为二叉搜索树的性质,这里我们采用中序遍历: 

template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key)插入数据{....}void InOrder()//中序遍历{_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == NULL)//如果是空树就直接结束{return;}_InOrder(root->_lchild);//先递归遍历其左子树cout << root->_key << " ";//再遍历其根节点_InOrder(root->_rchild);//最后递归遍历其右子树}private:Node* _root = nullptr;//根节点
};

那为什么要写两个中序遍历函数呢?因为如果我们直接使用_InOrder函数,无法直接使用对象对_InOrder函数进行传参

2.3 查找数据

template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key)//插入数据{......}void InOrder()//中序遍历{......}void _InOrder(Node* root){......}bool Find(const K& key)//查找数据{Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_rchild;}else if (cur->_key > key){cur = cur->_lchild;}else{return true;}}return false;}private:Node* _root = nullptr;//根节点
};

2.4 删除数据

对于在二叉搜索树中删除数据,我们就要好好说道说道了

下面我们有这样的一个二叉搜索树:

现在我们要删除其叶子节点,这很容易,直接删除完,再将其父节点对应的孩子指针置空即可

那我们要删只有一个孩子节点的数据呢?例如14和10

这个稍微麻烦一点,删除完该节点后将其孩子节点托付给其父节点即可:

那要删带有两个孩子节点的数据呢?例如3、6、8:

对于这种情况我们可以选择其节点下的左子树的最大节点(左子树的最右节点),或者右子树的最小节点(右子树的最左节点)来替代要删除的节点:

综上所述,要删除的结点可能分下面四种情况:

a. 要删除的结点无孩子结点

b. 要删除的结点只有左孩子结点 

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左、右孩子结点

看起来有待删除节点有4中情况,实际情况a可以与情况b或者c合并起来,因此真正的删除过程如下:

情况b:删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除

情况c:删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除

情况d:在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删除节点中,再来处理该结点的删除问题--替换法删除

思路我们有了,下面用代码来实现一下:

template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key)//插入数据{...}void InOrder()//中序遍历{...}private:void _InOrder(Node* root){...}public:bool Find(const K& key)//查找数据{...}bool Erase(const K& key){Node* cur = _root;//使用cur遍历二叉树找到要删除元素的位置Node* parent = cur;//记录cur的父节点while (cur)//寻找需要删除的节点{if (cur->_key < key){parent = cur;cur = cur->_rchild;}else if (cur->_key > key){parent = cur;cur = cur->_lchild;}else//找到了,开始删除{if (cur->_lchild == cur->_rchild && cur->_lchild == nullptr)//删除的节点为叶子节点{if (parent == cur)//删除的是根节点{_root = nullptr;//更新根节点}//将其父节点指向的自身的指针置空else if (parent->_lchild == cur){parent->_lchild = nullptr;}else{parent->_rchild = nullptr;}//释放节点空间delete cur;cur = nullptr;}else if (cur->_rchild == nullptr)//删除的节点右孩子为空,左孩子不为空{if (parent == cur)//删除的是根节点{_root = cur->_lchild;//更新根节点}//将删除节点的左孩子交给其父节点else if (parent->_lchild == cur){parent->_lchild = cur->_lchild;}else{parent->_rchild = cur->_lchild;}//释放节点空间delete cur;cur = nullptr;}else if (cur->_lchild == nullptr)//删除的节点左孩子为空,右孩子不为空{if (parent == cur)//删除的是根节点{_root = cur->_rchild;//更新根节点}//将删除节点的右孩子交给其父节点else if (parent->_lchild == cur){parent->_lchild = cur->_rchild;}else{parent->_rchild = cur->_rchild;}//释放节点空间delete cur;cur = nullptr;}else//删除的节点左右孩子都不为空,要找到删除节点的左子树的最大节点或右子树的最小节点可将其替换{//这里找要删除节点的左子树的最大节点(右子树的最小节点也可)Node* maxleft = cur->_lchild; // 记录左子树的最大节点Node* pmaxleft = cur;//记录左子树的最大节点的父节点while (maxleft->_rchild)//查找左子树的最大节点{pmaxleft = maxleft;maxleft = maxleft->_rchild;}//将找到的节点替换要删除的节点cur->_key = maxleft->_key;if (pmaxleft->_lchild == maxleft){pmaxleft->_lchild = maxleft->_lchild;}else{pmaxleft->_rchild = maxleft->_lchild;}//释放节点空间delete maxleft;maxleft = nullptr;}return true;}}return false;//没找到要删除的节点}
private:Node* _root = nullptr;//根节点
};

2.4.1 删除数据的非递归实现

template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool EraseR(const K& key)//递归删除数据{return _EraseR(_root, key);}bool _EraseR(Node*& root, const K& key){if (root == nullptr){return false;}else if (root->_key < key){_EraseR(root->_rchild, key);}else if (root->_key > key){_EraseR(root->_lchild, key);}else{Node* del = root;if (root->_lchild == root->_rchild && root->_lchild == nullptr)//删除的节点为叶子节点{//释放节点空间delete root;//将其父节点指向的自身的指针置空root = nullptr;}else if (root->_rchild == nullptr)//删除的节点右孩子为空,左孩子不为空{//将删除节点的左孩子交给其父节点root = root->_lchild;//释放节点空间delete del;del = nullptr;}else if (root->_lchild == nullptr)//删除的节点左孩子为空,右孩子不为空{//将删除节点的右孩子交给其父节点root = root->_rchild;//释放节点空间delete del;del = nullptr;}else//删除的节点左右孩子都不为空,要找到删除节点的左子树的最大节点或右子树的最小节点将其替换{//这里找要删除节点的右子树的最小节点(左子树的最大节点也可)Node* minright = del->_rchild; // 记录右子树的最小节点while (minright->_lchild)//查找右子树的最小节点{minright = minright->_lchild;}root->_key = minright->_key;//将找到的节点替换要删除的节点return _EraseR(root->_rchild, root->_key);//继续递归删除其右子树中用来替换的节点}return true;}}private:Node* _root = nullptr;//根节点
};

 

2.5 模拟实现二叉搜索树的全部代码

#include<iostream>
using namespace std;template<class K>
struct BSTreeNode//节点
{BSTreeNode<K>* _lchild;BSTreeNode<K>* _rchild;K _key;BSTreeNode(const K& key):_lchild(nullptr),_rchild(nullptr),_key(key){}
};template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key)//插入数据{if (_root == nullptr)//如果根节点为空就直接插入{_root = new Node(key);_root->_key = key;return true;}Node* cur = _root;//使用cur遍历二叉树找到合适的插入位置Node* parent = cur;//记录cur的父节点while (cur){parent = cur;if (key < cur->_key){cur = cur->_lchild;}else if (key > cur->_key){cur = cur->_rchild;}else{return false;//这里创建的二叉搜索树不允许出现值的冗余}}cur = new Node(key);//创建//将创建的节点链接到二叉树上if (key < parent->_key){parent->_lchild = cur;}else{parent->_rchild = cur;}return true;}bool InsertR(const K& key)//插入数据(递归){return _InsertR(_root, key);}private:bool _InsertR(Node*& root,const K& key)//这里使用指针的引用用来直接修改其父节点指针的指向{if (root == nullptr){root = new Node(key);return true;}if (root->_key > key){_InsertR(root->_lchild, key);}else if (root->_key < key){_InsertR(root->_rchild, key);}else{return false;}}public:void InOrder()//中序遍历{_InOrder(_root);cout << endl;}private:void _InOrder(Node* root){if (root == NULL)//如果是空树就直接结束{return;}_InOrder(root->_lchild);//先递归遍历其左子树cout << root->_key << " ";//再遍历其根节点_InOrder(root->_rchild);//最后递归遍历其右子树}public:bool Find(const K& key)//查找数据{Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_rchild;}else if (cur->_key > key){cur = cur->_lchild;}else{return true;}}return false;}bool Erase(const K& key)//删除数据{Node* cur = _root;//使用cur遍历二叉树找到要删除元素的位置Node* parent = cur;//记录cur的父节点while (cur)//寻找需要删除的节点{if (cur->_key < key){parent = cur;cur = cur->_rchild;}else if (cur->_key > key){parent = cur;cur = cur->_lchild;}else//找到了,开始删除{if (cur->_lchild == cur->_rchild && cur->_lchild == nullptr)//删除的节点为叶子节点{if (parent == cur)//删除的是根节点{_root = nullptr;//更新根节点}//将其父节点指向的自身的指针置空else if (parent->_lchild == cur){parent->_lchild = nullptr;}else{parent->_rchild = nullptr;}//释放节点空间delete cur;cur = nullptr;}else if (cur->_rchild == nullptr)//删除的节点右孩子为空,左孩子不为空{if (parent == cur)//删除的是根节点{_root = cur->_lchild;//更新根节点}//将删除节点的左孩子交给其父节点else if (parent->_lchild == cur){parent->_lchild = cur->_lchild;}else{parent->_rchild = cur->_lchild;}//释放节点空间delete cur;cur = nullptr;}else if (cur->_lchild == nullptr)//删除的节点左孩子为空,右孩子不为空{if (parent == cur)//删除的是根节点{_root = cur->_rchild;//更新根节点}//将删除节点的右孩子交给其父节点else if (parent->_lchild == cur){parent->_lchild = cur->_rchild;}else{parent->_rchild = cur->_rchild;}//释放节点空间delete cur;cur = nullptr;}else//删除的节点左右孩子都不为空,要找到删除节点的左子树的最大节点或右子树的最小节点可将其替换{//这里找要删除节点的左子树的最大节点(右子树的最小节点也可)Node* maxleft = cur->_lchild; // 记录左子树的最大节点Node* pmaxleft = cur;//记录左子树的最大节点的父节点while (maxleft->_rchild)//查找左子树的最大节点{pmaxleft = maxleft;maxleft = maxleft->_rchild;}//将找到的节点替换要删除的节点cur->_key = maxleft->_key;if (pmaxleft->_lchild == maxleft){pmaxleft->_lchild = maxleft->_lchild;}else{pmaxleft->_rchild = maxleft->_lchild;}//释放节点空间delete maxleft;maxleft = nullptr;}return true;}}return false;//没找到要删除的节点}bool EraseR(const K& key)//递归删除数据{return _EraseR(_root, key);}private:bool _EraseR(Node*& root, const K& key){if (root == nullptr){return false;}else if (root->_key < key){_EraseR(root->_rchild, key);}else if (root->_key > key){_EraseR(root->_lchild, key);}else{Node* del = root;if (root->_lchild == root->_rchild && root->_lchild == nullptr)//删除的节点为叶子节点{//释放节点空间delete root;//将其父节点指向的自身的指针置空root = nullptr;}else if (root->_rchild == nullptr)//删除的节点右孩子为空,左孩子不为空{//将删除节点的左孩子交给其父节点root = root->_lchild;//释放节点空间delete del;del = nullptr;}else if (root->_lchild == nullptr)//删除的节点左孩子为空,右孩子不为空{//将删除节点的右孩子交给其父节点root = root->_rchild;//释放节点空间delete del;del = nullptr;}else//删除的节点左右孩子都不为空,要找到删除节点的左子树的最大节点或右子树的最小节点将其替换{//这里找要删除节点的右子树的最小节点(左子树的最大节点也可)Node* minright = del->_rchild; // 记录右子树的最小节点while (minright->_lchild)//查找右子树的最小节点{minright = minright->_lchild;}root->_key = minright->_key;//将找到的节点替换要删除的节点return _EraseR(root->_rchild, root->_key);//继续递归删除其右子树中用来替换的节点}return true;}}private:Node* _root = nullptr;//根节点
};

本期博客到这里就结束了,代码量较大,还请各位仔细分析呀

我们下期见~

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

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

相关文章

我记不住的getopt_long的那些参数和返回值

前言&#xff1a;最近在学习面向Linux系统进行C语言的编程&#xff0c;通过查询man手册和查看网络上的各种文章来获取一点点的知识&#xff0c;重点是看完手册还是一脸懵逼&#xff0c;搞不懂手册里面再说啥&#xff0c;而本篇文章将记录一下学习getopt_long的那些参数和返回值…

ElasticStack日志分析平台-ES 集群、Kibana与Kafka

一、Elasticsearch 1、介绍&#xff1a; Elasticsearch 是一个开源的分布式搜索和分析引擎&#xff0c;Logstash 和 Beats 收集的数据可以存储在 Elasticsearch 中进行搜索和分析。 Elasticsearch为所有类型的数据提供近乎实时的搜索和分析&#xff1a;一旦数据被索引&#…

0基础学习PyFlink——水位线(watermark)触发计算

在《0基础学习PyFlink——个数滚动窗口(Tumbling Count Windows)》和《0基础学习PyFlink——个数滑动窗口&#xff08;Sliding Count Windows&#xff09;》中&#xff0c;我们发现如果窗口中元素个数没有把窗口填满&#xff0c;则不会触发计算。 为了解决长期不计算的问题&a…

PyCharm 【unsupported Python 3.1】

PyCharm2020.1版本&#xff0c;当添加虚拟环境发生异常&#xff1a; 原因&#xff1a;Pycharm版本低了&#xff01;不支持配置的虚拟环境版本 解决&#xff1a;下载PyCharm2021.1版本&#xff0c;进行配置成功&#xff01;

2023年,全球CIO最关注的问题是什么?

面对AI大潮&#xff0c;全球CIO们在焦虑什么&#xff1f;随着全球数字化转型步伐的加速&#xff0c;CIO的角色发生了哪些转变&#xff1f; 继2022年5月发布首份全球CIO报告之后&#xff0c;联想集团今年又发布了以“韧性的全球首席信息官&#xff08;The Resilient CIO&#xf…

python大数据毕设选题

文章目录 0 前言1 大数据毕设选题推荐2 开题指导3 最后 0 前言 大家好&#xff01;大四的同学们&#xff0c;毕业设计的时间即将到来&#xff0c;你们准备好了吗&#xff1f;为了帮助大家更好地开始毕设&#xff0c;我作为学长给大家整理了最新的计算机大数据专业的毕设选题。…

微信公众号与小程序打通:流量变现的新路径

随着移动互联网的迅速发展&#xff0c;微信公众号和小程序已经成为企业营销和运营的重要工具。将微信公众号与小程序打通&#xff0c;不仅可以提高用户体验&#xff0c;还能有效提升流量的变现效率。本文将为您解析如何打通微信公众号与小程序&#xff0c;让流量快速变现。 一、…

开发知识点-Git

团队协作-Git Giteegitee 创建仓库打开项目所在目录&#xff0c;右键选择Git Bush Here(你要确定电脑上已经安装了Git&#xff09;初始化本地仓库配置验证信息。 完美解决github访问速度慢介绍Git 与 SVN 区别IDEA 添加 gitee Gitee Git Gitee 大家都知道国内访问 Github 速度…

【前段基础入门之】=>CSS3新特性 响应式布局

文章目录 概念媒体查询媒体类型媒体特性媒体运算符 概念 所谓对响应式布局方案的理解&#xff0c;众说纷纭&#xff0c;核心点就是同一套代码在不同尺度屏幕下的布局呈现方式的不同 社区中有很多人分享&#xff0c;并列出了多种实现响应式布局的方案&#xff0c;比如【 rem&…

quickapp_快应用_快应用组件

快应用组件 web组件web页面与快应用页面通信网页接收/发送消息网页接收消息 快应用页面接收/发送消息给网页发送消息 通信前提- trustedurl list组件refresh组件语法error-使用refresh组件会改变页面高度&#xff01;refresh组件list组件实现下拉刷新 tab组件 web组件 作用&am…

微信抽奖活动怎么做

微信抽奖活动&#xff1a;打破传统&#xff0c;创新互动&#xff0c;带给你超乎想象的惊喜体验&#xff01; 随着互联网的飞速发展&#xff0c;人们越来越热衷于参与各种线上活动。而微信&#xff0c;作为中国最大的社交平台之一&#xff0c;自然成为了各种活动的聚集地。今天…

IntelliJ IDEA 安装 GitHub Copilot插件 (最新)

注意&#xff1a; GitHub Copilot 插件对IDEA最低版本要求是2021.2&#xff0c;建议直接用2023.3&#xff0c;一次到位反正后续要升级的。 各个版本的依赖关系&#xff0c;请参照&#xff1a; ##在线安装&#xff1a; 打开 IntelliJ IDEA扩展商店&#xff0c;输入 "Git…

IntelliJ IDEA启动一个普通的java web项目的配置

原创/朱季谦 这是我很久以前刚开始用IntelliJ IDEA时记录的笔记&#xff0c;应该是五年前的一篇笔记了。正好赶上最近离职了&#xff0c;可以有比较多的时间把以前的记录整理一下&#xff0c;可以让刚接触到IntelliJ IDEA的童鞋学习如何在IntelliJ IDEA引入一个单机版的jar形式…

【python零基础入门学习】python进阶篇之数据库连接-PyMysql-全都是干货-一起来学习吧!!!

本站以分享各种运维经验和运维所需要的技能为主 《python零基础入门》&#xff1a;python零基础入门学习 《python运维脚本》&#xff1a; python运维脚本实践 《shell》&#xff1a;shell学习 《terraform》持续更新中&#xff1a;terraform_Aws学习零基础入门到最佳实战 《k8…

【npm 错误】:npm ERR! code ERESOLVE、npm ERR! ERESOLVE could not resolve问题

用过npm的小伙伴都会有这么一个情况出现&#xff0c;就是npm install /npm install xxxx 会出现改一连串的错误&#xff0c;如下&#xff1a; 解决办法&#xff1a; 只要在npm install后面加上--legacy-peer-deps就可以解决问题,安装插件也一样 npm install --legacy-peer-dep…

原论文一比一复现 | 更换 RT-DETR 主干网络为 【VGG13】【VGG16】【VGG19】| 对比实验必备

本专栏内容均为博主独家全网首发,未经授权,任何形式的复制、转载、洗稿或传播行为均属违法侵权行为,一经发现将采取法律手段维护合法权益。我们对所有未经授权传播行为保留追究责任的权利。请尊重原创,支持创作者的努力,共同维护网络知识产权。 论文地址:https://arxiv.o…

V10服务器安装virt-manage

kvm是什么 KVM(Kernel-based Virtual Machine, 即内核级虚拟机) 是一个开源的系统虚拟化模块。它使用Linux自身的调度器进行管理&#xff0c;所以相对于Xen&#xff0c;其核心源码很少。目前KVM已成为学术界的主流VMM之一&#xff0c;它包含一个为处理器提供底层虚拟化 可加载…

[CISCN 2023 华北]pysym

源码如下 from flask import Flask, render_template, request, send_from_directory import os import random import string app Flask(__name__) app.config[UPLOAD_FOLDER]uploads app.route(/, methods[GET]) def index():return render_template(index.html) app.route…

IDEA写mybatis程序,java.io.IOException:Could not find resource mybatis-config.xml

找不到mybatis-config.xml 尝试maven idea:module&#xff0c;不是模块构造问题 尝试检验pom.xml&#xff0c;在编译模块添加了解析resources内容依旧不行 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.or…

vb.net 实时监控双门双向门禁控制板源代码

本示例使用设备介绍&#xff1a;实时网络双门双向门禁控制板可二次编程控制网络继电器远程开关-淘宝网 (taobao.com) Imports System.Net.Sockets Imports System.Net Imports System.Text Imports System.ThreadingImports System.Net.NetworkInformation Imports System.Man…