【C++】B树

概念

在这里插入图片描述

实现

二叉搜索树的插入（非递归）

二叉搜索树的中序遍历

二叉搜索树的查找（非递归）

二叉搜索树的删除（非递归）

二叉搜索树的查找（递归）

拷贝构造函数

赋值运算符重载

三、二叉搜索树的实现完整代码

namespace Key
{
	//结点
	template<class K>
	struct BSTreeNode
	{
		BSTreeNode(const K& val = K())
			:_key(val)
			, _left(nullptr)
			, _right(nullptr)
		{}
		K _key;
		BSTreeNode<K>* _left;
		BSTreeNode<K>* _right;
	};

	//树结构
	//class BinarySearchTree
	template<class K>
	class BSTree
	{
		typedef BSTreeNode<K> Node;
		Node* _root;
	public:
		BSTree()
			:_root(nullptr)
		{}

		//C++11强制编译器生成默认构造
		//BSTree() = default;

		BSTree(const BSTree<K>& x)
		{
			_root = _Copy(x._root);
		}
		BSTree<K> operator=(BSTree<K> x)
		{
			swap(_root, x._root);
			return *this;
		}
		bool Insert(const K& key)
		{
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}
			else
			{
				Node* parent = _root;
				Node* cur = _root;
				while (cur != nullptr)
				{
					if (cur->_key == key)
					{
						return false;
					}
					else if (cur->_key > key)
					{
						parent = cur;
						cur = cur->_left;
					}
					else
					{
						parent = cur;
						cur = cur->_right;
					}
				}
				cur = new Node(key);
				if (parent->_key > key)
				{
					parent->_left = cur;
				}
				else if (parent->_key < key)
				{
					parent->_right = cur;
				}
				return true;
			}
		}
		bool InsertR(const K& key)
		{
			return _InsertR(_root, key);
		}

		void InOrder()//中序遍历
		{
			_InOrder(_root);
			cout << endl;
		}

