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

       前言：二叉搜索树是一种常用的数据结构，支持快速的查找、插入、删除操作，C++中map和set的特性也是以二叉搜索树作为铺垫来实现的，而二叉搜索树也是一种树形结构，所以，在学习map和set之前，我们先来学习这种新的树形结构--二叉搜索树。

目录

1.二叉搜索树

二叉搜索树的功能及其实现

二叉搜索树的插入和查找

二叉搜索树的删除

查找函数递归实现

插入函数递归实现

删除函数递归实现

拷贝构造和赋值运算符重载

搜索二叉树的相关性质及其应用

二叉搜索树的查找

key-value模型

1.二叉搜索树

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

     若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

     若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

     它的左右子树也分别为二叉搜索树，同样的，我们可以发现，二叉搜索树的中序遍历是升序排序的

二叉搜索树的功能及其实现

        我们先定义基础的节点的数据结构，明显是一个二叉树类型的节点，有左右节点，运用模板知识，我们可以描述出以下的节点结构体和搜索树的类的描述：

template<class T>
struct BSTreeNdoe {
	BSTreeNdoe(const T& data = T())
		: _left(nullptr), _right(nullptr), data(data)
	{}
	BSTreeNdoe<T>* _left;
	BSTreeNdoe<T>* _right;
	T data;

};
template<class T>
class BSTree {

	typedef BSTreeNdoe<T> Node;
public:
     //成员函数

private:
	Node* root = nullptr;

};

下面的功能函数将从上面给出的结构来进行扩充功能和优化改写：

二叉搜索树的插入和查找

插入的具体过程如下：

a. 树为空，则直接新增节点，赋值给root指针

b. 树不空，按二叉搜索树性质查找插入位置，插入新节点，从树的根节点依次寻找：如果待插入的值比当前节点大，那直接插入当前节点的右边，反之，插入当前节点的左边，这里注意，一般的，在二叉搜索树中不会存在相同的值，需要注意的是，为了保证新节点能够和树连接起来，需要记录好父节点。

//插入操作
	bool insert(const T& key)
	{
		if (root == nullptr)//如果当前树为空，那么直接建树
		{
			root = new Node(key);
			return true;
		}
		//如果不为空，直接寻找合适的位置插入即可
		Node* cur = root;
		Node* parent = nullptr;//记录父亲节点用来连接
		while (cur)
		{
			parent = cur;
			if (cur->data > key)//比当前节点小，往当前节点左边走
				cur = cur->_left;
			else if (cur->data < key)//比当前节点大，往当前节点右边走
				cur = cur->_right;
			//一般来说，搜索二叉树不会存在相同的两个值
			else
				return false;
		}
		cur = new Node(key);
		if (parent->data > key)
			parent->_left = cur;
		else if (parent->data < key)
			parent->_right = cur;
		return true;
	}

二叉搜索树的查找

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

b、最多查找高度次，走到到空，还没找到，这个值不存在。

bool find(const T& key)
	{
		Node* cur = root;
		while (cur)
		{
			if (cur->data > key)
				cur = cur->_left;
			else if (cur->data < key)
				cur = cur->_right;
			else
				return true;
		}
		return false;
	}

二叉搜索树的删除

        首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：

a. 要删除的结点无孩子结点

b. 要删除的结点只有左孩子结点

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左、右孩子结点

       实际上，这四种情况中，a情况可以算作b或者c情况中，因为删除叶子结点，本质上可以看做要删除的节点只有为nullptr的右孩子或者左孩子节点，我们来分别对这三种情况进行分析，

       对于替换法，我们需要注意特殊的情况，从上面的图可以看出，左子树中的最右节点，本质上就是第一次往待删除节点的左孩子节点走，之后的每一步，都开始往其右孩子方向走，右子树的最左节点是第一次往待删除节点的右孩子节点走，之后一直往其左孩子方向走，此时，我们的替换法是建立在待删除节点的左右孩子都存在的前提下，所以，左树最右节点和右树最左节点，左树和右树一定都具备，但是不一定有最右和最左节点，下面我们就以左树最右节点为例，来进行讨论分析：

