C++——二叉树搜索树

前面写了初阶数据结构——二叉树；本文内容是来对它来进行结尾

目录

一概念

二实现

2.1查找

2.2插入 

2.3删除

完整源代码

三二叉树的应用 

 四二叉搜索树的性能分析

 五二叉搜索树相关的面试题

一概念

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

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

二实现

以下面的二叉搜索树为例：

2.1查找

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

bool find(const K& val)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_key < val)
		{
			cur = cur->_right;
		}
		else if (cur->_key > val)
		{
			cur = cur->_left;
		}
		else
		{
			//相等
			return true;
		}
	}
	return false;
}

2.2插入 

a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

bool insert(const K& val)
{
	if (_root == nullptr)
	{
		_root = new Node(val);
		return true;
	}
	else
	{
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < val)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > val)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				//相等
				return false;
			}
		}
		//判断要在parent的左还是右进行插入
		cur = new Node(val);
		if (parent->_key > val)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		return true;
	}
}

2.3删除

a先通过二叉搜索树的性质找到节点的位置

b分析删除节点的左右孩子的情况：

无左右孩子节点(不考虑)

只有左孩子节点：删除之前把左孩子交给父亲节点

只有右孩子节点：删除之前把右孩子交给父亲节点

右孩子节点都有：有两种解决方法：

1找左节点的最大值的节点Max:Max的val与待删除的val进行交换；

2找右孩子的最小值的节点Min:Min的val与待删除的val进行交换；

以第二种为例来设计代码：

要注意对特殊情况的处理(删除根节点的情况)：

 

特别要记录cur(删除节点)的父节点(cur在父节点的左边还是右边不清楚) 

bool erase(const K& val)
{
	if (_root == nullptr) return false;
	Node* parent = nullptr;
	Node* cur = _root;

	while (cur)
	{
		if (cur->_key < val)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > val)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			//找到删除位置
			//右孩子为空
			if (cur->_right == nullptr)
			{
				//cur是根节点
				if (parent == nullptr) _root = cur->_left;
				//cur的左孩子交给parent
				else
				{
					if (parent->_left == cur) parent->_left = cur->_left;
					else if (parent->_right == cur) parent->_right = cur->_left;
				}
				delete cur;
			}
			//右孩子为空
			else if (cur->_left == nullptr)
			{
				//cur==_root
				if (parent == nullptr) _root = cur->_right;
				else
				{
					if (parent->_left == cur) parent->_left = cur->_right;
					else if (parent->_right == cur) parent->_right = cur->_right;
				}
				delete cur;
			}
			//都有
			else
			{
				//找到右节点的最小值进行替换删除（左节点的最大值）

				//要删除的可能是_root patent不能为nullptr
				Node* ParentRightMin = cur;
				Node* RightMin = cur->_right;
				while (RightMin->_left)
				{
					ParentRightMin = RightMin;
					RightMin = RightMin->_left;
				}

				swap(RightMin->_key, cur->_key);

				//RightMin的右子树交给ParentRightMin
				if (ParentRightMin->_right == RightMin)
				{
					ParentRightMin->_right = RightMin->_right;
				}
				else
				{
					ParentRightMin->_left = RightMin->_right;
				}

				delete RightMin;
			}
			return true;
		}
	}
	return false;
}

完整源代码


#pragma once
#include<iostream>
using namespace std;

namespace bit
{
	template<class K>
	struct Node
	{
		Node(const K& key = K())
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
		{}

		Node<K>* _left;
		Node<K>* _right;
		K _key;
	};
	template<class K>
	class BSTree
	{
		typedef Node<K> Node;
	public:
	
		bool insert(const K& val)
		{
			if (_root == nullptr)
			{
				_root = new Node(val);
				return true;
			}
			else
			{
				Node* parent = nullptr;
				Node* cur = _root;
				while (cur)
				{
					if (cur->_key < val)
					{
						parent = cur;
						cur = cur->_right;
					}
					else if (cur->_key > val)
					{
						parent = cur;
						cur = cur->_left;
					}
					else
					{
						//相等
						return false;
					}
				}
				//判断要在parent的左还是右进行插入
				cur = new Node(val);
				if (parent->_key > val)
				{
					parent->_left = cur;
				}
				else
				{
					parent->_right = cur;
				}
				return true;
			}
		}

