【C++】搜索二叉树底层实现

目录

一,概念

二,实现分析

1.  插入

(1.)非递归版本 

 (2.)递归版本

 2. 打印搜索二叉树

3.查找函数

(1.)非递归版本

(2.)递归版本

4. 删除函数(重难点) 

易错点分析,包你学会

(1.)删除目标,没有左右孩子

(2.)删除目标,只有一个孩子

(3.)删除目标,有两个孩子

代码

(1.)非递归版本 

(2.)递归版本

5. 析构函数

6.拷贝构造 

 三,应用

 四,搜索二叉树的缺陷及优化

五,代码汇总

结语


一,概念

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

为啥又被称作二叉排序树呢? 当该树被层序遍历时,就是升序。

二,实现分析

实验例子:

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

1.  插入

(1.)非递归版本 

a、从根开始比较,查找,比根大则往右边走查找,比根小则往左边走查找。
b、最多查找高度次,走到到空,还没找到,这个值不存在。

 比较简单这里就直接放代码:

template <class K>
class BinarySeaTree_node
{typedef BinarySeaTree_node<K> BST_node;
public:BinarySeaTree_node(const K& val): _val(val),_left(nullptr),_right(nullptr){}K _val;BST_node* _left;BST_node* _right;
};template <class T>
class BSTree
{typedef BinarySeaTree_node<T> BST_node;
private:BST_node* root = nullptr;public:bool Insert(const T& val){BST_node* key = new BST_node(val);BST_node* cur = root;BST_node* parent = nullptr;while (cur){if (key->_val < cur->_val){parent = cur;cur = cur->_left;}else if (key->_val > cur->_val){parent = cur;cur = cur->_right;}else{return 0;}}// 查询好位置后,建立链接if (!root){root = key;return 0;}if (key->_val > parent->_val){parent->_right = key;}else{parent->_left = key;}return 1;}
};

 (2.)递归版本

这里面整了个活,大家注意了!!!

bool Re_Insert(const T& val){  return Re_Insert_table(root, val);}bool Re_Insert_table(BST_node*& node, const T& val){if (node == nullptr){node = new BST_node(val);return 1;}if (val < node->_left){return Re_Insert_table(node->_left, val);}else if (val > node->_right){ return Re_Insert_table(node->_right, val);}else{return 0;}}

这里方便大家理解,我给大家花一个递归展开图。

