C++进阶--搜索二叉树

概念

搜索二叉树是一种特殊的二叉树，其具有以下特点：

1.对于每个结点，它的左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。
2.左子树和右子树都是搜索二叉树。

这个 特性使得搜索二叉树可以用于高效地进行查找、插入和删除操作。通过利用节点之间的大小关系，我们可以快速定位到目标值所在的位置，避免不必要的比较操作。

在数据结构专栏已经讲解过了二叉树了：

二叉树1
二叉树2

下面直接讲解对搜索二叉树的实现。

实现搜索二叉树

二叉树结点模板

在这里插入图片描述

默认构造

在这里插入图片描述

查找

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

插入

在这里插入图片描述

bool Insert(const K& key)
		{
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}

			cur = new Node(key);
			if (key > parent->_key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}

			return true;
		}

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

删除

bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_right)
							{
								parent->_right = cur->_right;
							}
							else
							{
								parent->_left = cur->_right;
							}
						}
						delete cur;
						return true;
					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}
						delete cur;
						return true;

					}
					else
					{
						Node* rightMinParent = cur;
						Node* rightMin = cur->_right;
						while (rightMin->_left)
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_left;
						}

						cur->_key = rightMin->_key;
						if (rightMin == rightMinParent->_left)
						{
							rightMinParent->_left = rightMin->_right;
						}
						else
						{
							rightMinParent->_right = rightMin->_right;
						}
						delete rightMin;
						return true;
					}
				}
			}
			return false;
		}

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

拷贝、赋值、析构

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

递归版本的增删查

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

删除：

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* rightMin = root->_right;
					while (rightMin->_left)
						rightMin = rightMin->_left;
					swap(root->_key, rightMin->_key);
					return _EraseR(root->_right, key);
				}
				delete del;
				return true;
			}
		}

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

实现源码

#pragma once

namespace fnc
{
	template<class K>
	struct BSTreeNode
	{
		typedef BSTreeNode<K> Node;

		Node* _left;
		Node* _right;
		K _key;

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

	template<class K>
	class BSTree
	{
		typedef BSTreeNode<K> Node;
	public:
		//强制生成默认构造
		BSTree() = default;
		//拷贝构造
		BSTree(const BSTree<K>& t)
		{
			_root = Copy(t._root);
		}
		//赋值
		BSTree<K>& operator=(BSTree<K> t)
		{
			swap(_root, t._root);
			return *this;
		}
		//析构
		~BSTree()
		{
			Destory(_root);
			cout << "Destory()" << endl;
		}
		//查找
		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)
		{
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}

			cur = new Node(key);
			if (key > parent->_key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}

			return true;
		}
		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_right)
							{
								parent->_right = cur->_right;
							}
							else
							{
								parent->_left = cur->_right;
							}
						}
						delete cur;
						return true;
					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}
						delete cur;
						return true;

					}
					else
					{
						Node* rightMinParent = cur;
						Node* rightMin = cur->_right;
						while (rightMin->_left)
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_left;
						}

						cur->_key = rightMin->_key;
						if (rightMin == rightMinParent->_left)
						{
							rightMinParent->_left = rightMin->_right;
						}
						else
						{
							rightMinParent->_right = rightMin->_right;
						}
						delete rightMin;
						return true;
					}
				}
			}
			return false;
		}
		//打印
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}


		

		bool FindR(const K& key)
		{
			return _FindR(_root, key);
		}
		bool InsertR(const K& key)
		{
			return _InsertR(_root, key);
		}
		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}

	private:
		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* rightMin = root->_right;
					while (rightMin->_left)
						rightMin = rightMin->_left;
					swap(root->_key, rightMin->_key);
					return _EraseR(root->_right, key);
				}
				delete del;
				return true;
			}
		}
		bool _InsertR(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				root = new Node(key);
				return true;
			}
			if (key > root->_key)
			{
				return _InsertR(root->_right, key);
			}
			else if (key < root->_key)
			{
				return _InsertR(root->_left, key);
			}
			else
			{
				return false;
			}
		}
		bool _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
			{
				return false;
			}
			if (root->_key < key)
			{
				return _FindR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _FindR(root->_left, key);
			}
			else
			{
				return true;
			}
		
		}

		void Destory(Node* root)
		{
			if (root == nullptr)
				return;

			Destory(root->_left);
			Destory(root->_right);
			delete 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;
		}
		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}
	private:
		Node* _root=nullptr;
	};
}

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

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

相关文章

PyTorch的10个基本张量操作

PyTorch的10个基本张量操作

