【数据结构取经之路】二叉搜索树的实现

目录

前言

二叉搜索树

概念

性质

二叉搜索树的实现

结点的定义

插入

查找

删除

二叉搜索树完整代码

前言

首先，二叉搜索树是一种数据结构，了解二叉搜素树有助于理解map和set的特性。

二叉搜索树

概念

二叉搜索树又称二叉排序树，它也可能是一棵空树，走中序遍历得到的结果是有序的。

性质

二叉搜索树如果不为空，它应满足一下性质：

● 每一个节点都有一个键值，而且每一个键值唯一标识一个节点（即二叉搜索树所有节点中没有重复的值）

● 假设根节点的值为X，那么它的左子树上的所有节点的值都小于X，右子树上的所有的结点的值都大于X

● 根的左右子树都是二叉搜索树（递归性质）

二叉搜索树的实现

二叉搜索树的基本操作有插入、查找、删除，其中插入和查找好说，最麻烦的是它的删除操作。

结点的定义

template <class K>
struct BSTNode
{
	BSTNode<K>* _left;
	BSTNode<K>* _right;
	K _key;

	BSTNode(const K& key) :_left(nullptr), _right(nullptr), _key(key) {}
};

插入

例如要插入0，0比8小，往左走，遇到3，0比3小，往左走，遇到1，0比1小，往左走，遇到空， 此时可以进行插入了。 总结起来就是：遇到空就可以插入。

直接上代码，后边再总结细节~

bool Insert(const K& key)
{
    //如果根节点为空，第一个插入的结点就充当根节点
	if (_root == nullptr)
	{
		Node* newNode = new Node(key);
		_root = newNode;
		return true;
	}

	Node* cur = _root;
	Node* parent = nullptr;
	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->_key == key，该值插入进入会破坏键值的唯一性，故插入失败
		}
	}

    //不知道上述代码是往左走到空还是往右走到空，
    //所以不确定是插入左边还是右边，需要判断
	Node* newNode = new Node(key);
	if (parent->_key > key)
		parent->_left = newNode;
	else
		parent->_right = newNode;

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

删除

上面的都好说，删除才是重头戏。

首先，查找所删除的结点是否在二叉搜索树中，如果不存在则返回false，如果存在就有以下几种情况。

1）要删除的节点为叶子结点

2）要删除的结点只有左孩子或只有右孩子

3）要删除的结点左右孩子均存在

针对第一种情况，直接删除就好，没什么好说的。

针对第二种情况，请看下面分析。

例如要删除的结点为14，根据上图，我们只需要将结点10的指向调整一下，让它指向13就可以了。当然，我们还要记录被删除结点的父节点才可以正确调整指向。仔细想想，就会返现，情况1和情况2是可以一起处理的。

第三种情况：

 

例如要删除结点3，根据上图，如果我们直接删除肯定是不对的，得用替换法来删除。用谁来替换是有讲究的，我们可以选择使用节点3的左子树的最大值或者是节点3右子树的最小值，简记：左的最大，右的最小。处理成下面这样：

 处理成这样后，删除掉rightMin节点即可。当然，rightMin节点也可能有右孩子（它不可能有左孩子，因为我们找的是右子树的最小值，必然是右子树中的最左节点），我们在删除的时候考虑进去就好了，这个并不难解决。下面，我们按照上面的逻辑来把代码写出来~


bool Erase(const K& key)
{
	Node* cur = _root;
	Node* parent = nullptr;

	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 (parent->_left == cur)
					parent->_left = cur->_right;
				else
					parent->_right = cur->_right;

				delete cur;
				return true;
			}
			else if (cur->_right == nullptr)
			{
				if (parent->_left == cur)
					parent->_left = cur->_left;
				else
					parent->_right = cur->_left;

				delete cur;
				return true;
			}
			else
			{
				Node* rightMin = cur->_right;
				Node* rightMinParent = nullptr;

				while (rightMin->_left)
				{
					rightMinParent = rightMin;
					rightMin = rightMin->_left;
				}

				//可以交换，也可以直接赋值
				cur->_key = rightMin->_key;

				rigntMinParent->_left = rightMin->_right;

				delete rightMin;
				return true;
			}
		}
	}
	return false;
}

我试着用上述代码把所有插入的结点都删掉，但是程序崩了~有以下几个原因。

在这种情况下，分析删除值为8的节点。该节点的parent为空， 程序执行下面的代码：

if (cur->_left == nullptr)
{
	if (parent->_left == cur)
		parent->_left = cur->_right;
	else
		parent->_right = cur->_right;

	delete cur;
	return true;
}

这时候就是对空指针的解引用了，程序当然会崩掉~所以需要对parent为空的情况单独处理。把上述代码改成这样：

