【C++】二叉搜索数

目录

一、二叉搜索树的概念

二、二叉搜索树的模拟实现

1、定义节点

2、构造二叉树

3、析构二叉树

​4、拷贝二叉树

5、二叉树赋值

6、插入节点

🌟【非递归方式】

🌟【递归方式】

7、打印节点

 8、搜索节点

🌟【非递归方式】

🌟【递归方式】

9、删除节点(重要)

🌟【非递归方式】

🌟【递归方式】

10、完整代码

三、二叉搜索树的应用

K模型&&KV模型


一、二叉搜索树的概念

  • 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
  • 若它的子树不为空,则左子树上所有节点的值都小于根节点的值
  • 若它的子树不为空,则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树

二、二叉搜索树的模拟实现

1、定义节点

首先需要确定二叉树的节点,有左节点、和右节点以及节点的值。

2、构造二叉树

3、析构二叉树

遍历左右二叉树,删除节点并将节点置为空。

 4、拷贝二叉树

拷贝二叉树,我们不能使用insert来一个一个插入,因为inset带有筛选的功能,最后结果顺序会不同的。
我们使用类似于前序遍历的方式,进行拷贝,遍历到哪就相当于拷贝到哪。
首先遇到空就返回。1.拷贝结点 2.递归拷贝左子树3.递归拷贝右子树。4.最后将拷贝结点返回。

5、二叉树赋值

6、插入节点

🌟【非递归方式】

过程:

a. 树为空,则直接新增节点,赋值给root指针

b. 树不空,按二叉搜索树性质查找插入位置,插入新节点 

步骤:

a.当插入的结点值key要比根结点大,则key需要到根的右树进行比较,当key的值比根结点小,则key需要到根的左树进行比较,当key的值与根结点相同时,则返回fasle,按照这样的方式循环下去,当要比较的结点为空时,则就可以将结点插入到这个位置上了。每次比较中都要记录父节点的位置,因为最后需要链接起来。
b.最后链接起来需要和父结点比较一下才能知道链接到父节点的左边还是右边。如果大于父节点则链接到右边,如果小于父节点则连接到左边。

 

🌟【递归方式】

递归实现方式的思想其实是一样的,如果节点为空,就创造一个节点。如果不为空,就比较节点与需要插入值的大小,如果比节点大就插入右边,如果比节点小就插入左边,遇到空就新建一个节点。当递归结束时,就可以将开辟好结点链接起来。(递归的过程就是不断的在创建结点,回来的过程就是不断地将结点链接起来)。这里不需要像非递归那样,每次比较都需要记录父节点的位置,我们这里用一个引用就可以轻松解决问题!我们的指针参数使用引用,即子函数的参数是递归函数参数的别名。

 

7、打印节点

运用递归,分别打印 root 左边和右边的数值,遇到空就返回。

 

 8、搜索节点

过程:

a.从根开始比较,查找,比根大则往右边走查找,比根小则往左边走查找。如果没有找到就返回 false.

b.最多查找高度次,走到到空,还没找到,这个值不存在。

🌟【非递归方式】

🌟【递归方式】

当所要找的节点小于根节点时,递归到左子树去找;当所要找的节点大于根节点时,递归到右节点去找。当等于所要找的节点时,返回真。如果一直找不到则返回假。

 

9、删除节点(重要)

首先查找元素是否在二叉搜索树中,如果不存在,则返回, 否则要删除的结点可能分下面四种情 况:

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

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

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

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

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

a.当删除结点没有孩子节点时,使用托孤法,将父节点与空链接起来。--直接删除
b.当删除结点只有一个孩子节点时,使用托孤法,将父节点与孤结点链接起来。--直接删除
c.当删除结点有两个孩子节点时,使用找保姆法,找一个可以替代本身的结点。交换这两个结点,删除这个替换结点。一般来说是将root节点和左子树的最大结点或者是右子树的最小结点相交换。--替换法删除

不管怎么删除都要遵循先查找后删除的原则,当要删除的数字比root大,就往右边查找;当要删除的数字比root小就往左边查找。 

🌟【非递归方式】

 1)当只有右孩子节点时,左孩子节点为空时

