当前位置： 首页 > article >正文

二叉搜索数（二叉排序树、二叉查找树）-----详解

article 2024/11/26 4:36:38

C++系列—二叉搜索树

提示：这里可以添加系列文章的所有文章的目录，目录需要自己手动添加
例如：第一章 Python 机器学习入门之pandas的使用

前言

一、二叉搜索树

1.1、二叉搜索树概念

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

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

在这里插入图片描述

二、二叉搜索树的构造

接下来我们以下面这个二叉搜索树为例进行讲解

在这里插入图片描述

假设我们需要使用这样一组数据构造一棵二叉搜索数 {8, 3, 1, 10, 6, 4, 7, 14, 13};

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

  1. 首先插入第一个元素 8，此时二叉搜索树只有一个节点，这个节点就是根节点.
  • 插入3，比较 3 和根节点 8，因为 3 < 8，所以 3 成为 8 的左子节点。
  • 插入1，比较 1 和根节点 8，1 < 8，再比较 1 和 8 的左子节点 3，因为 1 < 3，所以 1 成为 3 的左子节点。
  • 插入10，比较 10 和根节点 8，因为 10 > 8，所以 10 成为 8 的右子节点。
  • 插入6，比较 6 和根节点 8，6 < 8，再比较 6 和 8 的左子节点 3，因为 6 > 3，所以 6 成为 3 的右子节点。
  • 插入4，比较 4 和根节点 8，4 < 8，再比较 4 和 8 的左子节点 3，因为 4 > 3，继续比较 4 和 3 的右子节点 6，因为 4 < 6，所以 4 成为 6 的左子节点。
    7.插入7， 比较 7 和根节点 8，7 < 8，再比较 7 和 8 的左子节点 3，因为 7 > 3，继续比较 7 和 3 的右子节点 6，因为 7 > 6，所以 7 成为 6 的右子节点。
  • 插入14，比较 14 和根节点 8，因为 14 > 8，再比较 14 和 8 的右子节点 10，因为 14 > 10，所以 14 成为 10 的右子节点。
  • 插入13，比较 13 和根节点 8，13 > 8，再比较 13 和 8 的右子节点 10，因为 13 > 10，继续比较 13 和 10 的右子节点 14，因为 13 < 14，所以 13 成为 14 的左子节点。

我们可以看出：
只要左子树为空，就把小于父节点的数插入作为左子树
只要右子树为空，就把大于父节点的数插入作为右子树
如果不为空，就一直往下去搜索，直到找到合适的插入位置

那么构建出这样一颗二叉数，有什么用呢？
不妨思考一下，它为什么叫做二叉排序数？

当我们以中序遍历来读取它时得到的结果为：
1、2、4、6、7、8、10、13、14
这正是将上面数据升序，排序后的结果。

下面我们用代码将他实现出来：
节点：

利用结构体来实现，内部包含两个指针，一个指向左子树，一个指向右子树，一个_key变量用来存储数据。

