二叉搜索树的实现[C++]

文章目录

  • 搜索二叉树
    • 概念
    • 二叉搜索树的功能
      • 查找
  • 实现搜索二叉树
    • 节点的定义
    • 建立搜索二叉树
    • 接口
      • 插入
      • 搜索
      • 打印
      • 删除
  • 总结

今天本堂主来一起讨论下什么是搜索二叉树，和如何实现二叉搜索树

搜索二叉树

那么二叉搜索树似乎如何实现搜索呢？二叉搜索树和普通二叉树有什么不同呢？

概念

搜索二叉树又可以称作二叉搜索树或二叉排序树。
搜索二叉树需要满足几个条件或者说要具备几个性质：

  • 1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
  • 2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
  • 3.它的左右子树也分别为二叉搜索树
    在这里插入图片描述

二叉搜索树的功能

查找

二叉搜索树的查找：

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

这样在理想情况下时间复杂度是O（logn）,而极端情况如下图时间复杂度还是O（n²）

在这里插入图片描述

实现搜索二叉树

那么如何实现搜索二叉树呢？
在这里插入图片描述
咱们可以按照这个思路去实现

节点的定义

定义节点的时候二叉树包括：本身值，左节点，右节点
那么我们就可以这样来定义节点

template<class K>
struct BSTNode
{
	K _key;
	BSTNode<K>* _left;
	BSTNode<K>* _right;

	BSTNode(const K& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{}
};

这样我们就定义了一个二叉搜索树的节点结构体，构造函数则是用于创建节点并初始化建值，左右指针默认为空

建立搜索二叉树

那么接下来我们就进行声明根节点和初始化根节点为我们后面实现搜索二叉树的功能做铺垫

template<class K>
class BSTree
{
	typedef BSTNode<K> Node;
	\*
	...
	*\
private:
	Node* _root = nullptr;
};

声明根节点：我们声明了一个名为 _root 的指针，该指针指向 Node 类型的对象。这里的 Node 是 BSTNode 的类型别名。

初始化根节点：通过将 _root 初始化为 nullptr，我们是在创建一个空的搜索二叉树，为后面做铺垫。

接口

万事俱备那么我们就来实现搜索二叉树的功能吧

插入

首先一定是向空的搜索二叉树中插入数。

很简单我们先在BSTree的类里面定义一个Insert的函数

//插入
	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 if (parent->_key > key)
		{
			parent->_left = cur;
		}
		return true;
	}
  • 我们先判断_root如果为空那么我们定义一个新新节点连接到根节点，并给新节点赋值
  • 其次如果树不为空，遍历树来找到正确的插入位置（我这里用的双指针防止迷路）
  • 如果找到和键值相同的节点则不插入
  • 符合搜索二叉树的性质加入新节点

搜索

有了插入的铺垫我们搜索的函数在遍历查找树这里就可以CV下

//查找
	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key == key)
			{
				return true;
			}
			else if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else
			{
				cur = cur->_left;
			}
		}
		return false;
	}

不同的是在插入的时候找到和键值相同的值是返回false 而在搜索函数找到键值返回true证明找到了，而没找到值的时候才返回false

打印

那么打印这里就正常写就可以,但是会有一点点小问题
在我正常写打印函数之后，因为_root是私有的只有内部能用所以我用不了

	void InOrder()
	{
		if (root == nullptr)
		{
			return;
		}
		InOrder(root->_left);
		cout << root->_key << " ";
		InOrder(root->_right);
	}

在这里我就进行了些调整

	//打印
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
private:
	//打印的子函数
	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
			{
				//0-1个孩子
				if (cur->_left == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}
					delete cur;
					return true;
				}
				else if (cur->_right == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left == cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
					delete cur;
					return true;
				}
				//两个孩子
				else
				{
					Node* rightMinP = cur;
					Node* rightMin = cur->_right;
					while (rightMin->_left)
					{
						rightMinP = rightMin;
						rightMin = rightMin->_left;
					}

					cur->_key = rightMin->_key;

					if (rightMinP->_left == rightMin)
					{
						rightMinP->_left = rightMin->_right;
					}
					else
					{
						rightMinP->_right = rightMin->_right;
					}
					delete rightMin;
					return true;
				}
			}
		}

		return false;
	}