if (cur->_left == nullptr)
{
	  //左为空的情况习下，parent为可能空，即单支的树，所以需要判断
	  if (parent == nullptr)
	  {
		_root = cur->_right;
	  }
	  else
	  {
		if (parent->_left == cur)
			parent->_left = cur->_right;
		else
			parent->_right = cur->_right;
	  }

	  if (parent->_left == cur)
			parent->_left = cur->_right;
		else
			parent->_right = cur->_right;

		delete cur;
		return true;
}

上面分析的是只有左支的情况，只有右支的情况同样如此，需要做单独处理。

解决了只有单支的情况后，我又试着删除所有节点，程序还是崩了~原因如下：

3为要删除的结点。此时，按照代码逻辑，rightMin为6，rightMinParent为空， 后面执行这句代码：

rigntMinParent->_left = rightMin->_right;

 所以会崩掉~但此时我们可以看到，rightMin（节点6）的父亲结点为3，并不是空，所以rightMinParent初始化为空并不合理，应该初始化为cur。

完善到这步，也还有一个小问题，按照上面修改之后的逻辑，rightMin为6，rightMinParent为3，执行这句代码：

rigntMinParent->_left = rightMin->_right;

 我们可以很容易发现这是错的，应该是rightMinParent->_right = rightMin->_right; 所以我们还需要加判断，具体如下：

if (rightMinParent->_left == rightMin)
	rightMinParent->_left = rightMin->_right;
else
	rightMinParent->_right = rightMin->_right;

完整的修改后的代码如下：


bool Erase(const K& key)
{
	Node* cur = _root;
	Node* parent = nullptr;

	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)
			{
				//左为空的情况习下，parent为可能空，即单支的树，所以需要判断
				if (parent == nullptr)
				{
					_root = cur->_right;
				}
				else
				{
					if (parent->_left == cur)
						parent->_left = cur->_right;
					else
						parent->_right = cur->_right;
				}

				delete cur;
				return true;
			}
			else if (cur->_right == nullptr)
			{
				if (parent == nullptr)
				{
					_root = cur->_left;
				}
				else
				{
					if (parent->_left == cur)
						parent->_left = cur->_left;
					else
						parent->_right = cur->_left;
				}

				delete cur;
				return true;
			}
			else
			{
				Node* rightMin = cur->_right;
				Node* rightMinParent = cur;

				while (rightMin->_left)
				{
					rightMinParent = rightMin;
					rightMin = rightMin->_left;
				}

				//可以交换，也可以直接赋值
				cur->_key = rightMin->_key;

				//不一定是rigntMinParent的左边
				if (rightMinParent->_left == rightMin)
					rightMinParent->_left = rightMin->_right;
				else
					rightMinParent->_right = rightMin->_right;

				delete rightMin;
				return true;
			}
		}
	}
	return false;
}

二叉搜索树完整代码

#include <iostream>
using namespace std;

template <class K>
struct BSTNode
{
	BSTNode<K>* _left;
	BSTNode<K>* _right;
	K _key;

	BSTNode(const K& key):_left(nullptr), _right(nullptr), _key(key) {}
};

template <class K>
class BSTree
{
	typedef BSTNode<K> Node;
public:
bool Insert(const K& key)
{
	if (_root == nullptr)
	{
		Node* newNode = new Node(key);
		_root = newNode;
		return true;
	}

	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}

	Node* newNode = new Node(key);
	if (parent->_key > key)
		parent->_left = newNode;
	else
		parent->_right = newNode;

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

	
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	bool Erase(const K& key)
	{
		Node* cur = _root;
		Node* parent = nullptr;

		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)
				{
					//左为空的情况习下，parent为可能空，即单支的树，所以需要判断
					if (parent == nullptr)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
							parent->_left = cur->_right;
						else
							parent->_right = cur->_right;
					}

					delete cur;
					return true;
				}
				else if (cur->_right == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
							parent->_left = cur->_left;
						else
							parent->_right = cur->_left;
					}

					delete cur;
					return true;
				}
				else
				{
					Node* rightMin = cur->_right;
					//Node* rightMinParent = nullptr;
					Node* rightMinParent = cur;

					while (rightMin->_left)
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}

					cur->_key = rightMin->_key;

					//不一定是rigntMinParent的左边
					if (rightMinParent->_left == rightMin)
						rightMinParent->_left = rightMin->_right;
					else
						rightMinParent->_right = rightMin->_right;

					delete rightMin;
					return true;
				}
			}
		}
		return false;
	}

private:
	void _InOrder(Node* _root)
	{
		if (_root == nullptr)
			return;
		_InOrder(_root->_left);
		cout << _root->_key << " ";
		_InOrder(_root->_right);
	}
