[C++]二叉搜索树

一、定义

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

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

二、插入insert

对于二叉搜索树的插入操作，我们将需要插入的key值与当前结点（初始结点是root结点）比较，若小于该结点的值，则往左子树走；若大于该结点的值，则往右子树走。走到空结点的时候，那么这个位置就是这个key值的归宿。

template<class K, class V>
struct BSTreeNode
{
	BSTreeNode<K, V>* left;
	BSTreeNode<K, V>* right;

	K _key;
	V _value;
};

template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K, V> Node;
public:
	BSTree()
	{
		_root = nullptr;
	}


	bool Insert(const K& key, const V& value)
	{
		if (_root == nullptr)
		{
			_root = new Node;
			_root->_key = key;
			_root->_value = value;
			_root->left = nullptr;
			_root->right = nullptr;
		}
		else
		{
			Node* cur = _root;
			Node* parent = _root;
			while (cur)
			{
				if (key < cur->_key)
				{
					parent = cur;
					cur = cur->left;

				}
				else if (key > cur->_key)
				{
					parent = cur;
					cur = cur->right;
				}
			}
			cur = new Node;
			cur->left = nullptr;
			cur->right = nullptr;
			cur->_key = key;
			cur->_value = value;

			if (key < parent->_key)
			{
				parent->left = cur;
			}
			else
			{
				parent->right = cur;
			}

		}

		return true;
	}
private:


	Node* _root = nullptr;
};

三、查找操作find

对于二叉搜索树的查找操作，我们将需要查找的key值与当前结点（初始结点是root结点）比较，若小于该结点的值，则往左子树走；若大于该结点的值，则往右子树走。

若走到空，则说明没有这个值，返回空指针。若找到该值，则返回该值的结点。

	Node* Find(const K& key)
	{
		Node* cur = _root;

		while (cur)
		{
			if (key < cur->_key)
			{
				cur = cur->left;
			}
			else if (key > cur->_key)
			{
				cur = cur->right;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}

四、删除操作

	bool Erase(const K& key)
	{
		Node* cur = _root;
		Node* parent = _root;
		while (cur)
		{
			//若key小于当前结点的值，则往左子树走
			if (key < cur->_key)
			{
				parent = cur;
				cur = cur->left;
			}

			//若key大于当前结点的值，则往右子树走
			else if (key > cur->_key)
			{
				parent = cur;
				cur = cur->right;
			}
			//若key值与当前结点的值相等，则说明该结点就是需要删除的
			else
			{
				//该结点左右子树皆为空的情况
				if (cur->left == nullptr && cur->right == nullptr)
				{
					//直接删除
					if (key < parent->_key)
					{
						parent->left = nullptr;
					}
					if (key > parent->_key)
					{
						parent->right = nullptr;
					}

					delete cur;
				}
				//该结点左子树为空的情况
				else if (cur->left == nullptr)
				{
					//将该结点的左子树链接到该结点的父结点的子树上，然后删除该结点
					if (key < parent->_key)
						parent->left = cur->right;
					else
						parent->right = cur->right;
					delete cur;
				}
				//该结点右子树为空的情况
				else if (cur->right == nullptr)
				{
					//将该结点的右子树链接到该结点的父结点的子树上，然后删除该结点
					if (key < parent->_key)
						parent->left = cur->left;
					else
						parent->right = cur->left;
					delete cur;
				}
				//左右子树皆不为空
				//该情况下，我们需要找到左子树的最大结点/右子树的最小结点
				//然后将需要删除的结点的值和找到的最大结点/最小结点的值交换
				//此时我们只需要删除交换之后值为需要删除的数值的结点
				//这里以与左子树的最大结点交换为例
				else
				{
					//del是之后需要删除的结点
					Node* del = cur->left;
					//tmp是需要删除的结点的父结点
					Node* tmp = del;
					//找到左子树的最大结点，记录为del，此时tmp为del的父结点
					while (del->right)
					{
						tmp = del;
						del = del->right;

					}
					//交换key值
					swap(cur->_key, del->_key);

					//如即将被删除的结点有左子树，则将其链接到tmp上
					if (del->left)
					{
						tmp->right = del->left;
					}
					//否则直接将tmp指向即将被删除的结点的指针置空
					else
					{
						tmp->right = nullptr;
					}

					//删除交换key值后的结点
					delete del;
					
				}

				return true;
			}
			
		}

		return false;
	}

五、中序遍历InOrder

使用中序遍历二叉搜索树时，我们得到的是一个递增序列。

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->left);
		cout << root->_key << ' ';
		_InOrder(root->right);
	}


	void InOrder()
	{
		_InOrder(_root);

		cout << endl;
	}

