C++：二叉搜索树

1.二叉搜索树的概念

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

  • 若它的左子树不为空，那么左子树上的所有节点的值都小于等于根节点的值
  • 若它的右子树不为空，那么左子树上的所有节点的值都大于等于根节点的值
  • 它的左子树和右子树也是二叉搜索树
  • 二叉搜索树支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义，后续我们学习map/set/multimap/multiset系列的容器底层就是二叉搜索树，其中map/set不支持插入相等的值，multimap/multiset支持插入相等的值
二叉搜索树样例： 

 

2.二叉搜索树的性能分析

最优情况下，二叉搜索树为完全二叉树（或者接近完全二叉树），其高度为：O(logN)

最差情况下，二叉搜索树退化为单支树(或者类似单支）,其高度为：O(N)

所以综合而言二叉搜索树的时间复杂度为：O(N)

另外需要说明的是，二分查找也可以实现O(logN)级别的查找效率，但是二分查找有两大缺陷：

1.需要存储在支持下标随机访问的结构中(如数组），并且有序

2.插入和删除数据效率很低，这是因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据

3.二叉搜索树的插入

插入的具体过程如下：

1.如果这棵树为空树，那么直接新增节点，赋值给root节点

2.如果这棵树不为空树，按照二叉搜索树的性质，如果插入值比当前节点的值就往右走，插入值比当前节点的值小就往左走，找到空位置，新增节点并插入新节点

3.如果支持插入相等的值，如果插入值跟当前节点的值相等，可以往右走也可以向左走，找到空位置，插入新节点（要注意的是保持逻辑的一致性，插入相等的值不要一会往右走，一会往左走）

例子1：

 

int a[] = { 8,3,1,10,6,4,7,14,13};

代码：
 

template<class K>
struct BSTNode
{
	K _key;
	BSTNode<K>* _left;
	BSTNode<K>* _right;
	BSTNode(const K& key)
		:_key(key)
		, _left(nullptr)
		, _right(nullptr)
	{}
};

// Binary Search Tree
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
		{
			parent->_left = cur;
		}
		return true;
	}
	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;
};

int main()
{
	int a[] = { 8,3,1,10,6,4,7,14,13 };

	//插入值为16的节点
	BSTree<int> t;
	for (auto e : a)
	{
		t.Insert(e);
	}

	t.Insert(16);
	t.InOrder();

	return 0;
}

代码分析：

 首先我们通过一个模版结构体template<class K>  struct BSTNode定义了二叉搜索树的节点，它允许你指定一个类型为K作为节点的类型，K _key;  存储节点的值
BSTNode<K>* _left;  表示指向左节点的指针
BSTNode<K>* _right;表示指向左节点的指针

接着通过一个初始化列表初始化节点；

然后我们定义了一个模版类BSTree来表示一个二叉搜索树，接着我们在类里面先实现了插入操作，我们首先判断该节点是否为空，如果为空则代表着这是一颗空树，所以我们需要自己手动增加新节点，接着我们定义一个指向父节点的指针parent和一个指向当前节点的指针cur，cur首先赋值为根节点，然后我们使用一个while循环，如果当前节点不为空节点，那么我们继续进入循环，如果当前cur节点的值小于要插入树的值，我们让parent节点走到cur节点的位置，cur节点走到cur节点的右边（这是因为右节点大于根节点）；如果当前cur节点的值小大于要插入树的值，我们让parent节点走到cur节点的位置，cur节点走到cur节点的左边（这是因为左节点小于根节点）。当走到空位置时，我们跳出循环，重新新增一个节点。接着我们要判断一下cur节点当前要在哪里，如果要插入的值大于parent节点的值，那么在parent节点的右侧插入，如果要插入的值小于parent节点的值，那么在parent节点的左侧插入

此外，我们还定义了一个中序遍历函数void _InOrder(Node* root)来遍历这棵树，中序遍历的遍历方式是左子树，根，右子树，由于二叉搜索树的左子树的值都小于等于根节点， 二叉搜索树的右子树的值都大于等于根节点，所以使用中序遍历的结果必然是有序的。这里之所以重新定义了一个void InOrder()函数是因为 _InOrder函数是被定义为私有的，不能在类外访问

 执行结果：

4.二叉搜索树的查找

1.从根开始比较，查找x，如果x比根的值大则往右走，x比根的值小则往左走

2.最多查找高度次，如果走到空都没有找到，那么这个值不存在

3.如果不支持插入相等的值，找到x即可返回

4.如果支持插入相等的值，意味着有多个x存在，一般要求查找中序的第一个x。

例子2：

代码：

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;
		}
        //两个值相等代表已经找到了，返回true
		else
		{
			return true;
		}
	}
    //此时当前指针已经走到空位置还没有找到，返回false
	return false;
}

代码分析：