struct BSTreeNode {
	typedef BSTreeNode<T> Node;
	T _key;
	Node* _left;
	Node* _right;
	BSTreeNode(const T&key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{
	}
};

插入：

根据我们构建上述二叉搜索的步骤，编写代码

bool _Insert(Node* root,const T&key)
{
	if (root == nullptr)
	{ 
		_root = new Node(key);//树为空，直接更新根节点
		return true;
	}	
	Node* cur = _root;//记录当前节点
	Node* parent = nullptr;//记录当前节点的父节点
	while (cur)
	{
		parent = cur;
		if (cur->_key > key)//待插入值小于当前节点存储值
		{
			cur = cur->_left;//更新当前节点到左子树
		}
		else if (cur->_key < key)//待插入值大于当前节点存储值
		{
			cur = cur->_right;//更新当前节点到右子树
		}
		else {
			return false;//待插入值等于当前节点存储值，不插入
		}
	}
	cur= new Node(key);//cur为空，结束循环，找到要插入位置
	if (parent->_key > key)//利用父节点判断连接位置
		parent->_left = cur;
	else parent->_right = cur;
	return true;
}

三、二叉排序树的查找操作

二叉搜索树又叫二叉查找树，听名字就具备优秀的查找功能，其操作与二分查找非常相似，它是利用二叉树构建时的特性，来实现快速查找的。下面我们直接来查找一个，让大家体会一下查找过程。（这里要说明以下：在正常的数据结构中，由于数据量很大，所以我们也不知道我们想要的元素在不在里面；同时也不知道每个元素具体是多少，只知道他们的大小关系。我们是在此基础上进行查找）

在这里插入图片描述
假设要找6，首先我们拿待查找值与根节点所存储值8，进行比较，发下6小于8，于是我们就可以去8的左子树中查找，也就是和3比较，发现比它大，于是去3的右子树中查找，再通过比较，发现相等，就可以找到了。同样的如果，所查找值，不存在这棵树中，最终我们会得到一个空节点。

bool find(const T&x)//用来处理类外无法获得根节点问题，也可添加一个成员函数，用于在类外获取根节点
{
	_find(_root);
}
bool _find(Node*root,const T&key)
{
	if (root == nullptr)
		return false;
	if (root->_key > key)
		return _find(root->_left);
	if (root->_key < key)
		return _find(root->_right);
	return true;
}

四、二叉搜索数的删除

这一块可以说是二叉搜索数最难的一个成员函数了

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

a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程
如下：
情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题–替换法删除（简单来说就是查找待删除节点左子树的最右节点，或右子树的最左节点来和他交换）

这样讲理论是很抽象的，下面我们结合图型来分析一下这几种情况

4.1、被删除结点为叶子结点

这一场景，即可归为情况b,也可归为情况c，如果不理解，没关系先继续往下看

直接从二叉排序中删除即可，不会影响到其他结点。例如删去13
在这里插入图片描述

4.2、被删除结点cur仅有一个孩子

情况b->仅有左孩子：
在这里插入图片描述
情况c->仅有右孩子：
在这里插入图片描述

4.3、被删除结点左右孩子都在

这种情况就要复杂很多了,大家要仔细看。

在学习堆的删除时，我们使用到了替换法，它的目的是保证，删除堆顶元素后，仍要保持结构满足堆的特性，这里也一样，我们要在删除节点后使得仍满足，搜索二叉树的性质，那么我们该找哪个位置的元素，来和待删除位置进行交换呢？

为了方便大家看，把树再放下来一份
在这里插入图片描述

假设我们们要删除8(它满足左右节点都存在），我们需要在下面找一个可以看住场子的了“老大哥”，这时只有，左子树的最大节点或右子树的最小节点，来带替这个位置最合适，即左子树的最右节点或右子树的最左节点。
使用8左子树的最右节点：

在这里插入图片描述
使用8右子树的最左节点：
在这里插入图片描述

删除操作代码：

bool erase(const T& key)
{
	if (_root == nullptr)//空树删除失败
		return false;
	Node* parent = nullptr;
	Node* cur = _root;//存储待删除节点
	while (cur)//循环找到要删除节点
	{
		parent = cur;
		if (cur->_key > key)
		{
			cur = cur->_left;
		}
		else if (cur->_key < key)
			cur = cur->_right;
		else break;
	}
	if (cur == nullptr)return false;//待删除节点不存在，返回失败
	if (cur->_left==nullptr)// 当前节点只有右孩子---可直接删除（思考一下这里叶子节点也能跑过）
	{//删除后让付节点指向右孩子，这里右孩子是否为空，不产生影响，顾上述可将四种情况，归纳为三种
		if (parent->_left = cur)
			parent->_left = cur->_right;
		else
			parent->_right = cur->_right;
		delete cur;
	}
	else if (cur->_right == nullptr)// 当前节点只有左孩子---可直接删除
	{
		if (parent->_left = cur)
			parent->_left = cur->_left;
		else
			parent->_right = cur->_left;
		delete cur;
	}
	else //左右孩子都存在
	{
		Node* parent = cur;
		Node* subLeft = cur->_right;//这里我使用的是右子树，最左节点
		while (subLeft->_left)
		{
			parent = subLeft;
			if (subLeft->_left)
				subLeft = subLeft->_left;
		}
		swap(subLeft->_key, cur->_key);//交换待删除节点，右子树最左节点（值交换）
		if (parent->_left == subLeft)
			parent->_left = subLeft->_right;
		else
			parent->_right = subLeft->_right;
		delete subLeft;
	}
	return true;
}

还有一些简单接口，就不讲解了，我把代码给大家贴出来

#include<iostream>
using namespace std;
template<class T>
struct BSTreeNode {
	typedef BSTreeNode<T> Node;
	T _key;
	Node* _left;
	Node* _right;
	BSTreeNode(const T&key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{
	}
};
template<class T>
class BSTree {
public:
	BSTree()
		:_root(nullptr)
	{
	}
	typedef BSTreeNode<int> Node;
	bool Insert(T key)
	{
		return _Insert(_root,key);
	}
	bool _Insert(Node* root,const T&key)
	{
		if (root == nullptr)
		{ 
			_root = new Node(key);
			return true;
		}	
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			parent = cur;
			if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else {
				return false;
			}
		}
		cur= new Node(key);
		if (parent->_key > key)
			parent->_left = cur;
		else parent->_right = cur;
		return true;
	}
	bool find(const T&x)
	{
		_find(_root);
	}
	bool _find(Node*root,const T&key)
	{
		if (root == nullptr)
			return false;
		if (root->_key > key)
			return _find(root->_left);
		if (root->_key < key)
			return _find(root->_right);
		return true;
	}
	bool erase(const T& key)
	{
		if (_root == nullptr)
			return false;
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			parent = cur;
			if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else if (cur->_key < key)
				cur = cur->_right;
			else break;
		}
		if (cur == nullptr)return false;
		if (cur->_left==nullptr)
		{
			if (parent->_left = cur)
				parent->_left = cur->_right;
			else
				parent->_right = cur->_right;
			delete cur;
		}
		else if (cur->_right == nullptr)
		{
			if (parent->_left = cur)
				parent->_left = cur->_left;
			else
				parent->_right = cur->_left;
			delete cur;
		}
		else 
		{
			Node* parent = cur;
			Node* subLeft = cur->_right;
			while (subLeft->_left)
			{
				parent = subLeft;
				if (subLeft->_left)
					subLeft = subLeft->_left;
			}
			swap(subLeft->_key, cur->_key);
			if (parent->_left == subLeft)
				parent->_left = subLeft->_right;
			else
				parent->_right = subLeft->_right;
			delete subLeft;
		}
		return true;
	}
	void print()
	{
		_print(_root);
	}
	void _print(Node* root)
	{
		if (root == nullptr)
			return;
		_print(root->_left);
		cout << root->_key << " ";
		_print(root->_right);
	}
	bool empty()
	{
		return _root == nullptr;
	}
	bool Erase(const T&key)
	{
		return _erase(_root,key);
	}
	bool _erase(Node*& root,const T&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
		{
			if (root->_left == nullptr)
				root = root->_right;
			else if (root->_right == nullptr)
				root = root->_left;
			else
			{
				Node* subLeft = root->_right;
				Node* parent = root;
				while (subLeft->_left)
				{
					parent = subLeft;
					subLeft = subLeft->_left;
				}
				swap(root->_key, subLeft->_key);
				if (parent->_left == subLeft)
					parent->_left = subLeft->_right;
				else
					parent->_right = subLeft->_right;
			}
		}
		return true;
	}
private:
	Node* _root;
};

总结

在学习树型结构时，希望大家可以画图理解！！！！


http://www.kler.cn/a/402625.html

相关文章：