		//非递归
		//先考虑parent与cur之间的关系
		bool Erase1(const K& key)
		{
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				if (cur->_key > key)//往左子树走
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key)//往右子树走
				{
					parent = cur;
					cur = cur->_right;
				}
				else//找到了
				{
					//目标值为根节点
					if (parent == nullptr)
					{
						if (cur->_left == nullptr)
						{
							_root = cur->_right;
							delete cur;
							return true;
						}
						else if (cur->_right == nullptr)
						{
							_root = cur->_left;
							delete cur;
							return true;
						}
						else
						{
							Node* leftMaxParent = cur;
							Node* leftMax = cur->_left;
							if (leftMax->_right == nullptr)
							{
								leftMax->_right = cur->_right;
								delete cur;
								_root = leftMax;
								return true;
							}
							while (leftMax->_right)
							{
								leftMaxParent = leftMax;
								leftMax = leftMax->_right;
							}
							std::swap(leftMax->_key, cur->_key);
							leftMaxParent->_right = leftMax->_left;
							delete leftMax;
							leftMax = nullptr;
							return true;
						}
					}
					//目标值在父节点的左子树
					if (parent->_left == cur)
					{
						//如果目标值的左子树为空
						if (cur->_left == nullptr)
						{
							parent->_left = cur->_right;
							delete cur;
							return true;
						}
						//如果目标值的右子树为空
						else if (cur->_right == nullptr)
						{
							parent->_left = cur->_left;
							delete cur;
							return true;
						}
						//如果目标值的左右子树都不为空
						else
						{
							Node* leftMaxParent = cur;
							Node* leftMax = cur->_left;
							if (leftMax->_right == nullptr)
							{
								leftMax->_right = cur->_right;
								delete cur;
								parent->_left = leftMax;
								return true;
							}
							while (leftMax->_right)
							{
								leftMaxParent = leftMax;
								leftMax = leftMax->_right;
							}
							std::swap(leftMax->_key, cur->_key);
							leftMaxParent->_right = leftMax->_left;
							delete leftMax;
							leftMax = nullptr;
							return true;
						}
					}
					//目标值在父节点的右子树
					else
					{
						if (cur->_left == nullptr)
						{
							parent->_right = cur->_right;
							delete cur;
							return true;
						}
						else if (cur->_right == nullptr)
						{
							parent->_right = cur->_left;
							delete cur;
							return true;
						}
						else
						{
							Node* leftMaxParent = cur;
							Node* leftMax = cur->_left;
							if (leftMax->_right == nullptr)
							{
								leftMax->_right = cur->_right;
								delete cur;
								parent->_right = leftMax;
								return true;
							}
							while (leftMax->_right)
							{
								leftMaxParent = leftMax;
								leftMax = leftMax->_right;
							}
							swap(leftMax->_key, cur->_key);
							leftMaxParent->_right = leftMax->_left;
							delete leftMax;
							leftMax = nullptr;
							return true;
						}
					}
				}
			}
			return false;
		}
		//先考虑cur与其孩子之间的关系
		bool Erase2(const K& key)
		{
			Node* cur = _root;
			Node* parent = nullptr;
			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 == nullptr)
						{
							_root = cur->_right;
						}
						else if (parent->_left == cur)
						{
							parent->_left = cur->_right;
						}
						else if (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
					}
					else if (cur->_right == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_left;
						}
						else if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else if (parent->_right = cur)
						{
							parent->_right = cur->_left;
						}
					}
					else
					{
						Node* leftMax = cur->_left;
						Node* leftMaxParent = cur;
						while (leftMax->_right)
						{
							leftMaxParent = leftMax;
							leftMax = leftMax->_right;
						}
						std::swap(cur->_key, leftMax->_key);
						if (leftMaxParent->_left == leftMax)
						{
							leftMaxParent->_left = leftMax->_left;
						}
						else
						{
							leftMaxParent->_right = leftMax->_left;
						}

						cur = leftMax;
					}
					delete cur;
					return true;
				}
			}
			return false;
		}

		//递归
		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}

		//非递归
		bool Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key == key)
				{
					return true;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					cur = cur->_right;
				}
			}
			return false;
		}
		//递归
		bool FindR(const K& key)
		{
			return _FindR(_root, key);
		}
		~BSTree()
		{
			_Destory(_root);
		}
	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}
		bool _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
				return false;

			if (key < root->_key)
				return _FindR(root->_left, key);
			else if (key > root->_key)
				return _FindR(root->_right, key);
			else
				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->_left, key);
			}
			else if (key > root->_key)
			{
				return _InsertR(root->_right, key);
			}
			else
				return false;
		}
		bool _EraseR(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				return false;
			}

			if (root->_key > key)
			{
				return _EraseR(root->_left, key);
			}
			else if (root->_key < key)
			{
				return _EraseR(root->_right, key);
			}
			else//找到了
			{
				Node* del = root;
				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else//左右子树均不为空
				{
					//找右树最左节点
					Node* min = root->_right;
					while (min->_left)
					{
						min = min->_left;
					}
					swap(root->_key, min->_key);
					return _EraseR(root->_right, key);
				}
				delete del;
				return true;
			}
		}
		void _Destory(Node*& root)
		{
			if (root == nullptr)
			{
				return;
			}
			_Destory(root->_left);
			_Destory(root->_right);
			delete root;
			root = nullptr;
		}
		Node* _Copy(Node* root)
		{
			if (root == nullptr)
			{
				return nullptr;
			}
			Node* copy = new Node(root->_key);
			copy->_left = _Copy(root->_left);
			copy->_right = _Copy(root->_right);
			return copy;
		}
	};
	void test1()
	{
		BSTree<int>root;
		int arr[] = { 1,5,4,8,15,-1,4,3,7,89,5,6,8,14,97,45,9 };
		for (auto it : arr)
		{
			root.Insert(it);
		}

		root.InOrder();

		root.Erase2(8);
		root.InOrder();

		BSTree<int>root1;
		root1.Insert(0);
		root1.Erase2(0);
		root1.InOrder();

		for (auto it : arr)
		{
			root.EraseR(it);
			root.InOrder();
		}
	}

	void test2()
	{
		BSTree<int>root;
		int arr[] = { 1,5,4,8,15,-1,4,3,7,89,5,6,8,14,97,45,9 };
		for (auto it : arr)
		{
			root.Insert(it);
		}
		BSTree<int>root1 = root;
		root1.InOrder();

		BSTree<int>root2;
		root2 = root;
		root2.InOrder();
	}
}

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

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

相关文章

三星系统因何而成？或许是因为吞噬了第四颗恒星

三星系统因何而成？或许是因为吞噬了第四颗恒星

相比于其他的类似星体&#xff0c;这个特殊的三星系统拥有更大更紧密的星体。 三星 天文学家发现了前所未见的三星系统。相比于其他典型的三星系统&#xff0c;这一三星系统拥有更大的体积&#xff0c;并且排列也更加紧密&#xff0c;这也使得这一系统更加特别。科学家推测&am…
阅读更多...
好用的Web数据库管理工具推荐（ChatGPT 4o的推荐是什么样？）

好用的Web数据库管理工具推荐（ChatGPT 4o的推荐是什么样？）

