C++实现二叉搜索树的增删查改（非递归玩法）

文章目录

    • 一、二叉搜索树的概念结构和时间复杂度
    • 二、二叉搜索树的插入
    • 三、二叉搜索树的查找
    • 四、二叉搜索树的删除（最麻烦，情况最多，一一分析）
      • 3.1首先我们按照一般情况下写，不考虑特殊情况下
        • 4.1.1左为空的情况（与右为空的情况差不多）
        • 4.1.2两边都不为空的情况下
      • 4.1其次我们考虑极端情况，如果刚好是整体树的根要删除
    • 五、二叉搜索树的中序遍历
    • 六、二叉搜索树的拷贝构造函数，析构函数，赋值操作
      • 6.1 赋值操作（比较简单）
      • 6.2拷贝构造
      • 6.3析构函数
    • 七、全部源码展现（递归玩法的代码也传进来了，下次讲解）

在这里插入图片描述


先赞后看，养成习惯！！！^ _ ^<3 ❤️ ❤️ ❤️
码字不易，大家的支持就是我坚持下去的动力。点赞后不要忘了关注我哦！
所属专栏:C++进阶
在这里插入图片描述

一、二叉搜索树的概念结构和时间复杂度

二叉搜索树（Binary Search Tree）又称二叉排序树（Binary Sort Tree），是一种特殊类型的二叉树，它所有的根节点大于左子树的节点，小于右子树的节点，对二叉搜索树进行中序遍历，即可得到有序的数列。二叉搜索树的时间复杂度由树的高度决定，其搜索、插入和删除的时间复杂度均为 O(log n)，其中 n 是节点数。在最坏的情况下，仍然会有 O(n)的时间复杂度。
在这里插入图片描述

二、二叉搜索树的插入

首先定义一个命名空间作用域，在域中进行插入操作，构造一个二叉树的节点，对节点进行初始化构造

namespace key
{
	template<class K>
	struct BSTreeNode
	{

		typedef BSTreeNode<K> Node;
		BSTreeNode(const K& key)
			:left(nullptr), 
			right(nullptr),
			_key(key)
		{}
		Node* left;
		Node* right;
		K _key;
	};
	template<class K>
	class BSTree
	{
	public:
	bool Insert(const K& key)
	{
	Node* root = new Node(key);
	if (_root == nullptr)
	{
		_root = root;
		return true;
	}
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_key > root->_key)
		{
			parent = cur;
			cur = cur->left;
		}
		else if (cur->_key < root->_key)
		{
			parent = cur;
			cur = cur->right;
		}
		else
		{
			return false;
		}
	}
	if (parent->_key < root->_key)
		parent->right = root;
	else
		parent->left = root;
	return true;
	}
}

代码图解：
在这里插入图片描述

三、二叉搜索树的查找

查找非常简单按照流程找就行了

typedef BSTreeNode<K> Node;
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;
}

四、二叉搜索树的删除（最麻烦，情况最多，一一分析）

3.1首先我们按照一般情况下写，不考虑特殊情况下

bool Erase(const K& key)
{
	assert(_root);
	Node* parent = nullptr;
	Node* cur = _root;

	while (cur)
	{
		if (cur->_key > key)
		{
			parent = cur;
			cur = cur->left;
		}
		else if (cur->_key < key)
		{
			parent = cur;
			cur = cur->right;
		}
		else
		{
			if (cur->left == nullptr)
			{
					if (parent->left == cur)
					{
						parent->left = cur->right;

					}
					else
					{
						parent->right = cur->right;

					}
					
				
				delete cur;
				return true;
			}
			else if (cur->right == nullptr)
			{
				
					if (parent->left == cur)
					{
						parent->left = cur->left;

					}
					else
					{
						parent->right = cur->left;

					}
				delete cur;
				return true;
			}
			else
			{
				Node* pminleft = cur;
				Node* minleft = cur->right;
				while (minleft->left)
				{
					pminleft = minleft;
					minleft = minleft->left;
				}
				cur->_key = minleft -> _key;
				if (minleft == pminleft->left)
					pminleft->left = minleft->right;
				else
					pminleft->right = minleft->right;
				delete minleft;
				return true;
			}
		}
		
	}
	
	return false;
}

代码图解（解释找到时候的情况）

4.1.1左为空的情况（与右为空的情况差不多）

在这里插入图片描述

4.1.2两边都不为空的情况下

在这里插入图片描述

4.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;
				return true;
			}
			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;
				return true;
}

五、二叉搜索树的中序遍历

这里我们用了一个小技巧，就是通过类里面的函数调用类里面的私有成员