		bool find(const K& val)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < val)
				{
					cur = cur->_right;
				}
				else if (cur->_key > val)
				{
					cur = cur->_left;
				}
				else
				{
					//相等
					return true;
				}
			}
			return false;
		}

		bool erase(const K& val)
		{
			if (_root == nullptr) return false;
			Node* parent = nullptr;
			Node* cur = _root;

			while (cur)
			{
				if (cur->_key < val)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > val)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					//找到删除位置
					//右孩子为空
					if (cur->_right == nullptr)
					{
						//cur是根节点
						if (parent == nullptr) _root = cur->_left;
						//cur的左孩子交给parent
						else
						{
							if (parent->_left == cur) parent->_left = cur->_left;
							else if (parent->_right == cur) parent->_right = cur->_left;
						}
						delete cur;
					}
					//右孩子为空
					else if (cur->_left == nullptr)
					{
						//cur==_root
						if (parent == nullptr) _root = cur->_right;
						else
						{
							if (parent->_left == cur) parent->_left = cur->_right;
							else if (parent->_right == cur) parent->_right = cur->_right;
						}
						delete cur;
					}
					//都有
					else
					{
						//找到右节点的最小值进行替换删除（左节点的最大值）

						//要删除的可能是_root patent不能为nullptr
						Node* ParentRightMin = cur;
						Node* RightMin = cur->_right;
						while (RightMin->_left)
						{
							ParentRightMin = RightMin;
							RightMin = RightMin->_left;
						}

						swap(RightMin->_key, cur->_key);

						//RightMin的右子树交给ParentRightMin
						if (ParentRightMin->_right == RightMin)
						{
							ParentRightMin->_right = RightMin->_right;
						}
						else
						{
							ParentRightMin->_left = RightMin->_right;
						}

						delete RightMin;
					}
					return true;
				}
			}
			return false;
		}

		//进行套壳
		void _InOrder()
		{
			InOrder(_root);
			cout << endl;
		}

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

	void Test1()
	{
		BSTree<int> sb;
		sb.insert(3);
		sb.insert(2);
		sb.insert(4);
		sb._InOrder();
		sb.erase(3);
		sb.erase(2);
		sb.erase(4);
		sb._InOrder();
	}
}

三二叉树的应用 

KV模型：

每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：
比如：英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英
文单词与其对应的中文<word, chinese>就构成一种键值对：

//对二叉搜索树进行改造：
template<class K,class V>
struct Node
{
	Node(const K& key = K(),const V& val=V())
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
		,_val(val)
	{}

	Node<K,V>* _left;
	Node<K,V>* _right;
	K _key;
	V _val;
};
template<class K,class V>
class BSTree
{
	typedef Node<K,V> Node;
public:

	bool Insert(const K& val,const K& valute)
	{
		if (_root == nullptr)
		{
			_root = new Node(val,valute);
			return true;
		}
		else
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < val)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > val)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					//相等
					return false;
				}
			}
			//判断要在parent的左还是右进行插入
			if (parent->_key > val)
			{
				parent->_left = new Node(val,valute);
			}
			else
			{
				parent->_right = new Node(val,valute);
			}
			return true;
		}
	}

	Node* Find(const V& val)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < val)
			{
				cur = cur->_right;
			}
			else if (cur->_key > val)
			{
				cur = cur->_left;
			}
			else
			{
				//相等
				return cur;
			}
		}
		return nullptr;
	}
	void _InOrder()
	{
		InOrder(_root);
	}

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

void Test1()
{
	// 输入单词，查找单词对应的中文翻译
	BSTree<string, string> dict;
	dict.Insert("string", "字符串");
	dict.Insert("tree", "树");
	dict.Insert("left", "左边、剩余");
	dict.Insert("right", "右边");
	dict.Insert("sort", "排序");
	// 插入词库中所有单词
	string str;
	while (cin >> str)
	{
		Node<string, string>* ret = dict.Find(str);
		if (ret == nullptr)
		{
			cout << "单词拼写错误，词库中没有这个单词:" << endl;
		}
		else
		{
			cout << "中文翻译:" << ret->_val << endl;
		}
	}
}

 四二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。 

但二叉搜索树在不同的场景可能会有以下结构：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：long2N
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N方

而在这种最差的情况下是有办法去去对它进行调整：将二叉树进行旋转，这个我们下文在说

 五二叉搜索树相关的面试题

 1. 二叉树创建字符串。oj链接
2. 二叉树的分层遍历1。oj链接
3. 二叉树的分层遍历2。oj链接
4. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 。oj链接
5. 二叉树搜索树转换成排序双向链表。oj链接
6. 根据一棵树的前序遍历与中序遍历构造二叉树。 oj链接
7. 根据一棵树的中序遍历与后序遍历构造二叉树。oj链接
8. 二叉树的前序遍历，非递归迭代实现 。oj链接
9. 二叉树中序遍历 ，非递归迭代实现。oj链接
10. 二叉树的后序遍历 ，非递归迭代实现。oj链接

以上便是我在学习二叉搜索树的相关内容，有错误欢迎在评论区指正，谢谢！！ 

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

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

相关文章

