【C++】:搜索二叉树

朋友们、伙计们,我们又见面了,本期来给大家解读一下有关多态的知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成!

C 语 言 专 栏:C语言:从入门到精通

数据结构专栏:数据结构

个  人  主  页 :stackY、

C + + 专 栏   :C++

Linux 专 栏  :Linux

​ 

目录

1. 搜索二叉树

1.1 概念

1.2 搜索二叉树操作

2. 模拟实现搜索二叉树 

2.1 非递归版本

2.1.1 基本构造

2.1.2 插入

2.1.3 删除

2.1.4 查找

2.2 递归版本

2.2.1 插入

2.2.2 删除

2.2.3 查找

2.2.4 中序遍历

3. 完整代码


1. 搜索二叉树

1.1 概念

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

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

1.2 搜索二叉树操作

 

1. 二叉树的查找

a、从根开始比较,查找,比根大则往右边走查找,比根小则往左边走查找。
b、最多查找高度次,走到空,还没找到,这个值不存在。

2. 二叉树的插入

插入的具体过程如下:
a. 树为空,则直接新增节点,赋值给root指针
b. 树不空,按二叉搜索树性质查找插入位置,插入新节点

3. 二叉树的删除 

首先查找元素是否在二叉搜索树中,如果不存在,则返回, 否则要删除的结点可能分下面四种情况:
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点

2. 模拟实现搜索二叉树 

搜索二叉树有两种模型:

1. Key模型:节点中只存在一个值key,并且这个值不可以修改,比如后面学习到的set

2. Key_Value模型:节点中存在两个值,一个是key,不可修改,另一个是与key对应的value,可以修改,比如后面学习到的map

在这里我们只实现Key模型的搜索二叉树

2.1 非递归版本

2.1.1 基本构造
//节点
template<class K>
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;

	K _key;
    //构造
	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};

//搜索二叉树
template<class K>
class BSTree
{
public:
	typedef BSTreeNode<K> Node;

	//构造
	BSTree() //给定了缺省值
	{}
	//拷贝构造
	BSTree(const BSTree<K>& tmp)
	{
		_root = Copy(tmp._root);
	}
	//operator=
	BSTree<K> operator=(BSTree<K> tmp)
	{
		swap(_root, tmp._root);
		return *this;
	}
	//析构
	~BSTree()
	{
		Destroy(_root);
	}
private:
    //递归拷贝左右子树
	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* newNode = new Node(root->_key);
		newNode->_left = Copy(root->_left);
		newNode->_right = Copy(root->_right);
		return newNode;
	}
    //后序遍历删除
	void Destroy(Node*& root)
	{
		if (root == nullptr)
		{
			return;
		}
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
		root = nullptr;
	}

private:
	Node* _root = nullptr;  //缺省值给空即可
}; 
2.1.2 插入

插入时如果为空直接插入即可,若存在节点,需要先进行判断,比根节点大的插入到它的右子树,比根节点小的插入左子树即可,这时需要注意的插入的节点需要与它的父节点进行链接,这时在往下比较的过程中就需要记录一下它的父节点。

//插入
	bool Insert(const K& key)
	{
		//如果为空可以直接插入链接
		if (_root == nullptr)
		{
			_root = new Node(key);
			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);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}
2.1.3 删除

首先找到需要删除的节点,删除的时候需要注意分下面几种情况:

  • 左子树为空,可以直接删除
  • 右子树为空,可以直接删除
  • 左右子树都不为空需要使用替换法删除
  • 替换法:使用左子树最大的节点替换需要删除的节点,或者使用右子树最小的节点替换需要删除的节点,替换之后直接删除被替换的节点即可完成删除。
  • 需要注意的是在这个过程中需要记录父节点,在删除之后需要及时链接,并且要注意的是删除的节点是根节点的时候可以直接将它的左右子树直接链接。
//删除
	bool Erase(const K& key)
	{
		Node* cur = _root;
		//记录父亲
		Node* parent = nullptr;
		while (cur)
		{
			//找到要删除的key
			if (cur->_key > key)
			{
				//更新父亲
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			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    //左右子树都不为空  //使用替换法
				{
					Node* parent = cur;
					//右树的最小节点进行替换或者左树的最大节点
					Node* subRight = cur->_right;
					while (subRight->_left)  //找到右树的最小节点
					{
						parent = subRight;
						subRight = subRight->_left;
					}

					swap(cur->_key, subRight->_key);  //替换两个节点

					//将删除节点的右树链接在它的父亲
					if (parent->_left == subRight)
					{
						parent->_left = subRight->_right;
					}
					else 
					{
						parent->_right = subRight->_right;
					}
					delete subRight;
				}
				return true;
			}
		}
		return false;
	}