//中序遍历
void _Inorder()
{
	Inorder(_root);
}
private:
	//中序遍历
	void Inorder(Node* root)
	{
		if (root == nullptr)
			return;
		Inorder(root->left);
		cout << root->_key << ' ';
		Inorder(root->right);
	}
	Node* _root = nullptr;

六、二叉搜索树的拷贝构造函数，析构函数，赋值操作

6.1 赋值操作（比较简单）

BSTree<K>& operator=(const BSTree& root)
{
	swap(_root, root->_root);
	return *this;
}

6.2拷贝构造

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;
}

6.3析构函数

~BSTree()
{
	Distroy(_root);
}
void Distroy(Node* root)
{
	if (root == nullptr)
		return;
	Distroy(root->left);
	Distroy(root->right);
	delete root;
}

七、全部源码展现（递归玩法的代码也传进来了，下次讲解）

#pragma once
#include<iostream>
#include<assert.h>
#include<algorithm>
using namespace std;

namespace key
{
	template<class K>
	struct BSTreeNode
	{

		typedef BSTreeNode<K> Node;
		BSTreeNode(const K& key)
			:left(nullptr), 
			right(nullptr),
			_key(key)
		{}
		Node* left;
		Node* right;
		K _key;
	};



	template<class K>
	class BSTree
	{
	public:
	//查
		BSTree() = default;//自动生成默认构造


		~BSTree()
		{
			Distroy(_root);
		}

		BSTree(const BSTree<K>& t)
		{
			_root = Copy(t._root);
		}

		BSTree<K>& operator=(const BSTree& root)
		{
			swap(_root, root->_root);
			return *this;
		}

		typedef BSTreeNode<K> Node;
		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 Insert(const K& key)
		{
			Node* root = new Node(key);
			if (_root == nullptr)
			{
				_root = root;
				return true;
			}
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key > root->_key)
				{
					parent = cur;
					cur = cur->left;
				}
				else if (cur->_key < root->_key)
				{
					parent = cur;
					cur = cur->right;
				}
				else
				{
					return false;
				}
			}
			if (parent->_key < root->_key)
				parent->right = root;
			else
				parent->left = root;
			return true;

		}

		//删
		bool Erase(const K& key)
		{
			assert(_root);
			Node* parent = nullptr;
			Node* cur = _root;

			while (cur)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->right;
				}
				else
				{
					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;
						return true;
					}
					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;
						return true;
					}
					else
					{
						Node* pminleft = cur;
						Node* minleft = cur->right;
						while (minleft->left)
						{
							pminleft = minleft;
							minleft = minleft->left;
						}
						cur->_key = minleft -> _key;
						if (minleft == pminleft->left)
							pminleft->left = minleft->right;
						else
							pminleft->right = minleft->right;
						delete minleft;
						return true;
					}
				}
				
			}
			
			return false;
		}


		/		
		//递归玩法

		//增
		bool _InsertR(const K& key)
		{
			_Insert(_root,key);
		}

		bool _EraseR(const K& key)
		{
			_Erase(_root, key);
		}

		bool _FindR(const K& key)
		{
			_Find(_root,key);
		}

		

		void Distroy(Node* root)
		{
			if (root == nullptr)
				return;
			Distroy(root->left);
			Distroy(root->right);
			delete root;
		}
		
		//中序遍历
		void _Inorder()
		{
			Inorder(_root);
		}
		

		private:
			//中序遍历
			void Inorder(Node* root)
			{
				if (root == nullptr)
					return;
				Inorder(root->left);
				cout << root->_key << ' ';
				Inorder(root->right);
			}

			bool _Insert(Node*& root,const K& key)
			{
				if (root == nullptr)
				{
					Node* newroot = new Node(key);
					root = newroot;
					return true;
				}
				if (root->_key > key)
				{
					_Insert(root->left, key);
				}
				else if (root->_key < key)
				{
					_Insert(root->right, key);
				}
				else
					return false;
			}

			Node& _Find(Node*& root, const K& key)
			{
				if (root == nullptr)
					return nullptr;
				if (root->_key > key)
				{
					_Find(root->left);
				}
				else if (root->_key < key)
				{
					_Find(root->right);
				}
				else
				{
					return 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;
			}

			bool _Erase(Node*& root, const K& key)
			{
				if (root == nullptr)
					return false;
				if (root->_key > key)
				{
					return _Erase(root->left,key);
				}
				else if(root->_key < key)
				{
					return _Erase(root->right ,key);
				}
				else
				{
					Node* minright = root->right;
					while (minright->left)
					minright = minright->left;
					swap(root->_key,minright->_key);

					minright->right = minright->right;
					delete minright;

					return true;
				}
			}

			Node* _root = nullptr;
	};
}

在这里插入图片描述

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

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

相关文章

分享：搭建企微知识库简单易学步骤

分享：搭建企微知识库简单易学步骤

