【C++高阶(一)】二叉搜索树深度剖析

• 编程语言

💓博主CSDN主页:杭电码农-NEO💓

 

⏩专栏分类:C++从入门到精通⏪

 

🚚代码仓库:NEO的学习日记🚚

 

🌹关注我🫵带你学习C++

  🔝🔝

在这里插入图片描述

这里写目录标题

  • 1. 前言
  • 2. 二叉搜索树的概念以及定义
  • 3. 二叉搜索树的性质
  • 4. 二叉搜索树模拟实现
  • 5. 二叉搜索树的插入操作
  • 6. 二叉搜索树的删除分析(一)
  • 7. 二叉搜索树的删除分析(二)
  • 8. 总结以及拓展

1. 前言

从本篇文章开始正式进入C++高阶
的学习,C++高阶主要包括二叉搜索树
,AVL树,红黑树,哈希等高阶数据结构,
以及C++11和智能指针,抛异常等等.
高阶的内容往往是与普通人拉开差距的
内容,请同学们耐心学习!

本章重点:

本篇文章着重讲解二叉搜索树的概念

以及定义,以及二叉搜索树的模拟实现!

最后拓展讲解二叉搜索树的应用场景.

2. 二叉搜索树的概念以及定义

二叉搜索树又称二叉排序树

它或者是一棵空树

或者是具有以下性质的二叉树:

  • 若它的左子树不为空,则左子树的

    所有节点的值都小于根节点的值

  • 若它的右子树不为空,则右子树的

    所有节点的值都大于根节点的值

  • 它的左右子树也分别为二叉搜索树

比如:

在这里插入图片描述

3. 二叉搜索树的性质

首先,二叉搜索树是有序的!

它的中序遍历出来就是一个有序的序列

上面的图片中,中序遍历出来如下

[1,3,4,6,7,8,10,14,13] 有序序列

其次,二叉搜索树只支持增删查,并不

支持改,因为随意修改会导致这棵树

可能不满足二叉搜索树的条件,比如

将上图中的14改为9,它就不是二叉

搜索树了,这一点很好理解!

在这里插入图片描述

一点小细节,二叉搜索树中不能出现

值相同的节点,若插入时出现值相同的

节点就直接返回false,插入失败!

4. 二叉搜索树模拟实现

我们先把基本的框架搭建一下:

template
struct BSTreeNode //二叉搜索树封装的节点信息
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;
	
	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{ }
};

template
class BSTree
{
	typedef BSTreeNode Node;
private:
	Node* _root = nullptr;
}

对代码的解释:

基本框架比较容易,就是套一层

结构体后使用root,不多解释!

5. 二叉搜索树的插入操作

插入函数是最容易实现的,插入的

值比较大就往右走,比较小就往左走

如果遇见和插入值相同的值,返回false!

bool insert(const K& key)//左小右大
{
	if (_root == nullptr)//第一次插入时的操作
	{
		_root = new Node(key);
		return true;
	}
	Node* cur = _root;
	Node* prev = nullptr;
	while (cur != nullptr)
	{
		if (cur->_key < key)
		{
			prev = cur;
			cur = cur->_right;
		}	
		else if (cur->_key > key)
		{
			prev = cur;
			cur = cur->_left;
		}
		else if (cur->_key == key)
			return false;
	}
	cur = new Node(key);
	if (prev->_key > key)
		prev->_left = cur;
	else
		prev->_right = cur;
	return true;
}

对代码的解释:

定义prev的意义是最后cur找到自己的

位置后,要把cur和它的父亲链接起来,

prev起到一个连接作用!最后一步代码

在判断cur是prev的左孩子还是右孩子

6. 二叉搜索树的删除分析(一)

搜索树的删除操作较为复杂

先分析前三种比较简单的情况

我们一步一步来分析:

  1. 被删除的节点无孩子

这种情况是最简单的,直接将此

节点删除了即可,不用做特殊处理!

  1. 被删除的节点只有左孩子

此节点被删除后,将此节点的左孩子

连接到此节点的父亲节点即可!

在这里插入图片描述

3. 被删除的节点只有右孩子

此节点被删除后,将此节点的右孩子

连接到此节点的父亲节点即可!

前三种情况的代码比较容易,直接上菜!

bool erase(const K& key)//非递归版本
{
Node* prev = nullptr;
Node* cur = _root;
while (cur != nullptr)//先找到此节点再删除
{
	if (cur->_key < key)
	{
		prev = cur;
		cur = cur->_right;
	}
	else if (cur->_key > key)
	{
		prev = cur;
		cur = cur->_left;
	}
	else//找到了此节点后,开始删除
	{
		//1. 左边为空
		//2. 右边为空
		//3. 左右都不为空
		if (cur->_left == nullptr)//左孩子为空情况
		{
			if (cur == _root)
				_root = cur->_right;
			else
			{
				if (cur == prev->_left)
					prev->_left = cur->_right;
				else
					prev->_right = cur->_right;
			}
			delete cur;
			return true;
		}
		else if (cur->_right == nullptr)//右孩子为空情况
		{
			if (cur == _root)
				_root = cur->_left;
			else
			{
				if (cur == prev->_left)
					prev->_left = cur->_left;
				else
					prev->_right = cur->_left;
			}
			delete cur;
			return true;
		}
}

对代码的解释:

看似只写了两种情况,其实把左右都为

空的情况也给算进去了!

7. 二叉搜索树的删除分析(二)

当被删除的节点存在左右孩子时,

此时不再是简单的指向问题了,

这里我使用的是一个常用的方法:

替换法

替换法替换法,和谁替换呢?这个

被替换的节点一定要满足两个条件:

  1. 小于所有右子树的值
  2. 大于所有左子树的值

那么现在就有两个人选了:

一个是左子树中的最右节点

一个是右子树中的最左节点

简单画个图来理解一下:

在这里插入图片描述

假设这里统一使用右子树中最左边的

节点来替换,替换完成后,还有问题!

那就是被替换的节点的左肯定是空了

因为此节点就是最左节点了,但是它的右

不一定为空,还需要分情况讨论,

具体代码如下:

//注,此时的cur即为要删除的节点
Node* tmp = cur->_right;
Node* prevtmp = cur;
while (1) //寻找右子树中的最左节点
{
	if (tmp->_left != nullptr)
	{
		prevtmp = tmp;
		tmp = tmp->_left;
	}
	else
		break;
}
cur->_key = tmp->_key;
if (tmp->_right == nullptr)//如果被替换的节点的右为空
{
	if (prevtmp == cur)//被删除节点右边只有一个节点,直接将被删除节点的右置空
		prevtmp->_right = nullptr;
	else
		prevtmp->_left = nullptr;
	delete tmp;
	tmp = nullptr;
}
else
{
	if (prevtmp == cur)
		prevtmp->_right = tmp->_right;
	else
		prevtmp->_left = tmp->_right;
	delete tmp;
	tmp = nullptr;
}

代码解释已放在代码注释中

8. 总结以及拓展

二叉搜索树的模拟实现远远不止于此

但是我们只是想了解它的底层,而不是

写一个更好的二叉树出来,在插入和删除

这两个函数的非递归写法后,还有它们的

递归写法,毕竟一想到树总能想到递归,

递归的插入和删除留给大家自己实现

拓展链接:二叉搜索树的全部代码:

二叉搜索树模拟实现


🔎
下期预告:AVL树深度剖析 🔍

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/a9fc232433.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