PyTorch是一个基于python的科学计算包。它的灵活性允许轻松集成新的数据类型和算法&#xff0c;并且框架也是高效和可扩展的&#xff0c;下面我们将介绍一些Pytorch的基本张量操作。 Tensors 张量Tensors是一个向量&#xff0c;矩阵或任何n维数组。这是深度学习的基本数据结构…
阅读更多...
C语言贪吃蛇详解

C语言贪吃蛇详解

个人简介&#xff1a;双非大二学生 个人博客&#xff1a;Monodye 今日鸡汤&#xff1a;人生就像一盒巧克力&#xff0c;你永远不知道下一块是什么味的 C语言基础刷题&#xff1a;牛客网在线编程_语法篇_基础语法 (nowcoder.com) 一.贪吃蛇游戏背景 贪吃蛇是久负盛名的游戏&…
阅读更多...
图解报文网关：一种低代码报文网关的创新设计

图解报文网关：一种低代码报文网关的创新设计

所有的支付系统都对接了很多的外部支付、流出、外汇等各种类型的渠道&#xff0c;这些渠道的接口和报文格式各异。今天和大家一起聊聊如何实现一种简洁高效的低代码报文网关设计&#xff0c;主要包括&#xff1a;报文网关的定位&#xff0c;三种形态&#xff0c;低代码报文网关…
阅读更多...
ClickHouse时区

ClickHouse时区

clickhouse数据库的时间是UTC时间。服务器默认的是上海时间。 sudo vim /etc/clickhouse-server/config.xml clickhouse默认的时区是注释的就是UTC时间 %F 表示日期&#xff0c;格式为 YYYY-MM-DD。%T 表示时间&#xff0c;格式为 HH:MM:SS。 因此&#xff0c;formatDateT…
阅读更多...
uniapp设置不显示顶部返回按钮

uniapp设置不显示顶部返回按钮

一、pages文件中&#xff0c;在相应的页面中设置 "titleNView": {"autoBackButton": false} 二、对应的页面文件设置隐藏元素 document.querySelector(.uni-page-head-hd).style.display none
阅读更多...
leetcode(滑动窗口)3.无重复字符的最长字串（C++详细题解）DAY2

leetcode(滑动窗口)3.无重复字符的最长字串（C++详细题解）DAY2

文章目录 1.题目示例提示 2.解答思路3.实现代码结果 4.总结 1.题目 给定一个字符串 s &#xff0c;请你找出其中不含有重复字符的 最长子串 的长度。 示例 示例 1: 输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”&#xff0c;所以其长度为 3。 示…
阅读更多...
开发大佬为什么都不喜欢关电脑？

开发大佬为什么都不喜欢关电脑？

引言 在平时工作中&#xff0c;咱们程序员这一群体往往展现出一些特有的行为习惯&#xff0c;其中之一便是不喜欢频繁地关闭电脑、拒绝关机、长久待机、特别是苹果的机器。 下面从技术分析与用户行为研究的角度出发&#xff0c;将深入探讨程序员倾向于保持电脑开机状态的原因…
阅读更多...
Git的一些基本操作

Git的一些基本操作

初始git 我们给出下面的一个场景&#xff0c;在大学里&#xff0c;一些老师在我们做完实验之后喜欢让我们交实验报告&#xff0c;假设我们有一个比较追求完美的老师和一个勤奋的学生&#xff0c;这个学生叫做小帅&#xff0c;那天小帅桑勤奋的完成实验报告&#xff0c;在第二天…
阅读更多...
关于函数接口的认识和学习

关于函数接口的认识和学习

1.复习拷贝文件的流程&#xff1a; a.打开文件&#xff1a;fopen b.文件的读写&#xff1a;fgetc/fputc/fgets/fputs c.关闭文件&#xff1a;fclose 注意&#xff1a;全缓存的缓存区大小为4k&#xff0c;所以定义了一个4096字节的char数组。打开两个目标文件和源文件&#xff0…
阅读更多...
大厂设计师亲授：PS 中文设置技巧

大厂设计师亲授：PS 中文设置技巧

Photoshop是Adobe开发的图像处理软件&#xff0c;也是市场上最受欢迎的图像处理软件之一。然而&#xff0c;对于一些不熟悉英语的用户来说&#xff0c;Photoshop的默认语言设置可能会成为使用的障碍。那么&#xff0c;如何将Photoshop设置为中文呢&#xff1f;以下是多个角度的…
阅读更多...
day21 图像标签、链接标签

day21 图像标签、链接标签