六、完整代码

#include<iostream>
#include<string>



template<class K, class V>
struct BSTreeNode
{
	BSTreeNode<K, V>* left;
	BSTreeNode<K, V>* right;

	K _key;
	V _value;
};

template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K, V> Node;
public:
	BSTree()
	{
		_root = nullptr;
	}


	bool Insert(const K& key, const V& value)
	{
		if (_root == nullptr)
		{
			_root = new Node;
			_root->_key = key;
			_root->_value = value;
			_root->left = nullptr;
			_root->right = nullptr;
		}
		else
		{
			Node* cur = _root;
			Node* parent = _root;
			while (cur)
			{
				if (key < cur->_key)
				{
					parent = cur;
					cur = cur->left;

				}
				else if (key > cur->_key)
				{
					parent = cur;
					cur = cur->right;
				}
			}
			cur = new Node;
			cur->left = nullptr;
			cur->right = nullptr;
			cur->_key = key;
			cur->_value = value;

			if (key < parent->_key)
			{
				parent->left = cur;
			}
			else
			{
				parent->right = cur;
			}

		}

		return true;
	}


	Node* Find(const K& key)
	{
		Node* cur = _root;

		while (cur)
		{
			if (key < cur->_key)
			{
				cur = cur->left;
			}
			else if (key > cur->_key)
			{
				cur = cur->right;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}



	bool Erase(const K& key)
	{
		Node* cur = _root;
		Node* parent = _root;
		while (cur)
		{
			//若key小于当前结点的值，则往左子树走
			if (key < cur->_key)
			{
				parent = cur;
				cur = cur->left;
			}

			//若key大于当前结点的值，则往右子树走
			else if (key > cur->_key)
			{
				parent = cur;
				cur = cur->right;
			}
			//若key值与当前结点的值相等，则说明该结点就是需要删除的
			else
			{
				//该结点左右子树皆为空的情况
				if (cur->left == nullptr && cur->right == nullptr)
				{
					//直接删除
					if (key < parent->_key)
					{
						parent->left = nullptr;
					}
					if (key > parent->_key)
					{
						parent->right = nullptr;
					}

					delete cur;
				}
				//该结点左子树为空的情况
				else if (cur->left == nullptr)
				{
					//将该结点的左子树链接到该结点的父结点的子树上，然后删除该结点
					if (key < parent->_key)
						parent->left = cur->right;
					else
						parent->right = cur->right;
					delete cur;
				}
				//该结点右子树为空的情况
				else if (cur->right == nullptr)
				{
					//将该结点的右子树链接到该结点的父结点的子树上，然后删除该结点
					if (key < parent->_key)
						parent->left = cur->left;
					else
						parent->right = cur->left;
					delete cur;
				}
				//左右子树皆不为空
				//该情况下，我们需要找到左子树的最大结点/右子树的最小结点
				//然后将需要删除的结点的值和找到的最大结点/最小结点的值交换
				//此时我们只需要删除交换之后值为需要删除的数值的结点
				//这里以与左子树的最大结点交换为例
				else
				{
					//del是之后需要删除的结点
					Node* del = cur->left;
					//tmp是需要删除的结点的父结点
					Node* tmp = del;
					//找到左子树的最大结点，记录为del，此时tmp为del的父结点
					while (del->right)
					{
						tmp = del;
						del = del->right;

					}
					//交换key值
					swap(cur->_key, del->_key);

					//如即将被删除的结点有左子树，则将其链接到tmp上
					if (del->left)
					{
						tmp->right = del->left;
					}
					//否则直接将tmp指向即将被删除的结点的指针置空
					else
					{
						tmp->right = nullptr;
					}

					//删除交换key值后的结点
					delete del;
					
				}

				return true;
			}
			
		}

		return false;
	}


	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->left);
		cout << root->_key << ' ';
		_InOrder(root->right);
	}


	void InOrder()
	{
		_InOrder(_root);

		cout << endl;
	}


private:


	Node* _root = nullptr;
};

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

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

相关文章

深入浅出熟悉OpenAI最新大作Sora文生视频大模型

深入浅出熟悉OpenAI最新大作Sora文生视频大模型

蠢蠢欲动&#xff0c;惴惴不安&#xff0c;朋友们我又来了&#xff0c;这个春节真的过的是像过山车&#xff0c;Gemini1.5 PRO还没过劲&#xff0c;OpenAI又放大招&#xff0c;人类真的要认输了吗&#xff0c;让我忍不住想要再探究竟&#xff0c;到底是什么让文生视频发生了质的…
阅读更多...
C语言—指针