说起企微知识库&#xff0c;可能有些人还不太清楚&#xff0c;为什么现在很懂企业选择搭建企微知识库&#xff1f;其实&#xff0c;企微知识库就是一个装满了企业的各种知识、经验和资料的载体。目的是为了方便员工随时查找和学习、有助于知识的传承和共享、加强团队协作和沟通…
阅读更多...
自然语言处理: 第二十一章大模型基底之llama2

自然语言处理: 第二十一章大模型基底之llama2

文章地址: LLaMA:OpenandEfficient Foundation Language Models 项目地址: meta-llama/llama: Inference code for Llama models (github.com) 前言 在LLaMa1的基础之上有兴趣的可以看看我上一篇博客自然语言处理: 第二十一章大模型基底之llama1。Meta 又继续推出了LLaMa2&a…
阅读更多...
windows安装OpenUSD

windows安装OpenUSD

一、下载OpenUSD git clone https://github.com/PixarAnimationStudios/OpenUSDOpenUSD&#xff0c;原名USD&#xff08;Universal Scene Description&#xff0c;通用场景描述&#xff09;&#xff0c;是由皮克斯动画工作室开发的一种开放数据格式。OpenUSD主要用于在虚拟世界…
阅读更多...
AI论文速读 |【综述】 时序分析基础模型：教程与综述

AI论文速读 |【综述】 时序分析基础模型：教程与综述

论文标题&#xff1a;Foundation Models for Time Series Analysis: A Tutorial and Survey 作者&#xff1a; Yuxuan Liang&#xff08;梁宇轩&#xff09;, Haomin Wen&#xff08;温浩珉&#xff09;, Yuqi Nie&#xff08;PatchTST一作&#xff09;, Yushan Jiang, Ming J…
阅读更多...
机器学习全攻略：概念、流程、分类与行业应用案例集锦

机器学习全攻略：概念、流程、分类与行业应用案例集锦

目录 1.引言 2.从零开始认识机器学习&#xff1a;基本概念与重要术语 3.五步走&#xff1a;掌握机器学习项目执行的完整流程 3.1.问题定义与数据收集 3.2.数据预处理与特征工程 3.3.模型选择与训练 3.4.模型评估与优化 3.5.模型部署与监控 4.深入了解各类机器学习方法…
阅读更多...
计算机网络—TCP协议详解：特性、应用（2）

计算机网络—TCP协议详解：特性、应用（2）

&#x1f3ac;慕斯主页&#xff1a;修仙—别有洞天 ♈️今日夜电波&#xff1a;マリンブルーの庭園—ずっと真夜中でいいのに。 0:34━━━━━━️&#x1f49f;──────── 3:34 &#x1f504; ◀️…
阅读更多...
基于卷积神经网络的苹果等级分类系统（pytorch框架）【python源码+UI界面+前端界面+功能源码详解】

基于卷积神经网络的苹果等级分类系统（pytorch框架）【python源码+UI界面+前端界面+功能源码详解】

功能演示&#xff1a; 苹果等级分类系统&#xff0c;基于vgg16&#xff0c;resnet50卷积神经网络&#xff08;pytorch框架&#xff09;_哔哩哔哩_bilibili &#xff08;一&#xff09;简介 基于卷积神经网络的苹果等级分类系统是在pytorch框架下实现的&#xff0c;系统中有两…
阅读更多...
LangChain-05 RAG Conversational 增强检索会话

LangChain-05 RAG Conversational 增强检索会话

安装依赖 pip install --upgrade --quiet langchain-core langchain-community langchain-openai编写代码 from langchain_core.messages import AIMessage, HumanMessage, get_buffer_string from langchain_core.prompts import format_document from langchain_core.runn…
阅读更多...
腾讯云轻量服务器8核16G服务器价格1668元一年送3个月，18M大带宽

腾讯云轻量服务器8核16G服务器价格1668元一年送3个月，18M大带宽

腾讯云轻量应用服务器8核16G配置租用优惠价格1668元15个月&#xff0c;买一年送3个月&#xff0c;配置为&#xff1a;轻量8核16G18M、270GB SSD盘、3500GB月流量、18M带宽&#xff0c;腾讯云优惠活动 yunfuwuqiba.com/go/txy 活动链接打开如下图&#xff1a; 腾讯云8核16G服务器…
阅读更多...
基于java+SpringBoot+Vue的网上订餐系统设计与实现

基于java+SpringBoot+Vue的网上订餐系统设计与实现

基于javaSpringBootVue的网上订餐系统设计与实现 开发语言: Java 数据库: MySQL技术: Spring Boot JSP工具: IDEA/Eclipse、Navicat、Maven 系统展示 前台展示 菜品浏览与选择&#xff1a;用户可以浏览不同的菜品分类&#xff0c;并选择心仪的菜品。 订单创建与管理&…
阅读更多...
多线程--深入探究多线程的重点,难点以及常考点线程安全问题