下面是一颗普通的二叉树：

        因为此时待删除节点需要满足存在左右节点，所以，此时符合要求的节点只有8,3，其中8是正常的情况，因为其左子树有右孩子，通过8到3之后可以直接找到7，所以8可以直接和7进行交换，因为此时已经遍历到了左子树的最右节点，也就是说，该节点不可能再存在右孩子，但是不能保证没有左孩子，比如说没有7这个节点，要删除8,8就只能和6交换，此时我们需要将4，也就是被交换节点的左子树放在3的右孩子上，这样就能达到删除8的目的；

     此时我们再来看3这个节点，这个节点特殊在其只有一个左孩子节点，并且左孩子节点没有了右子树，导致我们找左树最右节点的时候，只能找到第一步左树的位置而被迫停下来，此时，这个左树就只能当做左树的最右节点来看待，只是此时我们在将1和3交换之后，操作上要发生变化，因为此时没有了右子树，所以被交换后，3成了左子树，也就是说需要删除的是1的左子树而不是像上面的情况一样直接将被交换节点的父节点的右树直接被删除节点的左树。

这里我们给出代码和测试二叉树，方便我们下来模拟运行和理解：

//删除节点
	bool Erase(const T& key)
	{
		Node* parent = nullptr;
		Node* cur = root;
		while (cur)
		{
			if (cur->data < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->data > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				//找到了，开始删除
				//只有右孩子
				if (cur->_left == nullptr)
				{
					//此时父节点有三种情况

					//如果要删除的是根节点,需要特殊处理
					if (cur == root)
						root =cur->_right;
					else if (cur == parent->_left)
						parent->_left = cur->_right;
					else if (cur == parent->_right)
						parent->_right = cur->_right;
					delete cur;
				}
				//只有左孩子
				else if (cur->_right == nullptr)
				{
					//此时父节点有三种情况

					//如果要删除的是根节点
					if (cur == root)
						root = cur->_left;
					else if (cur == parent->_left)
						parent->_left = cur->_left;
					else if (cur == parent->_right)
						parent->_right = cur->_left;
					delete cur;
				}
				//有左右两个孩子节点
				else
				{
					//法1：假设默认选择左子树的最大节点
					//Node* pright = cur->_left;//先找到左子树，此时我们能确保待删除节点是有两个孩子的,所以p一定不为空
					//Node* pp = cur;//初始时父节点等于待删除节点
					//while (pright->_right)
					//{
					//	pp = pright;//更新父节点
					//	pright = pright->_right;
					//}
					//std::swap(cur->data, pright->data);

					//
					//if (pright == pp->_left)//左子树不存在右孩子，直接将p->_left赋值pp的左孩子即可
					//	pp->_left = pright->_left;
					//else  //左子树存在右孩子
					//	pp->_right = pright->_left; //直接将交换后的节点的左子树放到待删除节点的父节点的右子树上
					//delete pright;

					//法2：假设选择右子树的最小节点
					Node* pleft = cur->_right;//选择右子树,但是最终目的是寻找右子树的最左节点
					Node* pp = cur;
					while (pleft->_left)
					{
						pp = pleft;
						pleft = pleft->_left;
					}
					std::swap(cur->data, pleft->data);

					if (pleft == pp->_right)//如果待删除节点的右子树没有左孩子
						pp->_right = pleft->_right;
					else //如果是正常情况
						pp->_left = pleft->_right;//最左节点的右孩子需要保留在pp的左子树
					delete pleft;
				}
				return true;
			}
		}
		return false;
	}

查找函数递归实现

protected:
	bool findr(Node* root,const T&key)
	{
		if (root == nullptr)
			return false;
		else if (root->data > key)
			return finr(root->_left, key);
		else if (root->data < key)
			return finr(root->_right, key);
		else
			return true;
	}
public:
	bool FindR(const T&key)
	{
		return findr(root,key);
	}

插入函数递归实现

protected:
	bool insertr(Node* &root, const T& key)//由于要修改原树，所以建议传引用
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		if (root->data > key)
			return insertr(root->_left, key);
		else if (root->data < key)
			return insertr(root->_right, key);
		else
			return false;
	}
public:
	bool InsertR(const T& key)
	{
		return insertr(root, key);
	}

删除函数递归实现

//节点的删除递归实现
protected:
	bool eraser(Node* &root, const T& key)
	{
		if (root == nullptr)
			return false;

		if (root->data < key)
		{
			return eraser(root->_right, key);
		}
		else if (root->data > key)
		{
			return eraser(root->_left, key);
		}
		else
		{
			// 删除
			if (root->_left == nullptr)
			{
				Node* del = root;
				root = root->_right;
				delete del;

				return true;

			}
			else if (root->_right == nullptr)
			{
				Node* del = root;
				root = root->_left;
				delete del;

				return true;
			}
			else
			{
				//以删除右子树的最小节点为例
				Node* pleft = root->_right;
				while (pleft->_left)
				{
					pleft = pleft->_left;
				}

				std::swap(root->data, pleft->data);

				// 转换成在子树递归删除
				return eraser(root->_right, key);
			}
		}
	}