首先从根开始比较，查找key，如果key比根的值大则往右走，key比根的值小则往左走,最多查找高度次，如果走到空都没有找到（即已经走出while循环），那么这个值不存在,返回false

5.二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回false

如果查找元素存在则分以下4种情况分别处理：（假设要删除的节点为N）

1.要删除的节点N左右节点均为空

2.要删除的节点N左孩子为空，右孩子节点不为空

3.要删除的节点N右孩子为空，左孩子节点不为空

4.要删除的节点N左右节点均不为空

对应以上4中情况的解决方案：

1.把N节点的父节点对应的孩子指针指向空，直接删除N节点（把情况1当作情况2或者情况3处理是一样的）

2.把N节点的父节点对应的孩子指针指向N的右孩子，直接删除N节点

3.把N节点的父节点对应的孩子指针指向N的左孩子，直接删除N节点

4.无法直接删除N节点，因为N的两个孩子节点无处安放，只能用替换分删除。找N左子树的值的最大节点replace（最右节点）或者N右子树的值的最小节点replace（最左节点）替换N，因为这两个节点的任意一个放到N的位置都满足二叉搜索树的规则。替换N的意思是把N节点和replace节点的值交换，转而变成删除replace节点，replace节点符合情况2或情况3，可以直接删除。

情况1样例：

情况2 样例：

情况3样例：

情况4样例：

代码：

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

				delete cur;
			}

			//右为空
			else if (_root->_right == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_left;
				}

				else
				{
					//该节点为父节点的左节点
					if (cur == parent->_left)
					{
						parent->_left = cur->_left;
					}

					//该节点为父节点的右节点
					else
					{
						parent->_right = cur->_left;
					}
				}
				delete cur;
			}

			//左右节点都不为空
			else
			{
				Node* replaceParent = cur;
				Node* replace = cur->_right;

				//查找右子树中最左节点替换根节点
				while (replace->_left)
				{
					replaceParent = replace;
					replace = replace->_left;
				}

				cur->_key = replace->_key;

				if (replace == replaceParent->_left)
				{
					replaceParent->_left = replace->_right;
				}

				else
				{
					replaceParent->_right = replace->_right;
				}

				delete replace;
			}

			return true;
		}
	}

	return false;
}

代码分析：

我们定义两个指针一个指向当前节点cur，一个指向当前节点的父节点parent，首先我们在这棵二叉树中查找这个要删除的值，如果要删除的值大于当前节点的值，那么cur继续向右查找，如果要删除的值小于当前节点的值，那么cur继续向左查找，走到else语句中代表已经找到要删除的值的节点了，开始进行删除操作。

根据上面的描述我们可以知道我们可以分三种情况讨论：

第一种是左为空，右不为空：此时也分两种情况讨论：

        a：是如果当前节点为根节点，那么根节点就变换成为根节点的右节点

        b：如果当前节点为父节点的左孩子，就将父节点的左节点指向当前cur节点的右节点，如果当前节点为父节点的右孩子，就将父节点的右节点指向当前cur节点的右节点

第二种是右为空，左不为空，尝试也分两种情况讨论：

        a：是如果当前节点为根节点，那么根节点就变换成为根节点的左节点

        b：如果当前节点为父节点的左孩子，就将父节点的左节点指向当前cur节点的左节点，如果当前节点为父节点的右孩子，就将父节点的右节点指向当前cur节点的左节点

第三种是左右都为空（在此例子中使用的是查找右子树中最左节点替换要删除的节点）

此时我们需要多定义两个指针，一个指向被替换节点，一个指向被替换节点的父节点，此时被替换节点replace节点指向要删除节点的右节点，如果replace节点不为空，那么一直更新replace节点的位置，直到找到右子树中的最左节点，此时replace节点就是最左节点，将cur节点的值和replace节点的值交换，如果replace节点位于其父节点的左侧，将replaceparent节点的左节点指向replace节点的右节点，否者将replaceparent节点的右节点指向replace节点的右节点

完整代码：

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

// Binary Search Tree
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
		{
			parent->_left = cur;
		}
		return true;
	}

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

					delete cur;
				}

				//右为空
				else if (_root->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}

					else
					{
						//该节点为父节点的左节点
						if (cur == parent->_left)
						{
							parent->_left = cur->_left;
						}

						//该节点为父节点的右节点
						else
						{
							parent->_right = cur->_left;
						}
					}
					delete cur;
				}

				//左右节点都不为空
				else
				{
					Node* replaceParent = cur;
					Node* replace = cur->_right;

					//查找右子树中最左节点替换根节点
					while (replace->_left)
					{
						replaceParent = replace;
						replace = replace->_left;
					}

					cur->_key = replace->_key;

					if (replace == replaceParent->_left)
					{
						replaceParent->_left = replace->_right;
					}

					else
					{
						replaceParent->_right = replace->_right;
					}

					delete replace;
				}

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