C语言—指针

碎碎念:做指针题的时候我仿佛回到了原点&#xff0c;总觉得目的是为了把框架搭建起来&#xff0c;我胡说的哈31 1.利用指针变量将一个数组中的数据反向输出。 /*1.利用指针变量将一个数组中的数据反向输出。*/#include <stdio.h> #include <time.h> #include <…
阅读更多...
常用类与基础API-String的理解和不可变性

常用类与基础API-String的理解和不可变性

1.String类的理解 1.1类的声明 public final class String >final &#xff1a;String是不可继承的。 >Serializable :可序列化的接口,凡是实现此接口的类的对象就可以通过网络或本地流进行数据的传输 >comparable:凡是实现此接口的类,其对象都可以比较大小. 1.…
阅读更多...
【MySQL】多表关系的基本学习

【MySQL】多表关系的基本学习

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 ​&#x1f4ab;个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-3oES1ZdkKIklfKzq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-siz…
阅读更多...
基于8086单片机的数码管计时系统[proteus仿真]

基于8086单片机的数码管计时系统[proteus仿真]

基于8086单片机的数码管计时系统[proteus仿真] 8086仿真设计这个题目算是课程设计中常见的题目了&#xff0c;本期是一个基于8086单片机的数码管计时系统[proteus仿真] 需要的源文件和程序的小伙伴可以关注公众号【阿目分享嵌入式】&#xff0c;赞赏任意文章 2&#xffe5;&a…
阅读更多...
Fiddler抓包（网页、手机、MUMU模拟器）

Fiddler抓包（网页、手机、MUMU模拟器）

前置条件&#xff1a;电脑上下载安装好了Fiddler&#xff0c;有浏览器 一、网页抓包 1、fiddler下载安装证书 Tools-Options 勾选下面两个框 点击下面的选项&#xff0c;信任证书 会弹出弹窗&#xff0c;点击yes&#xff08;这个时候注意&#xff0c;DO_NOT_TRUST_FiddlerRo…
阅读更多...
防御保护第五次作业

防御保护第五次作业

1,办公区设备可以通过电信链路和移动链路上网(多对多的NAT,并且需要保留一个公网IP不能用来转换) FW5&#xff1a; 2,分公司设备可以通过总公司的移动链路和电信链路访问到DMz区的http服务器 FW5&#xff1a; 注&#xff1a;记得通过安全策略放行 分公司FW3 注意&#xff1a…
阅读更多...
Open CASCADE学习|曲线向曲面投影

Open CASCADE学习|曲线向曲面投影

在三维空间中&#xff0c;将曲线向曲面投影通常涉及复杂的几何计算。这个过程可以通过多种方法实现&#xff0c;但最常见的是使用数学和几何库&#xff0c;如OpenCASCADE&#xff0c;来处理这些计算。 在OpenCASCADE中&#xff0c;投影曲线到曲面通常涉及以下步骤&#xff1a;…
阅读更多...
【plt.bar绘制条形图】：从入门到精通，只需一篇文章！【Matplotlib】

【plt.bar绘制条形图】：从入门到精通，只需一篇文章！【Matplotlib】

【&#x1f4ca;plt.bar绘制条形图】&#xff1a;从入门到精通&#xff0c;只需一篇文章&#xff01;【Matplotlib】 利用Matplotlib进行数据可视化示例 &#x1f335;文章目录&#x1f335; &#x1f50d; 一、初识plt.bar&#xff1a;条形图的基本概念&#x1f4a1; 二、plt.…
阅读更多...
Spring Boot 笔记 025 主界面

Spring Boot 笔记 025 主界面

1.1 路由搭建 1.1.1 安装vue router npm install vue-router4 1.1.2 在src/router/index.js中创建路由器&#xff0c;并导出 import { createRouter, createWebHistory } from vue-router//导入组件 import LoginVue from /views/Login.vue import LayoutVue from /views/La…
阅读更多...
Eliminating Domain Bias for Federated Learning in Representation Space【文笔可参考】

Eliminating Domain Bias for Federated Learning in Representation Space【文笔可参考】

文章及作者信息&#xff1a; NIPS2023 Jianqing Zhang 上海交通大学 之前中的NeurIPS23论文刚今天传到arxiv上&#xff0c;这次我把federated learning的每一轮看成是一次bi-directional knowledge transfer过程&#xff0c;提出了一种促进server和client之间bi-direction…
阅读更多...
【机构vip教程】Requests(1)：Requests模块简介与安装