public:
	bool EraseR(const T& key)
	{
		return eraser(root, key);
	}

拷贝构造和赋值运算符重载

	//拷贝构造函数
protected:
	Node* copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* newroot = new Node(root->data);
		newroot->_left = copy(root->_left);
		newroot->_right = copy(root->_right);

		return newroot;
	}
public:
	BSTree(const BSTree<T>& b)
	{
		root = copy(b.root);
	}
	BSTree(){}//构造函数
	//赋值运算符重载
	BSTree<T>& operator=(BSTree<T>& b)
	{
		std::swap(root, b.root);
		return *this;
	}

搜索二叉树的相关性质及其应用

二叉搜索树的查找

       我们不难发现，搜索二叉树的中序遍历是对应的升序排列，当我们在二叉搜索树中查找某个值的时候，我们却不能简单的认为其查找效率是logn级别的，因为查找效率需要考虑最坏的情况，而我们的logn的效率实际上是理想化的情况，比某个数大和比某个数小的数各占一半，分别在这个数的左右两侧子树上，才有logn级别的效率，但是，若是在最坏的情况下，搜索树变成了类似于单链表式的链状结构，则查找效率就会变成 o(n) 级别的，因此，我们需要对二叉搜索树进行优化才能符合我们的要求，就叫做所谓的平衡搜索二叉树（AVL树，红黑树等），具体我们后面再做讲解。

key-value模型

        实际上，在C++中，key-value模型的例子有很多，比如map，pair等数据结构，它们通常是一个键值，一个值的方式组成，其中，键值作为功能函数的主要参数，相当于数组的下标，有了下标，我们就可以按下标访问任何一个存在的元素，相当于查找等操作，现在，我们想在二叉搜索树中实现key-value模型，此时，我们只需要将本来一个节点存储的一个数据，修改为一个节点可以存储两个数据即可，具体细节见下面的实现：

namespace key_value{

	template<class K, class V>
	struct BSTreeNode
	{
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
		K _key;
		V _value;

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

	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:
		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				parent = cur;

				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}

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

			return true;
		}

		Node* 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 cur;
				}
			}

			return nullptr;
		}

		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
				{
					// 准备删除  
					if (cur->_left == nullptr)
					{//左为空
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}
					}
					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;
							}
						}
					}
					else
					{//左右都不为空

						// 右树的最小节点(最左节点)
						Node* parent = cur;
						Node* subLeft = cur->_right;
						while (subLeft->_left)
						{
							parent = subLeft;
							subLeft = subLeft->_left;
						}

						swap(cur->_key, subLeft->_key);

						if (subLeft == parent->_left)
							parent->_left = subLeft->_right;
						else
							parent->_right = subLeft->_right;
					}

					return true;
				}
			}

			return false;
		}
		void InOrder()
		{
			_InOrder(_root);
			std::cout << std::endl;
		}
	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;

			_InOrder(root->_left);
			std::cout << root->_key << ":" << root->_value << std::endl;
			_InOrder(root->_right);
		}
	private:
		Node* _root = nullptr;
	};
}

       以上就是二叉搜索树的初阶内容了，我们后续在学习map和set时还会使用二叉搜索树来实现，具体我们后面再来分析，下一篇，我们将讲解一些二叉树的相关例题，敬请期待~

       要做一个情绪稳定的成年人，。烦躁的时候千万不要讲话，也不要做任何决定，就安静的待一会。当你内心足够坚定的时候，谁都没有办法影响你的情绪。经历的越多，反而明白的更多，把期待降低，把依赖变少，努力把生活变成自己想要的样子。

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

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

相关文章

鸿运主动安全云平台任意文件下载漏洞复习

鸿运主动安全云平台任意文件下载漏洞复习

简介 深圳市强鸿电子有限公司鸿运主动安全监控云平台网页存在任意文件下载漏洞&#xff0c;攻击者可通过此漏洞下载网站配置文件等获得登录账号密码 漏洞复现 FOFA语法&#xff1a;body"./open/webApi.html" 获取网站数据库配置文件 POC&#xff1a;/808gps/Mobile…
阅读更多...
Android Studio中配置Git

Android Studio中配置Git