2.1.4 查找
//查找
	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else
				return true;
		}
		return false;
	}

2.2 递归版本

2.2.1 插入

递归插入时也需要进行一层封装,在里面传递root,在这里采用引用传参比较好,可以不用额外的链接,遇到空直接创建一个节点即可,直接在原数上进行操作。

//插入
	bool InsertR(const K& key)
	{
		return _InsertR(key, _root);
	}

bool _InsertR(const K& key, Node*& root)
	{
		//树为空直接插入即可
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		//递归左
		if (root->_key > key)
			return _InsertR(key, root->_left);
		else if (root->_key < key)  //递归右
			return _InsertR(key, root->_right);
		else
			return false;
	}
2.2.2 删除

还是采用里面封装一层,在递归删除的时候先递归找到要删除的key,然后判断它的左右子树,如果左右子树只存在一个可以直接进行删除,然后将它的孩子链接在它的节点上,如果左右孩子均存在,使用替换法,用该节点的右子树的最小节点进行替换,先使用循环找到该最小节点,然后与其交换,然后转化为递归该节点右子树的删除问题即可。

//删除
	bool EraseR(const K& key)
	{
		return _EraseR(key, _root);
	}
bool _EraseR(const K& key, Node*& root)
	{
		if (root == nullptr)
			return false;
		//查找key
		if (root->_key < key)
		{
			return _EraseR(root->_right, key);
		}
		else if (root->_key > 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* subRight = root;  //找到右树的最小节点
				while (subRight->left)
				{
					subRight = subRight->_left;
				}
				swap(root->_key, subRight->_key);  //交换
				
				return _EraseR(key, root->_right);   //转化为递归右子树的子问题
			}
		}
	}
2.2.3 查找
//查找
	bool FindR(const K& key)
	{
		_FindR(key, _root);
	}
bool _FindR(const K& key, Node* root)
	{
		if (root == nullptr)
			return false;
		if (root->_key > key)
			return _FindR(root->_left);
		else if (root->_key < key)
			return _FindR(root->_right);
		else
			return true;
	}
2.2.4 中序遍历

中序遍历时需要封装一层,在外面不好传递节点,中序遍历:左子树、根、右子树

	//中序遍历
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

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

3. 完整代码

#pragma once
#include <iostream>

using namespace std;

template<class K>
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;

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

template<class K>
class BSTree
{
public:
	typedef BSTreeNode<K> Node;

	//构造
	BSTree() //给定了缺省值
	{}
	//拷贝构造
	BSTree(const BSTree<K>& tmp)
	{
		_root = Copy(tmp._root);
	}
	//operator=
	BSTree<K> operator=(BSTree<K> tmp)
	{
		swap(_root, tmp._root);
		return *this;
	}
	//析构
	~BSTree()
	{
		Destroy(_root);
	}

	//非递归版本
	//插入
	bool Insert(const K& key)
	{
		//如果为空可以直接插入链接
		if (_root == nullptr)
		{
			_root = new Node(key);
			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);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}
	//删除
	bool Erase(const K& key)
	{
		Node* cur = _root;
		//记录父亲
		Node* parent = nullptr;
		while (cur)
		{
			//找到要删除的key
			if (cur->_key > key)
			{
				//更新父亲
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			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    //左右子树都不为空  //使用替换法
				{
					Node* parent = cur;
					//右树的最小节点进行替换或者左树的最大节点
					Node* subRight = cur->_right;
					while (subRight->_left)  //找到右树的最小节点
					{
						parent = subRight;
						subRight = subRight->_left;
					}

					swap(cur->_key, subRight->_key);  //替换两个节点

					//将删除节点的右树链接在它的父亲
					if (parent->_left == subRight)
					{
						parent->_left = subRight->_right;
					}
					else
					{
						parent->_right = subRight->_right;
					}
					delete subRight;
				}
				return true;
			}
		}
		return false;
	}

	//查找
	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else
				return true;
		}
		return false;
	}

	
	//递归版本
	//插入
	bool InsertR(const K& key)
	{
		return _InsertR(key, _root);
	}
	//删除
	bool EraseR(const K& key)
	{
		return _EraseR(key, _root);
	}
	//查找
	bool FindR(const K& key)
	{
		_FindR(key, _root);
	}
	//中序遍历
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