在现代数据管理和开发中&#xff0c;Web数据库管理工具变得越来越重要。这些工具不仅提供了直观的用户界面&#xff0c;还支持跨平台操作&#xff0c;方便用户在任何地方进行数据库管理。 目录 1. SQLynx 2. phpMyAdmin 3. Adminer 4. DBeaver 5 结论 以下是几款推荐的Web…
阅读更多...
操作系统安全：Windows系统安全配置，Windows安全基线检查加固

操作系统安全：Windows系统安全配置，Windows安全基线检查加固

「作者简介」&#xff1a;2022年北京冬奥会网络安全中国代表队&#xff0c;CSDN Top100&#xff0c;就职奇安信多年&#xff0c;以实战工作为基础对安全知识体系进行总结与归纳&#xff0c;著作适用于快速入门的 《网络安全自学教程》&#xff0c;内容涵盖系统安全、信息收集等…
阅读更多...
数据结构与算法笔记：基础篇 - 红黑树（上）：为什么工程中都用红黑树这种二叉树？

数据结构与算法笔记：基础篇 - 红黑树（上）：为什么工程中都用红黑树这种二叉树？

概述 上两篇文章&#xff0c;我们依次讲解了树、二叉树、二叉查找树。二叉查找树是最常用的一种二叉树&#xff0c;它支持快速插入、删除、查找操作&#xff0c;各个操作的时间复杂度跟树的高度成正比&#xff0c;理想情况下&#xff0c;时间复杂度是 O ( l o g n ) O(logn) …
阅读更多...
如何用R语言ggplot2画折线图

如何用R语言ggplot2画折线图

文章目录 前言一、数据集二、ggplot2画图1、全部代码2、细节拆分1&#xff09;导包2&#xff09;创建图形对象3&#xff09;主题设置4&#xff09;轴设置5&#xff09;图例设置6&#xff09;颜色7&#xff09;保存图片 前言 一、数据集 数据下载链接见文章顶部 数据&#xff1a…
阅读更多...
网络数据包抓取与分析工具wireshark的安及使用

网络数据包抓取与分析工具wireshark的安及使用

WireShark安装和使用 WireShark是非常流行的网络封包分析工具&#xff0c;可以截取各种网络数据包&#xff0c;并显示数据包详细信息。常用于开发测试过程中各种问题定位。 1 任务目标 1.1 知识目标 了解WireShark的过滤器使用,通过过滤器可以筛选出想要分析的内容 掌握Wir…
阅读更多...
企业微信hook接口协议,ipad协议http,确认群发消息

企业微信hook接口协议,ipad协议http,确认群发消息

确认群发消息 参数名必选类型说明uuid是String每个实例的唯一标识&#xff0c;根据uuid操作具体企业微信 请求示例 {"uuid": "d85c7605-ae91-41db-aad5-888762493bac","vids":[],//如果是客户群群发需要填群id"msgid":1097787129…
阅读更多...
前端三剑客之JavaScript基础入门

前端三剑客之JavaScript基础入门

目录 ▐ 快速认识JavaScript ▐ 基本语法 &#x1f511;JS脚本写在哪? &#x1f511;注释 &#x1f511;变量如何声明? &#x1f511;数据类型 &#x1f511;运算符 &#x1f511;流程控制 ▐ 函数 ▐ 事件 ▐ 计时 ▐ HTML_DOM对象 * 建议学习完HTML和CSS后再…
阅读更多...
手把手带你做一个自己的网络调试助手(4) - 优化完善

手把手带你做一个自己的网络调试助手(4) - 优化完善

了解全部信息&#xff0c;请关注专栏: QT网络调试助手_mx_jun的博客-CSDN博客 优化服务器 1.不能设置随拖动变大: this->setLayout(ui->verticalLayout); 2. 未连接就能发送消息: //在处理新连接槽函数中加入 if(!ui->btnSend->isEnabled()){//只有客户端连接…
阅读更多...
【CC精品教程】osbg格式三维实景模型全解

【CC精品教程】osbg格式三维实景模型全解

数据格式同样都是osgb，不同软件生产的，建模是参数不一样，还是有很大区别的，本讲进行一一讲解。 文章目录 一、CC生产的osbg1. osgb的文件结构2. metadata.xml是什么？​（1）EPSG模式metadata.xml​（2）EPSG带+模式metadata.xml​（3）ENU模式metadata.xml​（4）LOCAl模式…
阅读更多...
《大道平渊》· 拾贰 —— 天下大事必作于细：做好每一件小事，必然大有所成！

《大道平渊》· 拾贰 —— 天下大事必作于细：做好每一件小事，必然大有所成！