 2. 打印搜索二叉树

 

插入的具体过程如下:
a. 树为空,则直接新增节点,赋值给root指针
b. 树不空,按二叉搜索树性质查找插入位置,插入新节点

这里也是仅做代码分享: 

void Print_table() { Re_Print(root); }void Re_Print(const BST_node* node){if (node == nullptr)return;Re_Print(node->_left);cout << node->_val << " ";Re_Print(node->_right);}

3.查找函数

思路:其实也没啥思路,比父结点小,就找左边,否则找右边。 

(1.)非递归版本

BST_node* Find(const T& val){//直接跟寻找位置一样BST_node* parent = nullptr;BST_node* cur = root; // 以返回cur的方式返回while (cur)   // 非递归版本{if (val < cur->_val){parent = cur;cur = cur->_left;}else if (val > cur->_val){parent = cur;cur = cur->_right;}else{return cur;}}return cur;}

(2.)递归版本

BST_node* Re_Find(const T& val){   return Re_Find_table(root, val); }BST_node* Re_Find_table(BST_node* node, const T& val){if (node == nullptr)return nullptr;if (val < node->_val){return Re_Find_table(node->_left, val);}else if (val > node->_val){return Re_Find_table(node->_right, val);}else{return node;}}

4. 删除函数(重难点) 

我们简单寻找了一下思路,如下:

但这些思路只是大概方向,其中藏着许多的坑点,诺接下来我来带大家,对这些易错点进行分析

首先是查询到目标:

这个比较简单,这里不做解释。 

       //首先寻找到目标,并且记录到parentBST_node* parent = nullptr;BST_node* cur = root;while (cur){if (val < cur->_val){parent = cur;cur = cur->_left;}else if (val > cur->_val){parent = cur;cur = cur->_right;}else{break;}}if (!cur){return 0;}

易错点分析,包你学会

(1.)删除目标,没有左右孩子

 

(2.)删除目标,只有一个孩子

一般的思路: 

 但,这是有漏洞的!

诺:

(3.)删除目标,有两个孩子

 好啦,前菜上完了来看看,本次的大菜。

代码

(1.)非递归版本 

bool Erase(const T& val){//首先寻找到指定值,并且记录到parentBST_node* parent = nullptr;BST_node* cur = root;while (cur){if (val < cur->_val){parent = cur;cur = cur->_left;}else if (val > cur->_val){parent = cur;cur = cur->_right;}else{break;}}if (!cur){return 0;}// 查询成功,开始删除if (!cur->_left && !cur->_right) // cur没有左右孩子{   // 当要删除目标是根if (cur == root){root = nullptr;delete cur;}// 判断cur是左右孩子else if (cur->_val < parent->_val){parent->_left = nullptr;delete cur;}else{parent->_right = nullptr;delete cur;}return 1;}else if (!cur->_left || !cur->_right)  // 只有一个孩子{if (!parent)  // 判断是否是目标是根{root = cur->_left != nullptr ? cur->_left : cur->_right;delete cur;}// 判断cur为啥孩子else if (cur->_val < parent->_val) // 左侧{parent->_left = cur->_left != nullptr ? cur->_left : cur->_right;delete cur;}else                          // 右侧{parent->_right = cur->_left != nullptr ? cur->_left : cur->_right;delete cur;}}else   // 有2个孩子{  // 使用左侧最大的孩子来领养// 寻找左侧最大BST_node* maxnode = cur->_left;BST_node* max_parent = cur;while (maxnode->_right){max_parent = maxnode;maxnode = maxnode->_right;}// 现在又进入一种特殊情况,1.max_parent就没进入循环,2.进入了循环if (max_parent == cur){max_parent->_left = maxnode->_left;}else{max_parent->_right = maxnode->_left;}// 值转移cur->_val = maxnode->_val;delete maxnode;}return 1;}

(2.)递归版本

bool Re_Erease( const T& val){return Re_Erease_table(root, val);}bool Re_Erease_table(BST_node*& node, const T& val){// 首先我们先找到值if (node == nullptr){return 0; // 如果访问到了空,则说明删除失败,原因是:不存在}if (val < node->_val){return Re_Erease_table(node->_left, val);}else if (val > node->_val){return Re_Erease_table(node->_right, val);}else{// 开始删除目标数据。方法如下;// 1. 就按照非递归的思路,不用改多少代码 // 2. 使用递归方法,优势就是代码简洁// 这里使用方法2BST_node* del = node;  // 保存每次访问的对象,如果是目标,就备份好了if (node->_left == nullptr){node = node->_right;}else if (node->_right == nullptr){node = node->_left;}else{//处理左右都有孩子的目标// 左侧查找最大值,右侧查找最小值BST_node* max_node = node->_left;while (max_node->_right){max_node = max_node->_right;}// 完成循环后,max_node最多有左孩子,然后数据交换,我们以目标左侧树为起点// 再次递归删除替换数据。swap(max_node->_val, node->_val);return Re_Erease_table(node->_left, val); //已经完成删除,就直接退出,以免触发删除delete}			//处理前两种情况delete del;}}

5. 析构函数

思路:

~BSTree(){  Distroy_Re(root);root = nullptr;   }
void Distroy_Re(BST_node*& node) // 我们采用递归删除{if (node == nullptr)return ;// 先处理左右孩子Distroy_Re(node->_left);Distroy_Re(node->_right);delete node;node = nullptr;}

6.拷贝构造 

    // 我们实现了拷贝构造,默认构造函数则不会生成 // 解决方案:1.实现构造函数 2.使用default关键字,强制生成默认构造BSTree()                 {}// BSTree() = defaultBSTree(const BSTree& Tree) // 拷贝构造{root = copy(Tree.root);}BST_node* copy(BST_node* root){if (root == nullptr)return nullptr;BST_node* new_node = new BST_node(root->_val);new_node->_left = copy(root->_left);new_node->_right = copy(root->_right);return new_node;}

 三,应用

1. K模型:K模型即只有key作为关键码,结构中只需要存储Key即可,关键码即为需要搜索到
的值
比如: 给一个单词word,判断该单词是否拼写正确,具体方式如下:以词库中所有单词集合中的每个单词作为key,构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在,存在则拼写正确,不存在则拼写错误。
2. KV模型:每一个关键码key,都有与之对应的值Value,即<Key, Value>的键值对。该种方式在现实生活中非常常见:
比如 英汉词典就是英文与中文的对应关系,通过英文可以快速找到与其对应的中文,英文单词与其对应的中文<word, chinese>就构成一种键值对;
再比如 统计单词次数,统计成功后,给定单词就可快速找到其出现的次数, 单词与其出现次数就是<word, count>就构成一种键值对(这个比较简单,修改一下即可)

 四,搜索二叉树的缺陷及优化

对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数,即结点越深,则比较次数越多。
但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:

最坏情况:N

平均情况:O(logN)

问题:如果退化成单支树,二叉搜索树的性能就失去了。那能否进行改进,不论按照什么次序插入关键码,二叉搜索树的性能都能达到最优?那么我们后续章节学习的AVL树和红黑树就可以上场了。

五,代码汇总

namespace key
{
template <class K>
class BinarySeaTree_node
{typedef BinarySeaTree_node<K> BST_node;
public:BinarySeaTree_node(const K& val): _val(val),_left(nullptr),_right(nullptr){}K _val;BST_node* _left;BST_node* _right;
};template <class T>
class BSTree
{
public:typedef BinarySeaTree_node<T> BST_node;// 我们实现了拷贝构造,默认构造函数则不会生成 // 解决方案:1.实现构造函数 2.使用default关键字,强制生成默认构造BSTree(){}// BSTree() = defaultBSTree(const BSTree& Tree) // 拷贝构造{root = copy(Tree.root);}BSTree<T>& operator=(BSTree<T> t){swap(root, t.root);return *this;}BST_node* copy(BST_node* root){if (root == nullptr)return nullptr;BST_node* new_node = new BST_node(root->_val);new_node->_left = copy(root->_left);new_node->_right = copy(root->_right);return new_node;}bool Re_Insert(const T& val) { return Re_Insert_table(root, val); }void Re_Print() { Re_Print_table(root); }bool Re_Erease(const T& val) { return Re_Erease_table(root, val); }BST_node* Re_Find(const T& val) { return Re_Find_table(root, val); }bool Insert(const T& val){BST_node* key = new BST_node(val);BST_node* cur = root;BST_node* parent = nullptr;while (cur){if (key->_val < cur->_val){parent = cur;cur = cur->_left;}else if (key->_val > cur->_val){parent = cur;cur = cur->_right;}else{return 0;}}// 查询好位置后,建立链接if (!root){root = key;return 0;}if (key->_val > parent->_val){parent->_right = key;}else{parent->_left = key;}return 1;}BST_node* Find(const T& val){//直接跟寻找位置一样BST_node* parent = nullptr;BST_node* cur = root; // 以返回cur的方式返回while (cur)   // 非递归版本{if (val < cur->_val){parent = cur;cur = cur->_left;}else if (val > cur->_val){parent = cur;cur = cur->_right;}else{return cur;}}return cur;}bool Erase(const T& val){//首先寻找到指定值,并且记录到parentBST_node* parent = nullptr;BST_node* cur = root;while (cur){if (val < cur->_val){parent = cur;cur = cur->_left;}else if (val > cur->_val){parent = cur;cur = cur->_right;}else{break;}}if (!cur){return 0;}// 查询成功,开始删除if (!cur->_left && !cur->_right) // cur没有左右孩子{   // 当要删除目标是根if (cur == root){root = nullptr;delete cur;}// 判断cur是左右孩子else if (cur->_val < parent->_val){parent->_left = nullptr;delete cur;}else{parent->_right = nullptr;delete cur;}return 1;}else if (!cur->_left || !cur->_right)  // 只有一个孩子{if (!parent)  // 判断是否是目标是根{root = cur->_left != nullptr ? cur->_left : cur->_right;delete cur;}// 判断cur为啥孩子else if (cur->_val < parent->_val) // 左侧{parent->_left = cur->_left != nullptr ? cur->_left : cur->_right;delete cur;}else                          // 右侧{parent->_right = cur->_left != nullptr ? cur->_left : cur->_right;delete cur;}}else   // 有2个孩子{  // 使用左侧最大的孩子来领养// 寻找左侧最大BST_node* maxnode = cur->_left;BST_node* max_parent = cur;while (maxnode->_right){max_parent = maxnode;maxnode = maxnode->_right;}// 现在又进入一种特殊情况,1.max_parent就没进入循环,2.进入了循环if (max_parent == cur){max_parent->_left = maxnode->_left;}else{max_parent->_right = maxnode->_left;}// 值转移cur->_val = maxnode->_val;delete maxnode;}return 1;}~BSTree(){Distroy_Re(root);root = nullptr;}protected:bool Re_Insert_table(BST_node*& node, const T& val){if (node == nullptr){node = new BST_node(val);return 1;}if (val < node->_val){return Re_Insert_table(node->_left, val);}else if (val > node->_val){return Re_Insert_table(node->_right, val);}else{return 0;}}void Re_Print_table(const BST_node* node){if (node == nullptr)return;Re_Print_table(node->_left);cout << node->_val << " ";Re_Print_table(node->_right);}BST_node* Re_Find_table(BST_node* node, const T& val){if (node == nullptr)return nullptr;if (val < node->_val){return Re_Find_table(node->_left, val);}else if (val > node->_val){return Re_Find_table(node->_right, val);}else{return node;}}bool Re_Erease_table(BST_node*& node, const T& val){// 首先我们先找到值if (node == nullptr){return 0; // 如果访问到了空,则说明删除失败,原因是:不存在}if (val < node->_val){return Re_Erease_table(node->_left, val);}else if (val > node->_val){return Re_Erease_table(node->_right, val);}else{// 开始删除目标数据。方法如下;// 1. 就按照非递归的思路,不用改多少代码 // 2. 使用递归方法,优势就是代码简洁// 这里使用方法2BST_node* del = node;  // 保存每次访问的对象,如果是目标,就备份好了if (node->_left == nullptr){node = node->_right;}else if (node->_right == nullptr){node = node->_left;}else{//处理左右都有孩子的目标// 左侧查找最大值,右侧查找最小值BST_node* max_node = node->_left;while (max_node->_right){max_node = max_node->_right;}// 完成循环后,max_node最多有左孩子,然后数据交换,我们以目标左侧树为起点// 再次递归删除替换数据。swap(max_node->_val, node->_val);return Re_Erease_table(node->_left, val); //已经完成删除,就直接退出,以免触发删除delete}// 查找到删除数据delete del;}}void Distroy_Re(BST_node*& node) // 我们采用递归删除{if (node == nullptr)return;// 先处理左右孩子Distroy_Re(node->_left);Distroy_Re(node->_right);delete node;node = nullptr;}
private:BST_node* root = nullptr;};
}

结语

   本小节就到这里了,感谢小伙伴的浏览,如果有什么建议,欢迎在评论区评论,如果给小伙伴带来一些收获请留下你的小赞,你的点赞和关注将会成为博主创作的动力

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

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

相关文章

stm32--独立看门狗

最近学习到独立看门狗&#xff0c;总结下笔记 1.看门狗的作用&#xff1a;防止程序异常跑飞&#xff0c;跑飞时&#xff0c;进行系统复位&#xff0c;从而不会导致代码瘫痪&#xff0c;奔溃卡死在某段程序。 2.看门狗其实是12bit递减计数器&#xff0c;&#xff0c;减到0会产…

入户式防汛报警器是什么?

入户式防汛报警器是一款能够和雨量气象监测设备搭配的仪器&#xff0c;是集实时监测、信息显示、多时段声光报警功能的监测报警设备&#xff0c;支持不同级别的声光报警。 当监测要素超过设定的危险警戒值时设备发出报警声&#xff0c;提醒居民做好防汛&#xff08;转移&#…

new/delete, malloc/free 内存泄漏如何检测

区别&#xff1a; 首先new/delete是运算符&#xff0c;malloc/free是库函数。malloc/free只开辟内存不初始化&#xff1b;new/delete及开辟内存也初始化。抛出异常的方式&#xff1a;new/delete开辟失败使用抛出bad_alloc&#xff1b;malloc/free通过返回值判断。malloc和new区…

天然气跟踪监管系统功能模块实现

天然气跟踪监管系统功能模块实现 1. 数据库查询3. 仓库管理&#xff08;1&#xff09;仓库查询与展示。代码说明 1. 数据库查询 救援物资跟踪监管系统的绝大部分功能都会涉及关系数据库中的业务数据&#xff0c;因此关系数据库的查询是本系统不可或缺的重要部分。 本系统中的数…

Vivado初体验LED工程

文章目录 前言一、PL 和 PS二、LED 硬件介绍三、创建 Vivado 工程四、创建 Verilog HDL 文件五、添加管脚约束六、添加时序约束七、生成 BIT 文件八、仿真测试九、下载测试 前言 本节我们要做的是熟练使用 Vivado 创建工程并实现对 LED 灯控制&#xff0c;每秒钟控制开发板上的…

vue3中css使用script中定义的变量

代码 <template><div class"box">haha</div> </template><script setup lang"ts"> const boxWidth 500px </script><style lang"scss"> .box {width: v-bind(boxWidth);height: 200px;background-c…

聚观早报 | iPhone 15系列正式发布;月饼专利申请超10000项

【聚观365】9月14日消息 iPhone 15系列正式发布 月饼专利申请超10000项 “五个女博士”自建研究院 2023中国民营企业研发十强公布 华为和小米达成全球专利交叉许可协议 iPhone 15系列正式发布 2023年苹果秋季新品发布会如期而至。发布会上&#xff0c;苹果发布了iPhone 1…

innovus: 各种padding一勺烩

我正在「拾陆楼」和朋友们讨论有趣的话题&#xff0c;你⼀起来吧&#xff1f; 拾陆楼知识星球入口 instance padding specifyInstPad $instance_name -left/-right $site_num site_num指的是padding的大小以site宽度为单位。 module padding setPlaceMode -place_global_mo…

Java版分布式微服务云开发架构 Spring Cloud+Spring Boot+Mybatis 电子招标采购系统功能清单

项目说明 随着公司的快速发展&#xff0c;企业人员和经营规模不断壮大&#xff0c;公司对内部招采管理的提升提出了更高的要求。在企业里建立一个公平、公开、公正的采购环境&#xff0c;最大限度控制采购成本至关重要。符合国家电子招投标法律法规及相关规范&#xff0c;以及审…

HNU小学期工训-STC15单片机模型大作业实验报告

STC15单片机模型大作业实验报告 全称&#xff1a;基于STC15单片机与OLED显示模块&PC端演示的多功能声光温振时钟智能手表模型 计科210X 甘晴void 202108010XXX 【请注意&#xff1a;本作业入选优秀范例&#xff0c;直接照抄源码有很大风险】 【建议理解原理之后作改动】 …

阿里云无影电脑:免费体验无影云电脑3个月

阿里云无影云电脑免费领取流程&#xff0c;免费无影云电脑配置为4核8G&#xff0c;可以免费使用3个月&#xff0c;阿里云百科分享阿里云无影云电脑&#xff08;云桌面&#xff09;免费申请入口、申请流程及免费使用限制条件说明&#xff1a; 目录 阿里云无影云电脑免费申请入…

Ansible自动化:简化你的运维任务

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…

Paper Reading: RSPrompter,基于视觉基础模型的遥感实例分割提示学习

目录 简介目标工作重点方法实验总结 简介 题目&#xff1a;《RSPrompter: Learning to Prompt for Remote Sensing Instance Segmentation based on Visual Foundation Model 》&#xff0c;基于视觉基础模型的遥感实例分割提示学习 日期&#xff1a;2023.6.28 单位&#xf…

STL list

文章目录 一、list 类的模拟实现 list 是一个带头双向循环链表&#xff0c;可以存储任意类型 模板参数 T 表示存储元素的类型&#xff0c;Alloc 是空间配置器&#xff0c;一般不用传 一、list 类的模拟实现 iterator 和 const_iterator 除了下述不同外&#xff0c;其他代码基…

GPIO子系统编写LED灯的驱动、linux内核定时器

一、GPIO子系统 1.概念&#xff1a; 一个芯片厂商生产出芯片后会给linux提供一个当前芯片中gpio外设的驱动&#xff0c;我们当前只需要调用对应的厂商驱动即可完成硬件的控制。而linux内核源码中的gpio厂商驱动有很多&#xff0c;这里linux内核对厂商驱动做了一些封装&#x…

【管理运筹学】第 8 章 | 动态规划(2,动态规划的基本思想)

文章目录 引言2.2 动态规划的基本思想 写在最后 引言 承接前文&#xff0c;介绍完基本概念后&#xff0c;我们来学习动态规划的基本思想&#xff0c;用上一篇文章的最短路问题来配合说明。 2.2 动态规划的基本思想 最短路问题中的网络如下图所示&#xff0c;从 A 到 E 可以分…

零基础学前端(四)重点讲解 CSS

1. 该篇适用于从零基础学习前端的小白 2. 初学者不懂代码得含义也要坚持模仿逐行敲代码&#xff0c;以身体感悟带动头脑去理解新知识 3. 初学者切忌&#xff0c;不要眼花缭乱&#xff0c;不要四处找其它文档&#xff0c;要坚定一个教授者的方式&#xff0c;将其学通透&#xff…

SpringMVC之自定义注解

一.什么是SpringMVC之自定义注解 二.Java注解简介 Java注解分类 JDK元注解 三.自定义注解简介 自定义注解的分类 四.自定义注解的基本案例 案例一&#xff08;获取类与方法上的注解值&#xff09; 案例二&#xff08;获取类属性上的注解属性值&#xff09; 案例三&a…

MyBatis笔记

Mybatis简介 MyBatis历史 MyBatis最初是Apache的一个开源项目iBatis, 2010年6月这个项目由Apache Software Foundation迁移到了Google Code。随着开发团队转投Google Code旗下&#xff0c;iBatis3.x正式更名为MyBatis。代码于2013年11月迁移到GithubiBatis一词来源于“intern…

【数据结构与算法】不就是数据结构

前言 嗨喽小伙伴们你们好呀&#xff0c;好久不见了,我已经好久没更新博文了&#xff01;之前因为实习没有时间去写博文&#xff0c;现在已经回归校园了。我看了本学期的课程中有数据结构这门课程&#xff08;这么课程特别重要&#xff09;&#xff0c;因为之前学过一点&#xf…