  • 秋招面试基础总结,Java八股文基础(串联知识)，四万字大全
  • Spring 框架七大模块（Java EE 学习笔记03）
  • HTML和CSS 表单、表格练习
  • fastapi入门
  • 【v5lite】调用onnx推理
  • 表格数据处理中大语言模型的微调优化策略研究
  • 连锁SPA馆拥抱数字化转型：多门店系统赋能高效运营
  • 刘艳兵-DBA046-ASSM表空间的全表扫描范围由哪些因素综合确定？
  • 前端-let和var和const的区别
  • Leetcode215. 数组中的第K个最大元素(HOT100)
  • 「二」体验HarmonyOS端云一体化开发模板——创建端云一体化工程
  • 微服务电商平台课程-番外篇二：工作场景中git常用命令
  • RAG VS Fine-Tuning模型微调详解
  • mysql-备份(二)
  • React Native 全栈开发实战班 - 项目最佳实践之模块化开发
  • Linux 学习笔记（十九）—— 进程间通信
  • 基于卷积神经网络的皮肤病识别系统（pytorch框架，python源码，GUI界面，前端界面）
  • 天津渤海职业技术学院“讯方技术HarmonyOS人才训练营”圆满开展
  • docker使用学习一
  • Harbor2.11.1生成自签证和配置HTTPS访问
  • Flutter将应用打包发布到App Store
  • 使用国产仿真平台SmartEDA，进行Arduino仿真设计之简易红绿灯设计（二）
  • Spring 框架中哪些接口可以创建对象
  • 【Redis 探秘】Redis 性能优化技巧
  • 在Linux下配置gitee与Github的远程仓库
  • 实战OpenCV之人脸识别