int main()
{
	int a[] = { 8,3,1,10,6,4,7,14,13 };

	//插入值为16的节点
	BSTree<int> t;
	for (auto e : a)
	{
		t.Insert(e);
	}

	t.Insert(16);
	t.InOrder();

	t.Find(7);
	t.InOrder();

	t.Erase(8);
	t.InOrder();

	return 0;
}

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

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

相关文章

免费像素画绘制软件 | Pixelorama v1.0.3

免费像素画绘制软件 | Pixelorama v1.0.3

Pixelorama 是一款开源像素艺术多工具软件&#xff0c;旨在为用户提供一个强大且易于使用的平台来创作各种像素艺术作品&#xff0c;包括精灵、瓷砖和动画。这款软件以其丰富的工具箱、动画支持、像素完美模式、剪裁遮罩、预制及可导入的调色板等特色功能&#xff0c;满足了像素…
阅读更多...
【JavaSE系列】注解

【JavaSE系列】注解

目录 前言 一、概述 二、Java预置注解 三、自定义注解 四、元注解 1. Retention 2. Target 3. Documented 4. Inherited 5. Repeatable 五、反射注解 总结 前言 随着Java语言的发展&#xff0c;注解&#xff08;Annotations&#xff09;逐渐成为了Java编程不可或…
阅读更多...
Linux下进程间的通信--共享内存

Linux下进程间的通信--共享内存

共享内存概述&#xff1a; 共享内存是进程间通信的一种方式&#xff0c;它允许两个或多个进程共享一个给定的存储区。共享内存是最快的一种IPC形式&#xff0c;因为它允许进程直接对内存进行读写操作&#xff0c;而不需要数据在进程之间复制。 共享内存是进程间通信&#xff…
阅读更多...
MySQL基础篇(黑马程序员2022-01-18)

MySQL基础篇(黑马程序员2022-01-18)

1 MySQL数据库概述 1.1 MySQL数据库的下载,安装,启动停止 1.2 数据模型 (1)关系型数据库(RDBMS) 概念&#xff1a;建立在关系模型基础上&#xff0c;由多张相互连接的二维表组成的数据库。 特点&#xff1a; A. 使用表存储数据&#xff0c;格式统一&#xff0c;便于维护。…
阅读更多...
【JavaScript】数据结构之树

【JavaScript】数据结构之树

什么是树形结构&#xff1f; 一种分层数据的抽象模型&#xff0c;用来分层级关系的。虚拟dom它所组织的那个数据原理就是树形结构 深度优先搜索&#xff08;遍历&#xff09;- 递归 从根出发&#xff0c;尽可能深的搜索树的节点技巧 访问根节点对根节点的children挨个进行深…
阅读更多...
基于python+django+vue的社区爱心养老管理系统

基于python+django+vue的社区爱心养老管理系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、SSM项目源码 系统展示 【2025最新】基于pythondjangovueMySQL的社…
阅读更多...
mysql的zip解压缩版安装

mysql的zip解压缩版安装

文章目录 一、MySQL下载二、mysql解压缩版安装1、解压缩2、设置环境变量3、mysql初始化4、安装mysql服务5、启动mysql服务6、连接mysql7、修改初始密码8、安装完成 一、MySQL下载 下载网址&#xff1a;MySQL下载 本文以mysql8.4.2版本为例下载解压缩版。 二、mysql解压缩版安…
阅读更多...
ElementUI 快速入门：使用 Vue 脚手架搭建项目

ElementUI 快速入门：使用 Vue 脚手架搭建项目

文章目录 一 . ElementUI 的基本安装1.1 通过 Vue 脚手架创建项目1.2 在 vue 脚手架中安装 ElementUI1.3 编写页面 ElementUI 是 Vue.js 的强大 UI 框架&#xff0c;让前端界面开发变得简单高效。本教程将带你从安装到实战&#xff0c;快速掌握 ElementUI 的核心技巧。 核心内容…
阅读更多...
MS SQL Server 实战 排查多列之间的值是否重复

MS SQL Server 实战 排查多列之间的值是否重复

目录 需求 范例运行环境 数据样本设计 功能实现 上传EXCEL文件到数据库 SQL语句 小结 需求 在日常的应用中&#xff0c;排查列重复记录是经常遇到的一个问题&#xff0c;但某些需求下&#xff0c;需要我们排查一组列之间是否有重复值的情况。比如我们有一组题库数据&…
阅读更多...
【初阶数据结构】排序

【初阶数据结构】排序