安装Git 在安装Android Studio之前&#xff0c;需要先安装Git。可以从Git官网下载并安装Git&#xff1a;https://git-scm.com/downloads 在Android Studio中配置Git 在Android Studio中&#xff0c;依次点击“File” -> “Settings”&#xff0c;在弹出的窗口中选择“Ver…
阅读更多...
vue学习part01

vue学习part01

02_Vue简介_哔哩哔哩_bilibili Vue.js - 渐进式 JavaScript 框架 | Vue.js (vuejs.org) 1.简介 2.常用用法 新项目一般vue3&#xff0c;老项目vue2 3.vue两种风格&#xff1a;选项式api&#xff08;vue2&#xff09;和组合式api&#xff08;vue3&#xff09; 两种方式实现累…
阅读更多...
财务数字化转型的切入点是什么？_光点科技

财务数字化转型的切入点是什么？_光点科技

随着科技的不断进步&#xff0c;数字化转型已经成为各个行业追求的目标&#xff0c;财务领域也不例外。那么&#xff0c;财务数字化转型的切入点在哪里呢&#xff1f;如何确保转型的成功进行&#xff1f; 数据整合与管理 财务数据的准确性与及时性是财务管理的基石。数字化转型…
阅读更多...
桥和割点，以及图的遍历树

桥和割点，以及图的遍历树