【机构vip教程】Requests(1)：Requests模块简介与安装

Requests模块简介 在python的标准库中&#xff0c;虽然提供了urllib,utllib2,httplib&#xff0c;但是做接口测试&#xff0c;requests使用更加方便快捷&#xff0c;正如官方说的&#xff0c;“让HTTP服务人类”。 Requests是用python语言基于urllib编写的&#xff0c;采用的是…
阅读更多...
【漏洞复现-通达OA】通达OA swfupload_new存在前台SQL注入漏洞

【漏洞复现-通达OA】通达OA swfupload_new存在前台SQL注入漏洞

一、漏洞简介 通达OA（Office Anywhere网络智能办公系统）是由北京通达信科科技有限公司自主研发的协同办公自动化软件，是与中国企业管理实践相结合形成的综合管理办公平台。通达OA为各行业不同规模的众多用户提供信息化管理能力，包括流程审批、行政办公、日常事务、数据统计…
阅读更多...
UVa1359/LA3491 Hills

UVa1359/LA3491 Hills

题目链接 本题是2005年ICPC亚洲区域赛杭州欧赛区的H题 题意 平面上有 n&#xff08;n≤500&#xff09;条线段&#xff0c;其中每条线段的端点都不会在其他线段上。你的任务是数一数有多少个“没有被其他线段切到”的三角形&#xff08;即小山&#xff09;。如下图所示&#x…
阅读更多...
初始树莓派 + VMware17 安装树莓派(Raspberry Pi 4B/5)

初始树莓派 + VMware17 安装树莓派(Raspberry Pi 4B/5)

文章目录 树莓派入门 VMware17 安装树莓派(Raspberry Pi 4/5B)前言一、树莓派入门指南&#xff1a;从零开始探索树莓派树莓派4B和5对比 二、在VMware Workstation 17上安装树莓派4B/5操作系统&#xff1a;实现强大性能与便捷模拟工具准备开始安装树莓派1.创建一个虚拟机2. 选择…
阅读更多...
[Docker实战] 旭日X3派上Docker Openwrt +Samba 实现局域网NAS 开启AP模式

[Docker实战] 旭日X3派上Docker Openwrt +Samba 实现局域网NAS 开启AP模式

​ &#x1f308; 博客个人主页&#xff1a;Chris在Coding &#x1f3a5; 本文所属专栏&#xff1a;[旭日X3派] [Docker实战] ❤️ 前置学习专栏&#xff1a;[Linux学习] ⏰ 我们仍在旅途 …
阅读更多...
【C++】类与对象【定义、访问限定符、this指针】

【C++】类与对象【定义、访问限定符、this指针】

&#x1f308;个人主页&#xff1a;秦jh__https://blog.csdn.net/qinjh_?spm1010.2135.3001.5343&#x1f525; 系列专栏&#xff1a;http://t.csdnimg.cn/eCa5z 目录 面向过程和面向对象初步认识 类的引入 类的定义 成员变量命名规则的建议&#xff1a; 类的访问限定符及…
阅读更多...
Java面试第一站：计算机网络基础知识

Java面试第一站：计算机网络基础知识

该系列会持续更新&#xff0c;关注我&#xff0c;第一时间获取我的最新动态哟 Java面试中&#xff0c;经常会问到跟计算机网络知识相关的考点&#xff0c;有的小伙伴不是很明白。考察网络知识有什么意义&#xff1f; 因为编程的时候&#xff0c;多数的情况下是不用我们来编写 …
阅读更多...
单主模式和多主模式切换

单主模式和多主模式切换

1 组复制模式切换注意点 组复制有两种运行模式&#xff0c;一种是单主模式&#xff0c;一种是多主模式。这个模式是在整个组中设置的&#xff0c;由 group_replication_single_primary_mode 这个系统变量指定&#xff0c;而且在所有成员上必须保持一致。ON 表示单主模式&#…
阅读更多...
OpenAI Sora视频生成机制：时空补丁

OpenAI Sora视频生成机制：时空补丁

AI如何将静态图像转化为动态、逼真的视频&#xff1f;OpenAI 的 Sora 通过时空补丁&#xff08;spacetime patches&#xff09;的创新使用给出了答案。 独特的视频生成方法 在生成模型的世界中&#xff0c;我们看到了从 GAN 到自回归和扩散模型的许多方法&#xff0c;它们都有…
阅读更多...
最新文章

Copyright @ 2022~2023