首先要判断父节点是不是 root,然后判断要删除的节点时父节点的左孩子节点还是右孩子节点,如果是左孩子节点就将删除节点的孩子节点链接上父节点的左边;如果是右孩子节点就将删除节点的孩子节点链接上父节点的右边。

 2)当只有左孩子节点时,右孩子节点为空时

 3)当存在两个孩子节点时

如果我们直接删除,那可能需要改变树的结构,这样会很复杂。我们可以找到需要删除节点的左边最大值,右边最小值相交换,然后再删除。

 【测试运行】

🌟【递归方式】

当key比根结点大的时候,递归到右子树进行比较,当key比根结点值小的时候,递归到左子树进行比较,当key跟结点值相同时,表明找到了。找到后就要分三种情况讨论。

【当存在一个孩子结点时】
不同于非递归版本需要记录父节点,递归版本不需要记录父节点,因为一个引用,让我们省去了很多麻烦。root 就是父节点的左指针或者右指针。托孤直接托孤给root即可。因为root就是父节点的左右指针指向。
当右子树不存在时,直接将要删除结点的左子树托孤给root。当左子树不存在时,直接将要删除结点的右子树托孤给root。

【当存在两个孩子结点时】
当存在两个孩子结点时,还是需要使用保姆法,首先找到保姆结点,然后将要删除结点的值与保姆结点值交换。这样就转化成子问题了。从整棵树来看,因为保姆结点和删除结点交换,而改变了搜索二叉树的特性。不能使用了。
但从左子树来看,还是完整的二叉搜索树,并且要删除结点就只有一个孩子,直接转化为上面的问题。

10、完整代码

#define  _CRT_SECURE_NO_WARNINGS
#pragma oncetemplate<class K>
struct BSTreeNode
{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;//初始化BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}
};template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public:/*BSTree():_root(nullptr){}*/BSTree() = default; // 制定强制生成默认构造BSTree(const BSTree<K>& t){_root = Copy(t._root);}BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}//~BSTree()//{//	Destroy(_root);//	//_root = nullptr;//}//非递归方式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;}//递归方式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){return _InsertR(root->_right, key);}else if (root->_key > key){return _InsertR(root->_left, key);}else{return false;}}//非递归方式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 FindR(const K& key){return _FindR(_root, key);}bool _FindR(Node* root, const K& key){if (root == nullptr)return false;if (root->_key == key)return true;if (root->_key < key)return _FindR(root->_right, key);elsereturn _FindR(root->_left, key);}void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}//非递归方式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{// 删除// 1、左为空if (cur->_left == nullptr){//如果cur是根节点,直接删除根节点,更改root值if (cur == _root){_root = cur->_right;}else{//判断cur 是父节点的左孩子还是右孩子if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;} // 2、右为空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* pminRight = cur;Node* minRight = cur->_right;while (minRight->_left){pminRight = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (pminRight->_left == minRight){pminRight->_left = minRight->_right;}else{pminRight->_right = minRight->_right;}delete minRight;}return true;}}return false;}//递归方式bool EraseR(const K& key){return _EraseR(_root, key);}bool _EraseR(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key < key){return _EraseR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else{Node* del = root;// 开始准备删除if (root->_right == nullptr){root = root->_left;}else if (root->_left == nullptr){root = root->_right;}else{Node* maxleft = root->_left;while (maxleft->_right){maxleft = maxleft->_right;}swap(root->_key, maxleft->_key);return _EraseR(root->_left, key);}delete del;return true;}}~BSTree(){Destroy(_root);//_root = nullptr;}void Destroy(Node*& root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}BSTree(const BSTree<K>& t){_root = Copy(t._root);}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}
private:Node* _root = nullptr;
};

三、二叉搜索树的应用

K模型&&KV模型

K模型即只有key作为关键码,结构中只需要存储Key即可,关键码即为需要搜索到的值。

比如:给一个单词word,判断该单词是否拼写正确,具体方式如下: 以词库中所有单词集合中的每个单词作为key,构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在,存在则拼写正确,不存在则拼写错误。