多线程--深入探究多线程的重点,难点以及常考点线程安全问题

˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好&#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解&#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如…
阅读更多...
SpringBoot登录校验（四）过滤器Filter

SpringBoot登录校验（四）过滤器Filter

JWT令牌生成后&#xff0c;客户端发的请求头中会带有JWT令牌&#xff0c;服务端需要校验每个请求的令牌&#xff0c;如果在每个controller方法中添加校验模块&#xff0c;则十分复杂且冗余&#xff0c;所以引入统一拦截模块&#xff0c;将请求拦截下来并做校验&#xff0c;这块…
阅读更多...
100道面试必会算法-18-岛屿问题（数量、周长、面积）

100道面试必会算法-18-岛屿问题（数量、周长、面积）

100道面试必会算法-18-岛屿问题&#xff08;数量、周长、面积&#xff09; 题目描述 给你一个由 1&#xff08;陆地&#xff09;和 0&#xff08;水&#xff09;组成的的二维网格&#xff0c;请你计算网格中岛屿的数量。 岛屿总是被水包围&#xff0c;并且每座岛屿只能由水平…
阅读更多...
银行数字化转型导师坚鹏：银行数字化转型给支行带来的8大价值

银行数字化转型导师坚鹏：银行数字化转型给支行带来的8大价值

银行数字化转型给支行带来的8大价值 银行数字化转型对不仅对总行、分行产生了深远影响&#xff0c;给总行、分行带来了新质生产力&#xff0c;对银行支行&#xff08;包括网点&#xff09;也会产生重要价值&#xff0c;银行数字化转型导师坚鹏从以下8个方面进行详细分析&#…
阅读更多...
Linux多进程通信（4）——消息队列从入门到实战！

Linux多进程通信（4）——消息队列从入门到实战！

Linux多进程通信总结——进程间通信看这一篇足够啦&#xff01; 1.基本介绍 1&#xff09;消息队列的本质其实是一个内核提供的链表&#xff0c;内核基于这个链表&#xff0c;实现了一个数据结构&#xff0c;向消息队列中写数据&#xff0c;实际上是向这个数据结构中插入一个…
阅读更多...
keil创建工程 芯源半导体CW32F003E4P7

keil创建工程 芯源半导体CW32F003E4P7

提前下载keil 安装步骤 1、下载CW32F003固件库 芯源半导体官网下载固件库 下载好后右键解压 CW32F003_StandardPeripheralLib_V1.5\IdeSupport\MDK 进入MDK文件夹 双击WHXY.CW32F003_DFP.1.0.4.pack安装固件库 点击next然后finish安装结束 keil创建工程 点击new uVision P…
阅读更多...
【软件工程】详细设计（一）

【软件工程】详细设计（一）

1. 引言 1.1 编写目的 该文档的目的是描述《学生成绩管理系统》项目的详细设计&#xff0c;其主要内容包括&#xff1a; 系统功能简介 系统详细设计简述 各个模块的实现逻辑 最小模块组件的伪代码 本文档的预期的读者是&#xff1a; 开发人员 项目管理人员 测试人员 …
阅读更多...
插入排序---算法

插入排序---算法

1、算法概念 插入排序&#xff1a;它的工作原理是通过构建有序排序&#xff0c;对于未排序数据&#xff0c;在已排序序列中从后向前扫描&#xff0c;找到相应位置插入。 2、算法步骤 将第一待排序序列第一个元素看作一个有序序列&#xff0c;把第二个元素到最后一个元素当成是…
阅读更多...
Exchanger 怎么用J.U.C

Exchanger 怎么用J.U.C

Exchanger简介 Exchanger通常用来解决以下类似场景的问题&#xff0c;如下&#xff1a;两个线程间需要交换数据的问题&#xff0c;在多线程编程中&#xff0c;经常会有这样的场景&#xff1a;两个线程各自持有一些数据&#xff0c;并且需要在某个点上交换这些数据&#xff0c;…
阅读更多...
【项目实战】【Docker】【Git】【Linux】部署V2rayA项目

【项目实战】【Docker】【Git】【Linux】部署V2rayA项目

今天着手了一个全新领域的项目&#xff0c;从完全没有头绪到成功运行&#xff0c;记录一下具体的部署流程 github项目链接V2rayA 一开始拿到以后完全没有抓手&#xff0c;去阅读了一下他的帮助文档 写着能用docker运行&#xff0c;就去下载了一个Docker配置了一下 拉取代码到…
阅读更多...
最新文章

Copyright @ 2022~2023