那么删除这里我在 BSTree 类中定义成员函数 Erase，用于删除搜索二叉树中具有特定键值 key 的节点。

  1. 定义函数：bool Erase(const K& key)，这是一个返回 bool 类型的函数，它接受一个键值 key 作为参数。
  2. 查找要删除的节点：
    • 初始化两个指针 parent 和 cur，分别用于跟踪父节点和当前节点。
    • 进入一个循环，直到找到要删除的节点或者当前节点为 nullptr。
    • 在循环中，通过比较 cur->_key 和 key 来确定是否继续向左或向右遍历。
  3. 删除节点的逻辑：
    • 如果找到要删除的节点，则根据节点是否有子节点或子节点的数量来决定如何删除节点。
    • 如果节点只有一个子节点（要么是左子节点，要么是右子节点），则直接将父节点的相应指针指向该子节点。
    • 如果节点有两个子节点，则需要找到右子树中的最小节点（即右子树的最左下角的节点），将其值复制到当前节点，然后删除右子树中的最小节点。
  4. 释放内存：
    • 在删除节点后，如果节点不再被引用，则释放其内存。
  5. 返回结果：
    • 如果成功删除节点，返回 true。
    • 如果循环结束而没有找到要删除的节点，返回 false。
      这段代码实现了搜索二叉树中键值的删除操作，它通过递归或迭代的方式找到要删除的节点，并确保在删除节点后树仍然保持搜索二叉树的性质。

总结

那么以上就是搜索二叉树的说明和实现，能给我点点赞吗？

完整代码：

#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)
	{}
};

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 if (parent->_key > key)
		{
			parent->_left = cur;
		}
		return true;
	}

	//查找
	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key == key)
			{
				return true;
			}
			else if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else
			{
				cur = cur->_left;
			}
		}
		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
			{
				//0-1个孩子
				if (cur->_left == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}
					delete cur;
					return true;
				}
				else if (cur->_right == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left == cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
					delete cur;
					return true;
				}
				//两个孩子
				else
				{
					//右子树的最大节点作为替代节点
					/*Node* rightMinP = nullptr;
					Node* rightMin = cur->_right;
					while (rightMin->_left)
					{
						rightMinP = rightMin;
						rightMin = rightMin->_left;
					}

					cur->_key = rightMin->_key;

					rightMinP->_left = rightMinP->_right;
					delete rightMin;
					return true;*/
					Node* rightMinP = cur;
					Node* rightMin = cur->_right;
					while (rightMin->_left)
					{
						rightMinP = rightMin;
						rightMin = rightMin->_left;
					}

					cur->_key = rightMin->_key;

					if (rightMinP->_left == rightMin)
					{
						rightMinP->_left = rightMin->_right;
					}
					else
					{
						rightMinP->_right = rightMin->_right;
					}
					delete rightMin;
					return true;
				}
			}
		}

		return false;
	}

	//打印
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
private:
	//打印的子函数
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

private:
	Node* _root = nullptr;
};

封面图
在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Android Media3 技术应用详解

Android Media3 技术应用详解

1、音视频基础 一个简单的音视频链路如下&#xff1a; 1&#xff09;采集&#xff0c;音视频经过采集后分别生成音频流和视频帧&#xff0c;音频是流式的物理上没有帧的概念&#xff0c;但为了数据处理的方便实际数据处理中引入了音频帧的概念&#xff0c;一般中间插入静音数据…
阅读更多...
py-automapper非常详细的详解——看完不会用你打我

py-automapper非常详细的详解——看完不会用你打我

一、py-automapper简介 开发过.Net项目的工程师大部分都用过AutoMapper来进行对象映射&#xff0c;py-automapper就是本第三方包的Python版本。我不太确定Python版本是否覆盖了.Net版本的所有功能&#xff0c;但常用功能都实现了&#xff1a;对象映射、空值处理、属性特殊处理…
阅读更多...
[米联客-安路飞龙DR1-FPSOC] FPGA基础篇连载-15 SPI接收程序设计