KV模型:每一个关键码key,都有与之对应的值Value,即的键值对。该种方式在现实生活中非常常见: 比如英汉词典就是英文与中文的对应关系,通过英文可以快速找到与其对应的中文,英文单词与其对应的中文就构成一种键值对; 再比如统计单词次数,统计成功后,给定单词就可快速找到其出现的次数,单词与其出现次数就是就构成一种键值对。

【测试代码】 

template<class K, class V>struct BSTreeNode{BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _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{typedef BSTreeNode<K, V> Node;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){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;}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;}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{// 删除// 1、左为空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;} // 2、右为空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* pminRight = cur;Node* minRight = cur->_right;while (minRight->_left){pminRight = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (pminRight->_left == minRight){pminRight->_left = minRight->_right;}else{pminRight->_right = minRight->_right;}delete minRight;}return true;}}return false;}void InOrder(){_InOrder(_root);cout << endl;}protected:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);}private:Node* _root = nullptr;};

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

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

相关文章

DDR3接口

mig IP核的配置 首先添加mig IP核   然后确认以下工程信息&#xff0c;主要是芯片型号以及编译环境&#xff0c;没什么问题后点击next.   如下图所示&#xff0c;这一页选择"Create Design"&#xff0c;在"Component Name"一栏设置该IP元件的名称&…

Prometheus+grafana环境搭建Nginx(docker+二进制两种方式安装)(六)

由于所有组件写一篇幅过长&#xff0c;所以每个组件分一篇方便查看&#xff0c;前五篇链接如下 Prometheusgrafana环境搭建方法及流程两种方式(docker和源码包)(一)-CSDN博客 Prometheusgrafana环境搭建rabbitmq(docker二进制两种方式安装)(二)-CSDN博客 Prometheusgrafana环…

第十届蓝桥杯大赛个人赛省赛(软件类) CC++ 研究生组2.0

A立方和 #include<iostream> #include<cmath> using namespace std; int main(){int n, t, flag, x;long long ans 0;for(int i 1; i < 2019; i){t i;flag 0;while(t && !flag){x t % 10;if(x 2 || x 0 || x 1 || x 9) flag 1;t / 10;}if(fl…

prompt 工程案例

目录 prompt 工程是什么&#xff1f; 案例 vllm 推理加速框架 prompt 工程是什么&#xff1f; prompt&#xff1a;提示词&#xff0c;也就是我们使用网页版输入给大模型的内容就叫 prompt&#xff0c;那什么是 prompt 工程呢&#xff1f; 简单理解其实就是利用编写的 prom…

3个 JavaScript 字符串截取方法

在 JavaScript 中&#xff0c;可以使用 substr()、slice() 和 substring() 方法截取字符串. substring() substring() 方法返回一个字符串在开始索引到结束索引之间的一个子集&#xff0c;或从开始索引直到字符串的末尾的一个子集。语法如下&#xff1a; str.substring(inde…

cmake中报错undefined reference to `pthread_create‘的解决方法

出现报错&#xff1a; 解决方法 一般网上会建议在终端指令g/gcc后面增加参数-pthread,但是我们没有用到g/gcc指令. cmake的解决方法是在CMakeLists.txt文件里面增加一行. add_executable(server2 main.cpp) target_link_libraries(server2 pthread)问题就解决了

uniapp切换中英文

一、安装 npm install uni-i18n --save 二、创建中英文切换的文件 1.英文en.js文件 2.中文zh_CN.js文件 三、 main.js中引用 // Vue i18n 国际化 import VueI18n from /common/vue-i18n.min.js; Vue.use(VueI18n);// i18n 部分的配置&#xff0c;引入语言包&#xff0c;注意路…

c# wpf template itemtemplate+ListBox

1.概要 2.代码 <Window x:Class"WpfApp2.Window7"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schemas.microsoft.com/expression/blend/…

SCP 从Linux快速下载文件到Windows本地

需求&#xff1a;通过mobaxterm将大文件拖动到windows本地速度太慢。 环境&#xff1a;本地是Windows&#xff0c;安装了Git。 操作&#xff1a;进入文件夹内&#xff0c;鼠标右键&#xff0c;点击Git Bash here&#xff0c;然后输入命令即可。这样的话&#xff0c;其实自己本…

基于SpringBoot+微信小程序的农产品销售平台

一、项目背景介绍&#xff1a; 随着人们收入的不断增加、生活水平的普遍提高,对生活质量的要求也日益凸显。而作为关乎每个人的生命、健康安全的食品卫生、质量无疑更被人们所重视。所以,… 2. 其他国家的绿色有机食品所占其国家食品市场比重比较大,如德国在99年便已达到40%,美…

基于51单片机和MAX1898的智能手机充电器设计

**单片机设计介绍&#xff0c;基于51单片机和MAX1898的智能手机充电器设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于51单片机和MAX1898的智能手机充电器设计概要 一、引言 随着智能手机的普及&#xff0c;其电池续航…

AcWing1402.星空之夜

【题目链接】1402. 星空之夜 - AcWing题库 夜空深处&#xff0c;闪亮的星星以星群的形式出现在人们眼中&#xff0c;形态万千。 一个星群是指一组非空的在水平&#xff0c;垂直或对角线方向相邻的星星的集合。 一个星群不能是一个更大星群的一部分。 星群可能是相似的。 如…

在深度学习模型中引入先验

当面对复杂问题的时候&#xff0c;在深度学习模型提取特征的过程中完全抛弃知识是非常不明智的策略。虽然有很多研究者在深度网络处理数据之前&#xff0c;利用具有某种知识的模型驱动方法对数据进行预处理&#xff0c;但是这种方法没有进行实质性地改造深度网络&#xff0c;且…

【美团笔试题汇总】2023-09-02-美团春秋招笔试题-三语言题解(CPP/Python/Java)

&#x1f36d; 大家好这里是KK爱Coding &#xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新美团近期的春秋招笔试题汇总&#xff5e; &#x1f4bb; ACM银牌&#x1f948;| 多次AK大厂笔试 &#xff5c; 编程一对一辅导 &#x1f44f; 感谢大家的订阅➕ 和 喜欢&#x1f…

Windows 2008虚拟机安装、安装VM Tools、快照和链接克隆、添加硬盘修改格式为GPT

一、安装vmware workstation软件 VMware workstation的安装介质&#xff0c;获取路径&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1AUAw_--yjZAUPbsR7StOJQ 提取码&#xff1a;umz1 所在目录&#xff1a;\vmware\VMware workstation 15.1.0 1.找到百度网盘中vmwa…

数字乡村创新实践探索:科技赋能农业现代化与乡村治理体系现代化同步推进

随着信息技术的飞速发展&#xff0c;数字乡村作为乡村振兴的重要战略方向&#xff0c;正日益成为推动农业现代化和乡村治理体系现代化的关键力量。科技赋能下的数字乡村&#xff0c;不仅提高了农业生产的效率和品质&#xff0c;也为乡村治理带来了新的机遇和挑战。本文旨在探讨…

哈希(数字+字符串)

模拟散列表 维护一个集合&#xff0c;支持如下几种操作&#xff1a; I x&#xff0c;插入一个整数 x&#xff1b;Q x&#xff0c;询问整数 x 是否在集合中出现过&#xff1b; 现在要进行 N 次操作&#xff0c;对于每个询问操作输出对应的结果。 输入格式 第一行包含整数 …

测开——Java、python、SQL、数据结构面试题整理

一、Java 1.Java中finally、final、finalize的区别 1.性质不同 &#xff08;1&#xff09;final为关键字; &#xff08;2&#xff09;finalize()为方法; &#xff08;3&#xff09;finally为为区块标志,用于try语句中; 2. 作用 &#xff08;1&#xff09;final为用于标识…

每日面经分享(Git经典题目,Git入门)

1. GitHub是什么 a. Git是一个分布式版本控制系统&#xff0c;作用是跟踪、管理和协调软件开发项目中的代码更改。 b. 提供了一种有效的方式来管理代码的版本历史&#xff0c;以及多人协作开发的能力。 2. Git的作用有哪些 a. 版本控制&#xff1a;Git可以记录每次代码更改的…