目录 什么是桥 寻找桥的算法 代码实现 什么是割点 ​寻找割点的算法 代码实现 什么是桥 寻找桥的算法 代码实现 import java.util.ArrayList;public class FindBridges {private Graph G;private boolean[] visited;private int ord[];private int low[];private int cnt…
阅读更多...
在基于亚马逊云科技的湖仓一体架构上构建数据血缘的探索和实践

在基于亚马逊云科技的湖仓一体架构上构建数据血缘的探索和实践

背景介绍 随着大数据技术的进步&#xff0c;企业和组织越来越依赖数据驱动的决策。数据的质量、来源及其流动性因此显得非常关键。数据血缘分析为我们提供了一种追踪数据从起点到终点的方法&#xff0c;有助于理解数据如何被转换和消费&#xff0c;同时对数据治理和合规性起到关…
阅读更多...
阿里云的OSS云存储的基本使用

阿里云的OSS云存储的基本使用

阿里云官网&#xff1a;阿里云-计算&#xff0c;为了无法计算的价值 通过阿里云官网&#xff0c;登录进入用户的界面&#xff0c;在搜索框中输入OSS&#xff0c;然后进入阿里云的对象存储OSS的控制台。&#xff08;未开通的开通即可&#xff09; 创建 Bucket 点击【Bucket 列…
阅读更多...
OpenShift - 利用容器的特权配置实现对OpenShift攻击

OpenShift - 利用容器的特权配置实现对OpenShift攻击

《OpenShift / RHEL / DevSecOps 汇总目录》 说明&#xff1a;本文已经在 OpenShift 4.13 的环境中验证 本文是《容器安全 - 利用容器的特权配置实现对Kubernetes攻击》的后续篇&#xff0c;来介绍 在 OpenShift 环境中的容器特权配置和攻击过程和 Kubernetes 环境的差异。 文…
阅读更多...
JVM——类的生命周期（加载阶段，连接阶段，初始化阶段）

JVM——类的生命周期（加载阶段，连接阶段，初始化阶段）

目录 1.加载阶段2.连接阶段1.验证2.准备3.解析 3.初始化阶段4.总结 类的生命周期 1.加载阶段 ⚫ 1、加载(Loading)阶段第一步是类加载器根据类的全限定名通过不同的渠道以二进制流的方式获取字节码信息。 程序员可以使用Java代码拓展的不同的渠道。 ⚫ 2、类加载器在加载完类…
阅读更多...
一个ppt带你读懂网络安全行业四大顶会之一的ndss论文＜＜Large Language Model guided Protocol Fuzzing＞＞

一个ppt带你读懂网络安全行业四大顶会之一的ndss论文＜＜Large Language Model guided Protocol Fuzzing＞＞

论文下载地址&#xff1a; Large Language Model guided Protocol Fuzzing
阅读更多...
14.Eclipse全局查找字符，类，方法快捷键

14.Eclipse全局查找字符，类，方法快捷键

eclipse开发中&#xff0c;查找会是一个经常用到的功能所以总结一下 1&#xff0c;查找一个类 Shift Ctrl h 或者 Shift Ctrl r 这种方式能快速的定位接口&#xff0c;类还有注解在那个包里面 2.综合查找 Ctrl H 这是一种综合查找 &#xff0c;可以用来查找 一个方法的…
阅读更多...
selenium爬虫——以爬取澎湃新闻某搜索结果为例

selenium爬虫——以爬取澎湃新闻某搜索结果为例

文章目录 selenium爬虫——以爬取澎湃新闻某搜索结果为例前言需要导入的包需要避雷的点webdriver的版本要与浏览器一致如果使用爬虫打开了新网页&#xff0c;要记得跳转XPath和selector都可以直接复制爬取多网页时记得try打入word时调整字体的问题 完整程序扩展爬取效果 seleni…
阅读更多...
【蓝桥杯】2023省赛H题

【蓝桥杯】2023省赛H题

考察知识点&#xff1a;双向链表&#xff0c;小根堆 完整代码在文章末尾 题目 【问题描述】 给定一个长度为 N 的整数数列: A1,A2,...,AN。你要重复以下操作 K 次 :…
阅读更多...
利用云计算和微服务架构开发可扩展的同城外卖APP

利用云计算和微服务架构开发可扩展的同城外卖APP

如今&#xff0c;同城外卖APP已经成为了人们点餐的主要方式之一。然而&#xff0c;要构建一款成功的同城外卖APP&#xff0c;不仅需要满足用户的需求&#xff0c;还需要具备可扩展性&#xff0c;以适应快速增长的用户和订单量。 一、了解同城外卖APP的需求 在着手开发同城外卖…
阅读更多...
Doris：StreamLoad导入数据

Doris：StreamLoad导入数据

目录 1.基本原理 2.支持数据格式 3.StreamLoad语法 3.1.请求参数 3.2.返回参数 4.StreamLoad实践 4.1.使用 curl命令 4.2.使用Java代码 Stream load 是一个同步的导入方式&#xff0c;用户通过发送 HTTP 协议发送请求将本地文件或数据流导入到 Doris 中。Stream load 主…
阅读更多...
Git（七）.git 文件夹瘦身，GitLab 永久删除文件

Git（七）.git 文件夹瘦身，GitLab 永久删除文件

目录 一、问题背景二、问题复现2.1 新建项目2.2 上传大文件2.3 上传结果 三、解决方案3.1 GitLab备份与还原1&#xff09;备份2&#xff09;还原 3.2 删除方式一&#xff1a;git filter-repo 命令【推荐】1&#xff09;安装2&#xff09;删除本地仓库文件3&#xff09;重新关联…
阅读更多...
深度学习实战：基于TensorFlow与OpenCV的手语识别系统

深度学习实战：基于TensorFlow与OpenCV的手语识别系统

文章目录 写在前面基于TensorFlow与OpenCV的手语识别系统安装环境一、导入工具库二、导入数据集三、数据预处理四、训练模型基于CNN基于LeNet5基于ResNet50 五、模型预测基于OpenCV 写在后面 写在前面 本期内容&#xff1a;基于TensorFlow与OpenCV的手语识别系统 实验环境&…
阅读更多...
333333333333

333333333333

一、Map 接口 接下来讲的都是基于 jdk8 来开展的。 1.1 特点 1、Map 与 Collection 并列存在。Map 是用于保存具有映射关系的数据&#xff0c;即 key-value。 2、Map 中的 key 和 value 可以是任何引用类型的数据类型。 3、Map 中的 key 不允许重复&#xff0c;原因和 HashSet…
阅读更多...
动态路由协议OSPF项目部署(二)

动态路由协议OSPF项目部署(二)

1. 静态和动态路由的区别&#xff1b; 2. OSPF协议通信过程与部署&#xff1b; 3. OSPF协议在项目上的应用场景 - OSPF - 开放式最短路径优先 - 一个动态路由协议 - 路由器转发数据 - 路由器需要一张地图 - 路由表 - 路由表如何构建的&#xff1f; - 依靠手动 或…
阅读更多...
API接口加密，解决自动化中登录问题

API接口加密，解决自动化中登录问题

一、加密方式 AES&#xff1a;对称加密&#xff0c;快RAS&#xff1a;非对称加密&#xff0c;慢AESRAS&#xff1a;安全高效 加密过程&#xff1a;字符串》字节流》加密的字节流&#xff08;算法&#xff09;&#xff0c;解密有可能出现乱码&#xff0c;所以不能直接转成字符…
阅读更多...
最新文章

Copyright @ 2022~2023