车机HMI：驾驶员小命握在UI设计师手，九大法则必须遵循。

车机HMI：驾驶员小命握在UI设计师手，九大法则必须遵循。

本文给大家列举了九大法则&#xff0c;欢迎评论点赞交流。 在车机HMI设计中&#xff0c;为了降低驾驶员的反应时间并增加驾驶安全性&#xff0c;可以遵循以下UI设计法则&#xff1a; 易读性和可识别性 确保界面上的文本和图标清晰易读&#xff0c;避免使用过小、过于复杂或模…
阅读更多...
Servlet讲解

Servlet讲解

Servlet生命周期 我们只需要继承Servlet接口&#xff0c;查看方法即可看出Servlet的生命周期 import java.io.IOException;import javax.servlet.Servlet; import javax.servlet.ServletConfig; import javax.servlet.ServletException; import javax.servlet.ServletRequest…
阅读更多...
【RAG 论文】FiD：一种将 retrieved docs 合并输入给 LM 的方法

【RAG 论文】FiD：一种将 retrieved docs 合并输入给 LM 的方法

论文&#xff1a; Leveraging Passage Retrieval with Generative Models for Open Domain Question Answering ⭐⭐⭐⭐ EACL 2021, Facebook AI Research 论文速读 在 RAG 中&#xff0c;如何将检索出的 passages 做聚合并输入到生成模型是一个问题&#xff0c;本文提出了一…
阅读更多...
类和对象一（从封装开始讲述）

类和对象一（从封装开始讲述）

目录&#xff1a; 一.封装 二.封装扩展之包&#xff0c;自定义包 三.访问限定符 四.static成员 一.封装&#xff1a;封装&#xff1a;将数据和操作数据的方法进行有机结合&#xff0c;隐藏对象的属性和实现细节&#xff0c;仅对外公开接口来和对象进行 交互。面向对象…
阅读更多...
Oracle 流stream数据的复制

Oracle 流stream数据的复制

Oracle 流stream数据的复制 --实验的目的是捕获scott.emp1表的变化&#xff0c;将变化应用到远程数据库scott.emp1表中。 --设置初始化参数 AQ_TM_PROCESSES1 COMPATIBLE9.2.0 LOG_PARALLELISM1 GLOBAL_NAMEStrue JOB_QUEUE_PROCESSES2 --查看数据库的名称&#xff0c;我的为o…
阅读更多...
Hadoop-未授权访问-内置配合命令执行RCE

Hadoop-未授权访问-内置配合命令执行RCE

一、Hadoop常见端口及配置文件 Hadoop中有多种端口&#xff0c;这些端口用于不同的服务和通信。以下是Hadoop中常见的端口以及它们的用途&#xff1a; NameNode Web界面端口 (默认: 9870)NameNode 对客户端服务端口 (默认: 8020)Secondary NameNode Web界面端口 (默认: 9868)…
阅读更多...
undolog

undolog

undolog回滚段 undolog执行的时间&#xff1a;在执行器操作bufferpool之前。 undolog页
阅读更多...
1-02-02:虚拟化与容器化Docker环境搭建

1-02-02:虚拟化与容器化Docker环境搭建

1.02.02 虚拟化与容器化Docker环境搭建 一. 虚拟化与容器化技术简介1. 虚拟机环境2. docker环境 二. Docker 架构与隔离机制2.1 Docker 架构2.2 Docker 隔离机制2.3 资源限制2.4 Docker应用场景 三. 实战:Docker在Centos7安装与镜像加速 ❤❤❤3.1 docker安装3.2 设置镜像加速 …
阅读更多...
物流单打印机怎么调格式距离，佳易王物流托运单管理系统软件打印单据左边距调节教程

物流单打印机怎么调格式距离，佳易王物流托运单管理系统软件打印单据左边距调节教程

物流单打印机怎么调格式距离&#xff0c;佳易王物流托运单管理系统软件打印单据左边距调节教程 一、前言 以下软件操作教程以&#xff0c;佳易王物流单打印管理软件为例说明 软件文件下载可以点击最下方官网卡片——软件下载——试用版软件下载 1、佳易王物流单管理系统打印…
阅读更多...
CMake创建跨平台OpenGL工程(学习笔记)

CMake创建跨平台OpenGL工程(学习笔记)

一、跨平台环境基本配置 1、环境搭建 1&#xff09;linux OpenGL环境搭建参考&#xff1a;ubuntu18.04 OpenGL开发&#xff08;显示YUV&#xff09;_ubuntu opengl-CSDN博客 https://blog.51cto.com/cerana/6433535 本文使用的是QTCreator 2&#xff09;windows下环境搭建…
阅读更多...
三. TensorRT基础入门-ONNX注册算子的方法

三. TensorRT基础入门-ONNX注册算子的方法