文章目录 图像标签链接标签1.文本超链接2.图像超链接3.页面间链接4.锚链接5.功能性链接 图像标签 常见的图像格式 JPGGIFPNGBMP… <img src"path" alt"text" title"text" width"x" height"y"/>src【必填】&#xff…
阅读更多...
前端使用pdf.js进行pdf文件预览的第二种方式：Viewer.html

前端使用pdf.js进行pdf文件预览的第二种方式：Viewer.html

背景 最近需要实现一个PDF文档预览的功能&#xff0c;按理说&#xff0c;如果只是简单的预览&#xff0c;使用<embed>、<object>等就可以实现。 但是&#xff0c;我们的需求要实现搜索&#xff01;而且&#xff0c;文档还都超大&#xff0c;均300页以上。那<e…
阅读更多...
###C语言程序设计-----C语言学习（9）#函数基础

###C语言程序设计-----C语言学习（9）#函数基础

前言&#xff1a;感谢您的关注哦&#xff0c;我会持续更新编程相关知识&#xff0c;愿您在这里有所收获。如果有任何问题&#xff0c;欢迎沟通交流&#xff01;期待与您在学习编程的道路上共同进步。 一. 基础知识的学习 1.函数的定义 函数是一个完成特定工作的独立程序模块&…
阅读更多...
Stable Diffusion 模型下载：国风3 GuoFeng3

Stable Diffusion 模型下载：国风3 GuoFeng3

文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八案例九案例十推荐提示词下载地址模型介绍 欢迎使用GuoFeng3模型 - 这是一个中国华丽古风风格模型，也可以说是一个古风游戏角色模型，具有2.5D的质感。 条目内
阅读更多...
Tauri：相比Electron，还有很长路要走的。

Tauri：相比Electron，还有很长路要走的。

一、Tauri是什么 Tauri是一个开源的框架&#xff0c;用于构建跨平台的桌面应用程序。它允许开发者使用Web技术&#xff08;如HTML、CSS和JavaScript&#xff09;来构建高性能的本地应用程序&#xff0c;同时提供了访问底层操作系统功能的能力。 Tauri的设计目标是提供一种简单…
阅读更多...
js改善轮播图（transform）时内部文本上下闪动问题

js改善轮播图（transform）时内部文本上下闪动问题

前些天绘制轮播图时&#xff0c;发现轮播图中不同span标签内&#xff08;样式不同&#xff09;文字上下跳动。 为了防止眩晕在岗位上&#xff0c;需要对其进行改善&#xff0c;试了很多种方法&#xff0c;最后来总结一下&#xff1a; 我的轮播图template代码片段&#xff1a; …
阅读更多...
DBeaver连接人大金仓数据库

DBeaver连接人大金仓数据库

人大金仓的驱动 1. 打开DBeaver软件&#xff0c;点击“数据库”&#xff0c;选择“驱动管理器” 2. 点击“新建”进行达人大金仓驱动管理器配置。 3、创建驱动-设置&#xff1a;驱动名称、类名、url 驱动名称&#xff1a;人大金仓&#xff1b; 类名&#xff1a;com.kingbas…
阅读更多...
2024美赛数学建模A题思路分析 - 资源可用性和性别比例(2)

2024美赛数学建模A题思路分析 - 资源可用性和性别比例(2)

# 1 赛题 问题A&#xff1a;资源可用性和性别比例 虽然一些动物物种存在于通常的雄性或雌性性别之外&#xff0c;但大多数物种实质上是雄性或雌性。虽然许多物种在出生时的性别比例为1&#xff1a;1&#xff0c;但其他物种的性别比例并不均匀。这被称为适应性性别比例的变化。…
阅读更多...
UE中对象创建方法示例和类的理解

UE中对象创建方法示例和类的理解

对象创建方法示例集 创建Actor示例 //创建一个护甲道具 AProp* armor GetWorld()->SpawnActor<AProp>(pos, rotator); 创建Component示例 UCapsuleComponent* CapsuleComponent CreateDefaultSubobject<UCapsuleComponent>(TEXT("CapsuleComponent&qu…
阅读更多...
C++多线程学习[六]： 多线程之间的同步

C++多线程学习[六]： 多线程之间的同步

一、同步问题 实际开发场景中有很多需要同步的情况&#xff0c;例如&#xff0c;音频和视频的同步输出、或者通讯能够第一时间同步接受处理… 二、多线程同步demo 可以看到cond可以阻塞等待&#xff08;wait&#xff09;可以通知一个线程(notify_one)也可以通知所有的线程&am…
阅读更多...
最新文章

Copyright @ 2022~2023