private:
	//插入
	bool _InsertR(const K& key, Node*& root)
	{
		//树为空直接插入即可
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		//递归左
		if (root->_key > key)
			return _InsertR(key, root->_left);
		else if (root->_key < key)  //递归右
			return _InsertR(key, root->_right);
		else
			return false;
	}
	//删除
	bool _EraseR(const K& key, Node*& root)
	{
		if (root == nullptr)
			return false;
		//查找key
		if (root->_key < key)
		{
			return _EraseR(root->_right, key);
		}
		else if (root->_key > 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* subRight = root;  //找到右树的最小节点
				while (subRight->left)
				{
					subRight = subRight->_left;
				}
				swap(root->_key, subRight->_key);  //交换

				return _EraseR(key, root->_right);   //转化为递归右子树的子问题
			}
		}
	}
	//查找
	bool _FindR(const K& key, Node* root)
	{
		if (root == nullptr)
			return false;
		if (root->_key > key)
			return _FindR(root->_left);
		else if (root->_key < key)
			return _FindR(root->_right);
		else
			return true;
	}
	//中序遍历
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
	//拷贝
	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* newNode = new Node(root->_key);
		newNode->_left = Copy(root->_left);
		newNode->_right = Copy(root->_right);
		return newNode;
	}
	//销毁
	void Destroy(Node*& root)
	{
		if (root == nullptr)
		{
			return;
		}
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
		root = nullptr;
	}
private:
	Node* _root = nullptr;
};

朋友们、伙计们,美好的时光总是短暂的,我们本期的的分享就到此结束,欲知后事如何,请听下回分解~,最后看完别忘了留下你们弥足珍贵的三连喔,感谢大家的支持!     

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

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

相关文章

uniapp实战 —— 轮播图【数字下标】(含组件封装,点击图片放大全屏预览)