目录 前言0. 简述1. 执行一下我们的python程序2.转换swin-tiny时候出现的不兼容op的例子3. 当出现导出onnx不成功的时候&#xff0c;我们需要考虑的事情4. unsupported asinh算子5. unsupported deformable conv算子总结参考 前言 自动驾驶之心推出的 《CUDA与TensorRT部署实战…
阅读更多...
新能源行业网间数据交换，更好用更专业的工具是什么？

新能源行业网间数据交换，更好用更专业的工具是什么？

新能源行业涵盖了多个方面&#xff0c;包括但不限于新能源汽车、可再生能源技术等。新能源行业发展具有重要的意义&#xff0c;新能源企业的研发数据极其重要&#xff0c;为了保障网络安全和数据安全&#xff0c;许多新能源企业采用逻辑隔离的方式进行网络隔离&#xff0c;此时…
阅读更多...
C#【进阶】泛型

C#【进阶】泛型

1、泛型 文章目录 1、泛型1、泛型是什么2、泛型分类3、泛型类和接口4、泛型方法5、泛型的作用思考 泛型方法判断类型 2、泛型约束1、什么是泛型2、各泛型约束3、约束的组合使用4、多个泛型有约束思考1 泛型实现单例模式思考2 ArrayList泛型实现增删查改 1、泛型是什么 泛型实现…
阅读更多...
08 - hive的集合函数、高级聚合函数、炸裂函数以及窗口函数

08 - hive的集合函数、高级聚合函数、炸裂函数以及窗口函数

目录 1、集合函数 1.1、size&#xff1a;集合中元素的个数 1.2、map&#xff1a;创建map集合 1.3、map_keys&#xff1a; 返回map中的key 1.4、map_values: 返回map中的value 1.5、array 声明array集合 1.6、array_contains: 判断array中是否包含某个元素 1.7、sort_a…
阅读更多...
SBM模型、超效率SBM模型代码及案例数据（补充操作视频）

SBM模型、超效率SBM模型代码及案例数据（补充操作视频）

01、数据简介 SBM&#xff08;Slack-Based Measure&#xff09;模型是一种数据包络分析&#xff08;Data Envelopment Analysis, DEA&#xff09;的方法&#xff0c;用于评估决策单元&#xff08;Decision Making Units, DMUs&#xff09;的效率。而超效率SBM模型是对SBM模型的…
阅读更多...
告别数据泥潭：PySpark性能调优的黄金法则

告别数据泥潭：PySpark性能调优的黄金法则

阿佑今天给大家带来个一张藏宝图——使用PySpark进行性能调优的黄金法则&#xff0c;从内存管理到执行计划&#xff0c;再到并行度设置&#xff0c;每一步都是提升数据处理速度的关键&#xff01; 文章目录 Python Spark 详解1. 引言2. 背景介绍2.1 大数据处理技术演变2.2 Apac…
阅读更多...
Flutter-加载中动画

Flutter-加载中动画

效果 考察内容 AnimationControllerTweenAnimatedBuilderTransformMatrix4 实现 ///源码&#xff1a;https://github.com/yixiaolunhui/flutter_xy class LoadingView extends StatefulWidget {const LoadingView({Key? key}) : super(key: key);overrideState<LoadingV…
阅读更多...
AI算法-高数5-线性代数1-基本概念、向量

AI算法-高数5-线性代数1-基本概念、向量

线性代数&#xff1a;主要研究1、张量>CV计算机视觉 2、研究张量的线性关系。 深度学习的表现之所以能够超过传统的机器学习算法离不开神经网络&#xff0c;然而神经网络最基本的数据结构就是向量和矩阵&#xff0c;神经网络的输入是向量&#xff0c;然后通过每个矩阵对向量…
阅读更多...
Vue3项目打包部署到云服务器的Nginx中

Vue3项目打包部署到云服务器的Nginx中

文章目录 一、打包vue3项目二、dist文件夹上传到服务器三、改nginx配置文件Docker安装nginx 一、打包vue3项目 npm run build 二、dist文件夹上传到服务器 将dist文件夹放到docker安装的nginx中的html目录下 三、改nginx配置文件 然后重启nginx【改了配置文件重启nginx才能…
阅读更多...
Cloudflare国内IP地址使用教程

Cloudflare国内IP地址使用教程

Cloudflare国内IP地址使用教程 加速网站&#xff1a; 首先我们添加一个 A 记录解析&#xff0c;解析 IP 就是我们服务器真实 IP&#xff1a; 然后侧边栏 SSL/TLS - 自定义主机名&#xff1a; 回退源这里填写你刚刚解析的域名&#xff0c;保存后回退源状态为有效再来接下的操作…
阅读更多...
最新文章

Copyright @ 2022~2023