《平渊》 拾贰 "天下难事必作于易&#xff0c;天下大事必作于细。" 社群一位大佬最近在研究新项目, 他做事的 "方法论" 令我深受启发。 他在测试项目时, 每一步都做的非常细致&#xff1a; 整个项目的测试都被划分为一件件小事, 然后有条不紊地推进…… …
阅读更多...
postgresql之翻页优化

postgresql之翻页优化

列表和翻页是所有应用系统里面必不可少的需求&#xff0c;但是当深度翻页的时候&#xff0c;越深越慢。下面是几种常用方式 准备工作 CREATE UNLOGGED TABLE data (id bigint GENERATED ALWAYS AS IDENTITY,value double precision NOT NULL,created timestamp with time zon…
阅读更多...
matlab 异常值检测与处理——Z-score法

matlab 异常值检测与处理——Z-score法

目录 一、算法原理1、算法概述2、主要函数3、参考文献二、代码实现三、结果展示四、相关链接本文由CSDN点云侠原创，原文链接。如果你不是在点云侠的博客中看到该文章，那么此处便是不要脸的爬虫。 一、算法原理 1、算法概述 使用Z分数法，可以找出距离平均值有多少个标准差值…
阅读更多...
Java面试八股之静态变量和实例变量的区别有哪些

Java面试八股之静态变量和实例变量的区别有哪些

Java静态变量和实例变量的区别有哪些 存储位置和生命周期&#xff1a; 静态变量&#xff1a;静态变量属于类级别&#xff0c;存储在Java的方法区&#xff08;或称为类区&#xff0c;随JVM实现而异&#xff0c;现代JVM中通常在元数据区内&#xff09;&#xff0c;并且在类首次…
阅读更多...
天锐绿盾，怎么防止公司内部核心文件、文档、设计图纸、源代码、音视频等数据资料外泄

天锐绿盾，怎么防止公司内部核心文件、文档、设计图纸、源代码、音视频等数据资料外泄

天锐绿盾通过多种技术和管理手段&#xff0c;全面保护公司内部的核心文件、文档、设计图纸、源代码、音视频等数据资料&#xff0c;防止外泄。以下是具体的防泄密措施&#xff1a; PC地址&#xff1a; https://isite.baidu.com/site/wjz012xr/2eae091d-1b97-4276-90bc-6757c5d…
阅读更多...
【技术干货】Linux命令“du-sh和df”执行结果存在差异，问题分析及处理过程

【技术干货】Linux命令“du-sh和df”执行结果存在差异，问题分析及处理过程

1.du-sh和df的差异 du和df是两个不同的Linux命令&#xff0c;它们⽤于查看磁盘空间的使⽤情况。但是它们有⼀些区别&#xff1a; • du&#xff08;diskusage&#xff09;会扫描每个⽂件和⽬录&#xff0c;并计算它们的总⼤⼩。[1]du-sh*会显⽰当前⽬录下每个⽂件或⽬录的⼤⼩…
阅读更多...
APD系列特高频局放监测装置

APD系列特高频局放监测装置

安科瑞电气股份有限公司 祁洁 15000363176 一、产品概述 现阶段&#xff0c;电力系统对于电能的质量提出越来越高的要求&#xff0c;不仅要确保供电稳定可靠&#xff0c;而且供电的安全性也是重要要求。电力系统中&#xff0c;金属封闭开关设备得到广泛应用&#xff0c;因…
阅读更多...
基于springboot实现影院订票系统项目【项目源码+论文说明】

基于springboot实现影院订票系统项目【项目源码+论文说明】

基于springboot实现影院订票系统演示 摘要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本影院订票系统就是在这样的大环境下诞生&#xff0c;其可以帮助管理者在…
阅读更多...
安卓手机电脑同步数据，2个方法，有效避免数据膨胀

安卓手机电脑同步数据，2个方法，有效避免数据膨胀

如今&#xff0c;我们的手机已经成为了数字生活的中心舞台&#xff0c;而电脑则是我们工作和娱乐的得力助手。两者之间的数据同步&#xff0c;就像是搭建了一座无形的桥梁&#xff0c;让我们的生活和工作变得更加便捷和高效。如何高效进行手机电脑同步数据呢&#xff1f;在这篇…
阅读更多...
第十三章 组合模式

第十三章 组合模式

目录 1 组合模式介绍 2 组合模式原理 3 组合模式实现 4 组合模式应用实例 5 组合模式总结 1 组合模式介绍 组合模式(Composite Pattern) 的定义是&#xff1a;将对象组合成树形结构以表示整个部分的层次结构.组合模式可以让用户统一对待单个对象和对象的组合. 2 组合模式…
阅读更多...
最新文章

Copyright @ 2022~2023