组件封装 src\components\SUI_Swiper2.vue <script setup lang"ts"> import { ref } from vue const props defineProps({config: Object, })const activeIndex ref(0) const change: UniHelper.SwiperOnChange (e) > {activeIndex.value e.detail.cur…

小红书品牌投放须知,家居产品软文怎么写?

家居产品软文&#xff0c;是一种展示家居产品的文案写作形式。优秀的家居产品软文能够通过引人入胜的文字&#xff0c;吸引受众的注意力并激发他们选购家居产品的兴趣。今天我们来为大家分享一下小红书品牌投放须知&#xff0c;家居产品软文怎么写&#xff1f; 一、关键词布局 …

[mysql]linux安装mysql5.7

之前安装的时候遇到了很多问题&#xff0c;浪费了一些时间。整理出这份教程&#xff0c;照着做基本一遍过。 这是安装包: 链接&#xff1a;https://pan.baidu.com/s/1gBuQBjA4R5qRYZKPKN3uXw?pwd1nuz 1.下载安装包&#xff0c;上传到linux。我这里就放到downloads目录下面…

认知觉醒(六)

认知觉醒(六) 第二节 感性&#xff1a;顶级的成长竟然是“凭感觉” 人类生存于世&#xff0c;比拼的是脑力思维&#xff0c;但极少有人知道&#xff0c;我们的身体里还有一个更高级的系统&#xff0c;若能善用&#xff0c;成就非凡。 1941年&#xff0c;德军对英国本土进行…

十二、MapReduce概述

1、MapReduce &#xff08;1&#xff09;采用框架 MapReduce是“分散——>汇总”模式的分布式计算框架&#xff0c;可供开发人员进行相应计算 &#xff08;2&#xff09;编程接口&#xff1a; ~Map ~Reduce 其中&#xff0c;Map功能接口提供了“分散”的功能&#xff…

ChatGPT新媒体运营神器:轻松驾驭内容创作与传播

文章目录 1. 内容创作2. 社交媒体管理3. 用户互动与客户服务 《巧用ChatGPT轻松玩转新媒体运营》内容简介作者简介目录前言/序言本书内容本书特色本书读者对象获取方式 随着互联网的高速发展&#xff0c;新媒体已经成为了人们获取信息、交流思想的重要渠道。在这个信息爆炸的时…

Spring cloud - gateway

什么是Spring Cloud Gateway 先去看下官网的解释&#xff1a; This project provides an API Gateway built on top of the Spring Ecosystem, including: Spring 6, Spring Boot 3 and Project Reactor. Spring Cloud Gateway aims to provide a simple, yet effective way t…

面试题之Docker篇

1、Docker 是什么&#xff1f; Docker一个开源的应用容器引擎&#xff0c;是实现容器技术的一种工具&#xff0c;让开发者可以打包他们的应用以及环境到一个镜像中&#xff0c;可以快速的发布到任何流行的操作系统上。 2、Docker的三大核心是什么? 镜像&#xff1a;Docker的镜…

MBD Introduction

介绍 MATLAB是MathWorks公司的商业数学软件&#xff0c;应用于科学计算、可视化以及交互式程序设计等高科技计算环境。Simulink是MATLAB中的一种可视化仿真工具。 Simulink是一个模块图环境&#xff0c;用于多域仿真以及基于模型的设计。它支持系统设计、仿真、自动代码生成以…

openGauss学习笔记-144 openGauss 数据库运维-例行维护-慢sql诊断

文章目录 openGauss学习笔记-144 openGauss 数据库运维-例行维护-慢sql诊断144.1 背景信息144.2 前提条件 openGauss学习笔记-144 openGauss 数据库运维-例行维护-慢sql诊断 144.1 背景信息 在SQL语句执行性能不符合预期时&#xff0c;可以查看SQL语句执行信息&#xff0c;便…

【Linux】tmux简单使用

它允许你在一个终端窗口中创建多个终端会话&#xff0c;并在它们之间进行切换。以下是tmux的一些主要用途和功能&#xff1a; 多窗口&#xff1a; Tmux允许你在一个终端中创建多个窗口。每个窗口可以包含一个或多个终端会话&#xff0c;你可以轻松地在这些窗口之间切换。面板分…

Helio 升级为 LISTA DAO,开启多链时代新篇章并宣布积分空投计划

Helio Protocol 是 BNB Chain 上排名第一的去中心化稳定币协议&#xff0c;其推出的超额抵押和清算机制支持的去中心化稳定币 HAY&#xff0c;在 BNB Chain 有非常广泛的应用&#xff0c;包括流动性挖掘、质押、交易、储值等&#xff01; 2023 年 7 月&#xff0c;Helio Protoc…

python基于DeeplabV3Plus开发构建手机屏幕表面缺陷图像分割识别系统

Deeplab是图像分割领域非常强大的模型&#xff0c;在前面的博文中我们也进行过很多相应项目的开发实践&#xff0c;感兴趣的话可以自行移步阅读即可&#xff1a; 《基于DeepLabv3Plus开发构建人脸人像分割系统》 《基于DeepLabV3实践路面、桥梁、基建裂缝裂痕分割》 《基于D…

金蝶 Apusic 应用服务器任意文件上传漏洞

声明 本文仅用于技术交流&#xff0c;请勿用于非法用途 由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;文章作者不为此承担任何责任。 1. 产品介绍 金蝶 Apusic 是金蝶集团旗下的一款企业级应用服务器&#…

鸿蒙原生应用/元服务开发-新手入门练习心得

1.先根据案例模仿代码&#xff08;页面跳转案例&#xff09; 点击next后跳转页面&#xff0c;点击back返回第一个页面 2.模块化层层拆解代码 先创建了row&#xff0c;一行&#xff0c;在这一行里面写代码&#xff1a; 内容都放到Column中 Text内置组件可以直接引用文本 thi…

前端笔记(四)Flex 布局

标准流 标准流也叫文档流&#xff0c;指的是标签在页面中默认的派不规则&#xff0c;例如&#xff1a;块元素独占一行&#xff0c;行内元素可以一行显示多个。 但是很多的网页布局都是块元素在一行中显示的&#xff0c;这时候就需要浮动和 Flex 布局&#xff0c;浮动只需要了解…

地址栏不安全提示

在使用浏览器时访问网站的时候&#xff0c;我们可能会遇到地址栏提示不安全的情况。这种情况通常都是是由于未安装有效SSL证书或者网站SSL证书过期等原因导致的。本文将介绍如何处理地址栏提示不安全的问题&#xff0c;以确保我们的上网安全。 1&#xff0c;缺少SSL证书&#x…

基于Java SSM框架实现超市进销存购物商城管理系统项目【项目源码+论文说明】

基于java的SSM框架实现超市进销存购物商城管理系统演示 摘要 随着科学技术的飞速发展&#xff0c;社会的方方面面、各行各业都在努力与现代的先进技术接轨&#xff0c;通过科技手段来提高自身的优势&#xff0c;社区生活超市管理系统当然也不能排除在外。社区生活超市管理系统…

TQ2440开发板-按键驱动程序设计

目录 按键测试底板原理图核心板原理图使用轮询方式设计按键程序 按键测试底板原理图 TQ2440开发板有4个用户可编程按键&#xff0c;它们直接与CPU的GPIO相连&#xff0c;低电平触发中断&#xff0c;资源占用如下图所示&#xff1a; 核心板原理图 使用轮询方式设计按键程序 按…
最新文章