private:
	Node* _root = nullptr;
};

完~

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

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

相关文章

服务器操作集合

服务器操作集合

服务器使用PC作为代理访问外网 1、PC上启动代理&#xff0c;比如nginx 下载nginx&#xff1a;http://nginx.org/en/download.html 修改配置文件&#xff0c;在conf下&#xff1a; http {include mime.types;default_type application/octet-stream; sendfile …
阅读更多...
C++深度解析教程笔记12ok-继承，继承的构造与析构，同名覆盖

C++深度解析教程笔记12ok-继承，继承的构造与析构，同名覆盖

C深度解析教程笔记12 第43课 - 继承的概念和意义实验-类的组合实验-类的继承实验-子类与父类的构造顺序小结 第44课 - 继承中的访问级别实验-子类直接访问父类非公成员&#xff08;error&#xff09;实验-子类访问父类非公成员protected实验-复杂的例子bug 小结 第45课 - 不同的…
阅读更多...
如何构建全生命周期的安全体系架构来确保容器的安全？

如何构建全生命周期的安全体系架构来确保容器的安全？

容器技术在云原生应用和微服务架构中得到了广泛应用&#xff0c;其轻量、灵活和高效的特点使其成为现代IT环境中的重要工具。然而&#xff0c;尽管容器带来了许多优势&#xff0c;但其安全性问题也不容忽视。接下来跟随博主一起探索如何构建全生命周期的安全体系架构以确保容器…
阅读更多...
《算法笔记》总结No.7——二分（多例题详解版）

《算法笔记》总结No.7——二分（多例题详解版）

一.二分查找 目前有一个有序数列&#xff0c;举个例子&#xff0c;假设是1~1000&#xff0c;让我们去查找931这个数字&#xff0c;浅显且暴力的做法就是直接从头到尾遍历一遍&#xff0c;直到找到931为止。当n非常大&#xff0c;比如达到100w时&#xff0c;这是一个非常大的量级…
阅读更多...
经纬恒润底盘控制产品R-EPS成功量产

经纬恒润底盘控制产品R-EPS成功量产

近日&#xff0c;经纬恒润开发的齿条式电动助力转向系统R-EPS&#xff08;Rack-Electronic Power Steering&#xff09;搭载某新能源车企中高端MPV车型&#xff0c;成功量产落地。 该产品采用恒润Double Pinion/Rack平台级的软硬件方案&#xff0c;模块复用程度更高&#xff0c…
阅读更多...
5.4 软件工程-系统设计

5.4 软件工程-系统设计

系统设计 - 概述 设计软件系统总体结构 数据结构及数据库设计 编写概要设计文档、评审 详细设计的基本任务 真题
阅读更多...
DHCP服务、FTP服务

DHCP服务、FTP服务

一、DHCP 1.1 DHCP是什么 DHCP&#xff08;Dynamic Host Configuration Protocol&#xff0c;动态主机配置协议&#xff09;是一种网络协议&#xff0c;用于自动分配 IP 地址和其他网络配置信息给网络中的设备 1.2 DHCP的好处 自动化: 减少了手动配置 IP 地址和网络参数的工…
阅读更多...
pc端注册页面 密码校验规则

pc端注册页面 密码校验规则