[米联客-安路飞龙DR1-FPSOC] FPGA基础篇连载-15 SPI接收程序设计

软件版本&#xff1a;Anlogic -TD5.9.1-DR1_ES1.1 操作系统&#xff1a;WIN10 64bit 硬件平台&#xff1a;适用安路(Anlogic)FPGA 实验平台&#xff1a;米联客-MLK-L1-CZ06-DR1M90G开发板 板卡获取平台&#xff1a;https://milianke.tmall.com/ 登录“米联客”FPGA社区 ht…
阅读更多...
【漏洞复现】WordPress——Recall——SQL注入（CVE-2024-32709）

【漏洞复现】WordPress——Recall——SQL注入（CVE-2024-32709）

声明&#xff1a;本文档或演示材料仅供教育和教学目的使用&#xff0c;任何个人或组织使用本文档中的信息进行非法活动&#xff0c;均与本文档的作者或发布者无关。 文章目录 漏洞描述漏洞复现测试工具 漏洞描述 WordPress是一款免费开源的内容管理系统(CMS)&#xff0c;最初是…
阅读更多...
Java 反射用法和8道练习题

Java 反射用法和8道练习题

目录 一、什么是反射二、反射的核心接口和类三、测试代码 Bean 类和目录结构Person 类代码目录结构 四、获取 Class 对象五、获取构造方法 Constructor 并使用六、获取成员变量 Field 并使用七、获取成员方法 Method 并使用八、练习1. 使用反射获取String类的所有公有方法&…
阅读更多...
虚拟机：VMware功能，安装与使用

虚拟机：VMware功能，安装与使用

目录 一、虚拟机介绍 二、VMware 1.介绍 2.安装 &#xff08;1&#xff09;根据提示按步骤安装​编辑 &#xff08;2&#xff09;更改软件的安装地址​编辑 &#xff08;3&#xff09;根据自己的需求选择是否需要软件更新​编辑 &#xff08;4&#xff09;根据需求选择…
阅读更多...
3. JavaSE ——【逻辑运算符】

3. JavaSE ——【逻辑运算符】

&#x1f680; 开场白 亲爱的读者&#xff0c;大家好&#xff01;我是一名正在学习编程的高校生。在这个博客里&#xff0c;我将和大家一起探讨编程技巧、分享实用工具&#xff0c;并交流学习心得。希望通过我的博客&#xff0c;你能学到有用的知识&#xff0c;提高自己的技能&…
阅读更多...
Billu_b0x靶机

Billu_b0x靶机

信息收集 使用arp-scan 生成网络接口地址来查看ip 输入命令&#xff1a; arp-scan -l 可以查看到我们的目标ip为192.168.187.153 nmap扫描端口开放 输入命令&#xff1a; nmap -min-rate 10000 -p- 192.168.187.153 可以看到开放2个端口 nmap扫描端口信息 输入命令&…
阅读更多...
【深度学习】PyTorch框架(2)：激活函数

【深度学习】PyTorch框架(2)：激活函数

1.引言 在文中&#xff0c;我们将深入探讨流行的激活函数&#xff0c;并分析它们在神经网络优化特性中的作用。激活函数在深度学习模型中扮演着至关重要的角色&#xff0c;因为它们为网络引入了非线性特性。尽管文献中描述了众多的激活函数&#xff0c;但它们并非一视同仁&…
阅读更多...
北京交通大学《深度学习》专业课，实验2-前馈神经网络

北京交通大学《深度学习》专业课，实验2-前馈神经网络

1. 源代码 见资源“北京交通大学《深度学习》专业课&#xff0c;实验2-前馈神经网络” 2. 实验内容 &#xff08;1&#xff09;手动实现前馈神经网络解决上述回归、二分类、多分类任务 分析实验结果并绘制训练集和测试集的loss曲线 &#xff08;2&#xff09;利用to…
阅读更多...
发电机保护屏的工作原理和组成

发电机保护屏的工作原理和组成