目录 一、排序的概念及其运用 1.1排序的概念 1.2常见的排序算法 二、常见排序算法的实现 2 .1插入排序 2 .1.1基本思想&#xff1a; 2.1.2直接插入排序&#xff1a; 算法复杂度&#xff1a; 最坏情况&#xff1a; 最好的情况&#xff1a; 直接插入排序的特性总结&…
阅读更多...
React js Router 路由 2, (把写过的几个 app 组合起来)

React js Router 路由 2, (把写过的几个 app 组合起来)

完整的项目&#xff0c;我已经上传了&#xff0c;资源链接. 起因&#xff0c; 目的: 每次都是新建一个 react 项目&#xff0c;有点繁琐。 刚刚学了路由&#xff0c;不如写一个 大一点的 app &#xff0c;把前面写过的几个 app, 都包含进去。 这部分感觉就像是&#xff0c; …
阅读更多...
BSV区块链上的覆盖网络服务现已开放公测

BSV区块链上的覆盖网络服务现已开放公测

​​发表时间&#xff1a;2024年8月30日 BSV区块链的覆盖网络服务现已正式开放公测。对于BSV区块链生态系统内的特定交易类型和数据管理及访问&#xff0c;覆盖网络服务都可以为它们提供强大、可扩展、并且合规的解决方案。覆盖网络以及其它即将推出的BSV服务将赋予开发者、企业…
阅读更多...
SQL Server开启网络访问

SQL Server开启网络访问

目前工作中很少用到SQL Server了&#xff0c;最近需要测试几个表&#xff0c;需要搭建一个SQL Server数据库服务&#xff0c;这里做个总结吧。 安装这里就不做详细介绍了&#xff0c;本文只介绍如何开启SQL Server网络访问。 1、云服务器安全组设置 如果是搭建在云服务器上&a…
阅读更多...
CTF——简单的《MICS》

CTF——简单的《MICS》

文章目录 一、MICS1、MISC-LSB2、MISC-循环解压3、MISC-一个不同的压缩包4、MISC-异性相吸5、MISC-仔细找找6、MISC-再来一题隐写7、MISC-找找吧8、MISC-这是一张单纯的图片9、MISC-真假flag10、MISC-真正的黑客才可以看到本质11、MISC-追象者12、MICS-鸡蛋别放在一起 一、MICS…
阅读更多...
【双方演化博弈】研究理论学习

【双方演化博弈】研究理论学习

1. 演化基础 1.1.演化博弈常用软件 载学习软件: Matlab、Vensim PLE、 Visio 其中,Matlab和Vensim PLE主要是用做演化博弈仿真,Matlab是演化博弈最常用的仿真软件&#xff0c;VensimPLE是系统动力学(SD)仿真软件也是常用仿真软件之一。 Python、Netlogo等软件也可以用来做演…
阅读更多...
THREE.js：网页上的3D世界构建者

THREE.js：网页上的3D世界构建者

THREE.js&#xff1a;网页上的3D世界构建者 前言 THREE.js 是一个强大的基于 JavaScript 的库&#xff0c;它使得在网页上创建和展示三维图形变得异常简单。 通过封装复杂的 WebGL 技术&#xff0c;THREE.js 提供了一套丰富的 API&#xff0c;让开发者能够轻松地构建出令人印…
阅读更多...
基于web的 BBS论坛管理系统设计与实现

基于web的 BBS论坛管理系统设计与实现

博主介绍&#xff1a;专注于Java .net php phython 小程序 等诸多技术领域和毕业项目实战、企业信息化系统建设&#xff0c;从业十五余年开发设计教学工作 ☆☆☆ 精彩专栏推荐订阅☆☆☆☆☆不然下次找不到哟 我的博客空间发布了1000毕设题目 方便大家学习使用 感兴趣的可以…
阅读更多...
MYSQL基础-多表操作-事务-索引

MYSQL基础-多表操作-事务-索引

1. 多表设计 概述 项目开发中&#xff0c;在进行数据库表结构设计时&#xff0c;会根据业务需求及业务模块之间的关系&#xff0c;分析并设计表结构&#xff0c;由于业务之间相互关联&#xff0c;所以各个表结构之间也存在着各种联系&#xff0c;基本上分为三种&#xff1a; …
阅读更多...
网络编程基础概述

网络编程基础概述

文章目录 协议网络协议栈(osi)局域网IPIP和Mac地址端口号TCP和UDP网络字节序 协议 (网络协议的)意义:为了让计算机传输之间将信息正确传输给目标机器 不同系统之间能接入网络是因为定制了一套通用的协议以便支持不同系统间的网络通信 1.网络通信的问题: 将数据可靠的从A传给B a…
阅读更多...
Cesium 计算3d凸包(ConvexHull)

Cesium 计算3d凸包(ConvexHull)

Cesium 计算3d凸包(ConvexHull) Cesium 计算3d凸包(ConvexHull)
阅读更多...
最新文章

Copyright @ 2022~2023