1.密码校验规则 格应包含大小写字母、数字和特殊符号,长度为8-20 var validateRetrievePassword (rule, value, callback) > {let reg /^(?.*[A-Za-z])(?.*\d)(?.*[~!#$%^&*()_<>?:"{},.\/\\;[\]])[A-Za-z\d~!#$%^&*()_<>?:"{},.\/\\;…
阅读更多...
Linux系统下weblogic10.3.6版本打补丁步骤

Linux系统下weblogic10.3.6版本打补丁步骤

linux系统 weblogic补丁压缩包&#xff1a;p35586779_1036_Generic.zip 链接&#xff1a;https://pan.baidu.com/s/1EEz_zPX-VHp5EU5LLxfxjQ 提取码&#xff1a;XXXX &#xff08;补丁压缩包中包含以下东西&#xff09; 打补丁步骤&#xff1a; 1.备份原weblogic(需要先确保服…
阅读更多...
【Linux杂货铺】期末总结篇3：用户账户管理命令 | 组账户管理命令

【Linux杂货铺】期末总结篇3：用户账户管理命令 | 组账户管理命令

&#x1f308;个人主页&#xff1a;聆风吟_ &#x1f525;系列专栏&#xff1a;Linux杂货铺、Linux实践室 &#x1f516;少年有梦不应止于心动&#xff0c;更要付诸行动。 文章目录 第五章5.1 ⛳️Linux 账户5.2 ⛳️用户配置文件和目录&#xff08;未完待续&#xff09;5.2.1 …
阅读更多...
【机器学习实战】Datawhale夏令营2：音视频攻防（deepfake）Baseline句解

【机器学习实战】Datawhale夏令营2：音视频攻防（deepfake）Baseline句解

# Datawhale # AI夏令营 # 夏令营 文章目录 1. 赛题简要介绍2. 赛题数据集3. 评价指标4. Baseline整体4.1 计算样本数4.2 创建video对象4.3 下载需要的库&&补充知识4.4 设置pytorch随机种子&&CUDNN配置4.5 音视频预处理4.6 创建训练数据文件夹4.7 生成梅尔频谱…
阅读更多...
habase集群安装

habase集群安装

解压到/opt/softs目录 tar -zxvf hbase-2.4.11-bin.tar.gz -C /opt/softs/ 改名 mv hbase-2.4.11/ hbase2.4.11 配置环境变量 修改/etc/profile vim /etc/profile 添加 #HBASE_HOME export HBASE_HOME/opt/softs/hbase2.4.11 export PATH$PATH:$HBASE_HOME/bin 修改其中的…
阅读更多...
Linux部署禅道（无脑复制版）

Linux部署禅道（无脑复制版）

目录 环境部署1、下载&#xff0c;解压2、启动3、设置开机自启 登录禅道登录数据库1、设置账号2、网页登录数据库 环境 Linux系统 Centos7 《Linux一键安装包安装禅道》视频链接&#xff1a; https://www.zentao.net/zentao-install/zentao-linux-install-80523.html 部署 …
阅读更多...
matine组件库踩坑日记 --- react

matine组件库踩坑日记 --- react

Mantine实践 一 禁忌核心css样式二 添加轮播图扩展组件 一 禁忌核心css样式 import React from react import ReactDOM from react-dom/client import { BrowserRouter } from react-router-dom; import App from ./App.jsx import ./index.css import mantine/core/styles.cs…
阅读更多...
如何PR到别人仓库（指定分支，无废话）

如何PR到别人仓库（指定分支，无废话）

如何PR到别人仓库&#xff08;指定分支&#xff09; 记录一下&#xff0c;之前都是直接master分支&#xff0c;现在记录如何pr到别人仓库的其他分支 首先进入别人仓库然后点击fork到自己仓库 步骤&#xff08;以博主自己一个例子为例&#xff09; &#xff08;1&#xff09;…
阅读更多...
Andriod Stdio新建Kotlin的Jetpack Compose简单项目

Andriod Stdio新建Kotlin的Jetpack Compose简单项目

1.选择 No Activity 2.选择kotlin 4.右键选择 在目录MyApplication下 New->Compose->Empty Project 出现下面的画面 Finish 完成
阅读更多...
MySql 数据库 - 下载安装

MySql 数据库 - 下载安装

MySQL数据库 简单介绍 数据库 数据存储的仓库数据库管理系统 操作和管理数据库的大型软件SQL 操作关系型数据库的变成语言&#xff0c;是一套标准 版本 MySQL官方提供了两种不同的版本&#xff1a; 社区版 免费&#xff0c;MySQL不提供任何的技术支持商业版 收费&#xff0c…
阅读更多...
[crypt]-密码学心声

[crypt]-密码学心声

通过音乐来传递情报&#xff0c;乐谱如下&#xff1a; 乐谱中有请转成艾塞克、十进制等等&#xff0c;可以将数字转为assic试试&#xff0c;1234567&#xff0c;猜测是8进制&#xff0c;三位一组&#xff0c;破解如下&#xff1a; oct8 [111, 114, 157, 166, 145, 123, 145, …
阅读更多...
【vue教程】二. Vue特性原理详解

【vue教程】二. Vue特性原理详解

目录 回顾本章涵盖知识点Vue 实例和选项创建 Vue 实例Vue 实例的选项 Vue 模板语法插值表达式指令v-bindv-modelv-on 自定义指令创建自定义指令在模板中使用自定义指令自定义指令的钩子函数自定义指令的实例演示 指令注册局部注册指令过滤器 数据绑定和响应式原理响应式数据绑定…
阅读更多...
Prometheus监控主机进程

Prometheus监控主机进程

前言 客户端安装及配置 Premetheus服务端配置 模板导入 grafana效果图 前言 此场景主要是利用process-export监控主机的进程存活、资源占用率&#xff0c;防止进程挂掉导致服务崩溃 gitlab地址&#xff1a;GitHub - ncabatoff/process-exporter: Prometheus exporter that…
阅读更多...
最新文章

Copyright @ 2022~2023