发电机保护屏的工作原理和组成 发电机保护屏的工作原理是通过监测发电机的电气参数和运行状态&#xff0c;‌一旦发现异常或故障&#xff0c;‌及时采取相应的保护措施&#xff0c;‌以确保发电机的安全运行。‌ 发电机保护屏通常包含各种传感器、‌保护继电器和控制…
阅读更多...
Golang | Leetcode Golang题解之第231题2的幂

Golang | Leetcode Golang题解之第231题2的幂

题目&#xff1a; 题解&#xff1a; func isPowerOfTwo(n int) bool {const big 1 << 30return n > 0 && big%n 0 }
阅读更多...
整数或小数点后补0操作

整数或小数点后补0操作

效果展示&#xff1a; 整数情况&#xff1a; 小数情况&#xff1a; 小编这里是以微信小程序举例&#xff0c;代码通用可兼容vue等。 1.在utils文件下创建工具util.js文本 util.js页面&#xff1a; // 格式…
阅读更多...
docker desktop历史版本安装

docker desktop历史版本安装

1.安装choco Windows安装 choco包管理工具-CSDN博客 2.通过choco安装 下面例子为安装旧版2.3.0.2,其它版本类似 Chocolatey Software | Docker Desktop 2.3.0.2 https://download.docker.com/win/stable/45183/Docker%20Desktop%20Installer.exe choco install docker-des…
阅读更多...
ESP32-S3多模态交互方案在线AI语音设备应用，启明云端乐鑫代理商

ESP32-S3多模态交互方案在线AI语音设备应用，启明云端乐鑫代理商

随着物联网&#xff08;IoT&#xff09;和人工智能&#xff08;AI&#xff09;技术的飞速发展&#xff0c;嵌入式设备正逐渐变得智能化&#xff0c;让我们的家庭生活变得更加智能化和个性化。 随着大型语言模型的不断进步和优化&#xff0c;AI语音机器人设备能够实现更加智能、…
阅读更多...
绝缘子污秽comsol仿真参数

绝缘子污秽comsol仿真参数

&#x1f3c6;本文收录于《CSDN问答解答》专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收藏&…
阅读更多...
Java+springboot+vue智慧班牌小程序源码，智慧班牌系统可以提供哪些服务？

Java+springboot+vue智慧班牌小程序源码，智慧班牌系统可以提供哪些服务？

智慧班牌全套源码&#xff0c;系统技术架构&#xff1a;Javaspringbootvue element-ui小程序电子班牌&#xff1a;Java Android演示正版授权。 智慧班牌在智慧校园的数字化建设中提供了多种服务&#xff0c;这些服务不仅丰富了校园的信息展示方式&#xff0c;还促进了家校互动…
阅读更多...
渲染100农场有哪些优势？渲染100邀请码1a12

渲染100农场有哪些优势？渲染100邀请码1a12

渲染100是知名的渲染农场&#xff0c;深受广大设计师欢迎&#xff0c;比起其他农场&#xff0c;它有什么优势呢&#xff1f;我们一起来看看。 1、资源丰富 渲染100拥有强大的计算集群&#xff0c;能多线处理大规模、超复杂的场景渲染需要&#xff0c;性能卓越。2、成本低廉 渲…
阅读更多...
文件的顺序读写

文件的顺序读写

文件读写函数介绍 文件顺序读写函数 函数名功能适用于fputc 字符输出函数 所有输出流 fgetc 字符输⼊函数 所有输⼊流 fputs ⽂本⾏输出函数 所有输出流fgets ⽂本⾏输⼊函数 所有输⼊流fprintf 格式化输出函数 所有输出流fscanf 格式化输⼊函数 所有输⼊流fwrite ⼆进制输出…
阅读更多...
Multi-modal Information Fusion for Action Unit Detection in the Wild

Multi-modal Information Fusion for Action Unit Detection in the Wild

标题&#xff1a;多模态信息融合用于野外动作单元检测 源文链接&#xff1a;https://openaccess.thecvf.com/content/CVPR2023W/ABAW/papers/Deng_Multi-Modal_Information_Fusion_for_Action_Unit_Detection_in_the_Wild_CVPRW_2023_paper.pdfhttps://openaccess.thecvf.com/…
阅读更多...
最新文章

Copyright @ 2022~2023