【C++】搜索二叉树(保姆教程)

🍅二叉树底层是堆,之前学习的简单二叉树不是大堆就是小堆,今天是二叉树进阶,一定要好好掌握!

目录

☃️1.搜索二叉树介绍

☃️2.底层实现

☃️3.key模型和key,value模型


☃️1.搜索二叉树介绍

右>根>左   这样结构的树就是搜索二叉树,显然,他的主要功能:搜索,因为想要找到x,首先和根比较,如果比根大,那么走右子树(右子树所有节点值都比root大),否则走左子树(左子树所有节点值比root小)

次要功能:排序

☃️2.底层实现

首先我们定义一个命名域,然后把下面写的所有代码封装进去

先定义一个树的节点,他是一个class也行(只不过应该写成public)那还不如写成struct,然后要保存做左孩子和右孩子,还要保存自己的节点值,并且附上初始化,方便后面用val去new,初始化的时候直接初始化列表即可,注意初始化列表的格式

然后就是整个树的类

首先把类型重命名一下,每个树的节点类型应该是node<class K>* 

重命名的时候带不带*都行,我这里没带,后面每个节点需要写成Node*

带上*,后面每个节点写成Node即可

类里面的成员变量只有根节点

 

 首先写一个构造函数

然后插入(非递归)

搜索树不允许插入重复的节点,所以要写成bool类型,不可以是void 

 我们先捋一下思路

发现这个就是来回比较的过程,如果找到了要插入的位置,还需要知道他的父节点(为了链接)

 

template <class K>

		class BST
		{
			typedef node<K> Node;
		public:
			BST()
				:_root(nullptr)
			{}
			bool insert(K val)
			{
				if (!_root) //空树,直接new然后返回true
				{
					_root = new Node(val);
					return true;
				}
				Node* parent = _root; //父节点
				Node* cur = _root;//遍历指针
				while (cur) //不走到空一直找
				{
					if (val > cur->_val) //要插入的更大,走右树
					{
						parent = cur; //先把孩子给给父亲
						cur = cur->_right; //孩子往后走
					}
					else if (val < cur->_val)//要插入的更小,走左树
					{
						parent = cur; 
						cur = cur->_left;
					}
					else
					{
						//说明存在这个节点,不可以插入
						return false;
					}
				}
				Node* newnode = new Node(val); //找到要插入的位置,new
				if (parent->_val > val) //判断往父节点的左/右插,节点val更大,说明要插入的更小,应该在左孩子
				{
					parent->_left = newnode;
				}
				else
				{
					parent->_right = newnode; //否则在右孩子
				}

				return true; //插入成功
			}

 还要查找节点函数

具体的搜索思想和刚才是一样的

	bool find(const K& val)
			{
				if (!_root) return false; //空树肯定找不到
				Node* cur = _root; //遍历指针
				while (cur)
				{
					if (cur->_val == val) return true; //找到啦
					else if (val < cur->_val) //搜索思想,不再赘述
					{
						cur = cur->_left;
					}
					else
					{
						cur = cur->_right;
					}
				}
				return false;
			}

 

中序遍历,打印二叉树

注意:这时候需要用到节点,但是根节点是私有的,我们可以写一个getroot的函数,但是最好不要破坏封装性,在函数里调用一个私有成员函数

void InOrder()
			{
				if (!_root) return;
				_InOrder(_root);//调用私有成员函数
				cout << endl; //打印之后换行
			}

 私有成员函数:

 

	void _InOrder(Node* root)
			{
				if (!root) return; //截断条件
				_InOrder(root->_left); //左
				cout << root->_val << " ";//根
				_InOrder(root->_right);//右
			}

 删除值为val的节点,如果没有返回false

要删除一个节点,要把他的父节点和其他节点连接上,所以也要保留父亲

先看搜索节点的部分 

 

判断一下是不是因为没找到目标节点才退出的

正常删除

首先要删节点左为空的情况

 

要删节点右为空,完全类似作为空,不赘述

 

 左右都不为空(删的不是叶子节点)

 

 思考:要是删的是root,不能写成,否则就是空指针的解引用

 最后完整的删除代码

bool Erase(const K& val)
			{
				if (!_root) return false; //空树不删除
				Node* cur = _root; //遍历指针
				Node* parent = _root; //父节点

				while (cur)
				{
					//首先找到要删除的节点,找不到直接false
					if (val > cur->_val) //搜索逻辑
					{
						parent = cur;
						cur = cur->_right;
					}
					else if (val < cur->_val)
					{
						parent = cur;
						cur = cur->_left;
					}
					else
					{
						break;
					}
				}
				if (!cur) 
					return false;//如果循环条件结束是因为每找到节点,直接false
				//左为空
				//右为空
				//都不为空
				if (!cur->_left)
				{
					if (cur == _root)
					{
						_root = _root->_right;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}
					delete cur;
				}

				else if (!cur->_right)
				{
					if (cur == _root)
					{
						_root = _root->_left;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
					delete cur;
				}
				else
				{
					Node* parent = cur; //保存父节点 
					Node* minRight = cur->_right; //找右树最小
					while (minRight->_left) //找小往左树走
					{
						//此时的父节点是要删除minRight的父节点
						parent = minRight; 
						minRight = minRight->_left;
					}
					cur->_val = minRight->_val; //找到右树最小,把他和要删除节点值交换
				
					if (minRight == parent->_left) //如果最小在父亲的左侧
					{
						parent->_left = minRight->_right; 
						//父亲左连minRight右,因为minRight的左一定是NULL(他是最小的)如果右节点还有一定要连上
					}
					else
					{
						parent->_right = minRight->_right;//父亲右连minRight右
					}
					delete minRight;
				}


				return true;
			}

左右都不为空时找左树最大也可以

	else
				{
					Node* parent = cur; //保存父节点 
					Node* maxleft = cur->_left;
					while (maxleft->_right)
					{
						parent = maxleft;
						maxleft = maxleft->_right;
					}
					cur->_val = maxleft->_val;
					if (maxleft == parent->_left)
						parent->_left = maxleft->_left;
					else
						parent->_right = maxleft->_left;
					delete maxleft;
				}

Find的递归版本,递归需要传根,所以还是写成调用私有吧成员函数的形式

 

	bool  _FindR(Node* root, const K& val)
			{
				if (!root) return false;
				if (root->_val > val)
				{
					//左
					_FindR(root->_left, val);
				}
				else if (root->_val < val)
				{
					_FindR(root->_right, val);
				}
				else
				{
					return true;
				}
			}

 插入的递归版本

看一个错误写法 

 

 问题在图片中写出了,无法连接

那么怎么做?给节点加上引用

 比如要插入2

 

可以递归找到插入位置在1的右

此时root是nullptr,但也是1右孩子的别名,给root开空间,就是给1右孩子开空间

bool _InsertR(Node*& root, const K& val)
			{
				if (!root) //root是他父节点的某个孩子的别名
				{
					root = new Node(val);//把孩子new,自然和父亲有链接
					return true;
				}
				if (root->_val > val)
					_InsertR(root->_left, val);
				else if (root->_val < val)
					_InsertR(root->_right, val);
				else
					return false;
			}

删除递归

 

整体思路和刚才一样的吗,只不过都不为空稍有变化 

 

 

 同样的找左树最大当替死鬼也可以

写一个copy函数(需要根,写成调用私有成员函数)

 

Node* _Copy(Node* root)
			{
				if (!root) return nullptr;

				Node* newnode = new Node(root->_val);
				newnode->_left = _Copy(root->_left);
				newnode->_right = _Copy(root->_right);

				return newnode;
			}

 还有不销毁函数

	void _Delete(Node* root, const K& val)
			{
				if (!root)
					return;
				_Delete(root->_left, val);
				_Delete(root->_right, val);
				delete root;
			}

 基本上最难最重要的就是删除函数,我们已经实现的差不多啦

最后补全析构函数和构造函数

 

	        BST()
				:_root(nullptr)
			{}
			BST(const BST<K>& t)
			{
				_root = Copy(t._root);
			}

			BST<K>& operator=(BST<K> t)
			{
				swap(_root, t._root);
				return *this;
			}

 

☃️3.key模型和key,value模型

key模型就是刚才讲的搜索树,每个节点的val就是模型里的key,

key value模型是用一个值找另一个信息的过程

比如用手机号查快递,用学号查分数

具体的代码和刚才没有很大区别,只是多了一个模板参数,和节点的变量值

namespace KV
{
	template<class K,class V>
	struct BTNode
	{
		BTNode<K, V>* _left;
		BTNode<K, V>* _right;
		V _val;
		K _key;
		BTNode(const K& key, const V& val)
			:_key(key)
			,_val(val)
			,_right(nullptr)
			,_left(nullptr)
		{}
	};
	template<class K, class V>

	class Tree
	{
		typedef  BTNode<K, V> Node;
	public:
		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;
			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 = new Node(key, value);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}

			return true;
		}

		Node* 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 cur;
				}
			}

			return nullptr;
		}

		void Inorder()
		{
			_Inorder(_root);
		}

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

			_Inorder(root->_left);
			cout << root->_key << ":" << root->_val << endl;
			_Inorder(root->_right);
		}
	private:
		Node* _root = nullptr;
	};

比如他可以帮我统计一个字符串数组中每个字符串出现的个数

 

k模型和kv模型是解决问题的两种不同手段 

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

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

相关文章

蜻蜓优化算法Python代码(详细注释)

1.代入例子&#xff0c;目标函数求最优解迭代过程&#xff1a;蜻蜓算法流程&#xff1a;蜻蜓算法&#xff08;Dragonfly Algorithm&#xff09;是一种基于种群的优化算法&#xff0c;灵感来自于蜻蜓的群集行为。该算法通过模拟蜻蜓之间的吸引力和斥力&#xff0c;以及蜻蜓的移动…

IDEA好用插件:MybatisX快速生成接口实体类mapper.xml映射文件

目录 1、在Idea中找到下载插件&#xff0c;Install&#xff0c;重启Idea 2、一个测试java文件&#xff0c;里面有com包 3、在Idea中添加数据库 --------以Oracle数据库为例 4、快速生成entity-service-mapper方法 5、查看生成的代码 6、自动生成&#xff08;增删查改&#xff0…

C++ | 对比inline内联函数和宏的不同点

文章目录一、前言二、宏的优缺点分析1、概念回顾2、宏的缺点3、宏的优点三、inline内联函数1、概念2、特性①&#xff1a;空间换时间&#x1f381;趣味杂谈&#xff1a;庞大的游戏更新包3、特性②&#xff1a;inline实现机制4、特性③&#xff1a;inline的声明与定义反汇编观察…

【链表OJ题(八)】相交链表

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;数据结构 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录链表OJ题(八)8. 相交…

【C++笔试强训】第三十二天

&#x1f387;C笔试强训 博客主页&#xff1a;一起去看日落吗分享博主的C刷题日常&#xff0c;大家一起学习博主的能力有限&#xff0c;出现错误希望大家不吝赐教分享给大家一句我很喜欢的话&#xff1a;夜色难免微凉&#xff0c;前方必有曙光 &#x1f31e;。 &#x1f4a6;&a…

Spring Bean实例化和初始化的过程

承接上文Spring Bean生命周期应用程序在运行过程中能否去读取当前系统的环境变量或系统属性?这里涉及到一个非常重要的接口Environment&#xff0c;System.getenv&#xff0c;System.getProperties都是获取当前系统环境变量&#xff0c;Environment接口的实现类AbstractEnviro…

浏览器前进与后退的秘密——栈 (栈的理解与实现)

文章目录前言&#xff1a;浏览器与栈的纠缠如何理解“栈”&#xff1f;如何实现一个“栈”&#xff1f;基于数组的顺序栈基于链表的链式栈解答开篇&#x1f431;‍&#x1f409;作者简介&#xff1a;大家好&#xff0c;我是黑洞晓威&#xff0c;一名大二学生&#xff0c;希望和…

每日算法题

题目描述 本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。 作为篮球队教练&#xff0c;你需要从以下名单中选出 11 号位至 55 号位各一名球员&#xff0c;组成球队的首发阵容。 每位球员担任 11 号位至 55 号位时的评分如下…

CCF-CSP真题《202212-3 JPEG 解码》思路+python,c++满分题解

想查看其他题的真题及题解的同学可以前往查看&#xff1a;CCF-CSP真题附题解大全 试题编号&#xff1a;202212-3试题名称&#xff1a;JPEG 解码时间限制&#xff1a;1.0s内存限制&#xff1a;512.0MB问题描述&#xff1a; 问题背景 四年一度的世界杯即将画上尾声。在本…

STM32 OTA应用开发——通过串口/RS485实现OTA升级(方式2)

STM32 OTA应用开发——通过串口/RS485实现OTA升级&#xff08;方式2&#xff09; 目录STM32 OTA应用开发——通过串口/RS485实现OTA升级&#xff08;方式2&#xff09;前言1 环境搭建2 功能描述3 程序编写3.1 BootLoader部分3.2 APP的制作4 修改工程中的内存配置4.1 Bootloader…

面试阿里测开岗失败后,被面试官在朋友圈吐槽了......

前一阵子有个徒弟向我诉苦&#xff0c;说自己在参加某大厂测试面试的时候被面试官怼得哑口无言&#xff0c;场面让他一度十分尴尬印象最深的就是下面几个问题&#xff1a;根据你以前的工作经验和学习到的测试技术&#xff0c;说说你对质量保证的理解&#xff1f;非关系型数据库…

HashMap扩容为什么每次都是之前的2倍

一. 背景介绍HashMap的底层是通过数组链表红黑树的数据结构来存放数据的。我们知道&#xff0c;当新添加元素的key值出现了hash碰撞&#xff0c;就会在同一个bucket中形成链表或者红黑树。当键值对的数量超过阈值时就会扩容&#xff0c;将以前处于同一个链表或者红黑树上的元素…

持续集成 在 Linux 上搭建 Jenkins,自动构建接口测试

本篇把从 0 开始搭建 Jenkins 的过程分享给大家&#xff0c;希望对小伙伴们有所帮助。 文章目录 在 Linux 上安装 Jenkins在 Linux 上安装 Git在 Linux 上安装 Python在 Linux 上安装 Allure配置 Jenkinsjenkins 赋能 - 使用邮箱发送测试报告jenkins 赋能 - 优化测试报告内容…

C语言刷题(6)(猜名次)——“C”

各位CSDN的uu们你们好呀&#xff0c;今天&#xff0c;小雅兰还是在复习噢&#xff0c;今天来给大家介绍一个有意思的题目 题目名称&#xff1a; 猜名次 题目内容&#xff1a; 5位运动员参加了10米台跳水比赛&#xff0c;有人让他们预测比赛结果&#xff1a; A选…

测试管理之路 —— 如何优化测试计划以提高测试覆盖率

&#x1f60f;作者简介&#xff1a;博主是一位测试管理者&#xff0c;同时也是一名对外企业兼职讲师。 &#x1f4e1;主页地址&#xff1a;&#x1f30e;【Austin_zhai】&#x1f30f; &#x1f646;目的与景愿&#xff1a;旨在于能帮助更多的测试行业人员提升软硬技能&#xf…

Github的使用

Github Date: March 8, 2023 Sum: Github的使用 Github 了解开源相关的概念 1. 什么是开源 2. 什么是开源许可协议 开源并不意味着完全没有限制&#xff0c;为了限制使用者的使用范围和保护作者的权利&#xff0c;每个开源项目都应该遵守开源许可协议&#xff08; Open Sou…

node多版本控制

前言 最近在折腾Python&#xff0c;并将node升级至v18.14.2。突然发现一个旧项目无法运行&#xff0c;也无法打包&#xff0c;里面的node-sass报错&#xff0c;显然这是因为node版本过高导致的。 将node版本降低至以前的v14.16.0&#xff0c;果然立马就能正常运行。 存在不同…

mysql-日志备份

1.binlog 用于数据恢复&#xff0c; 用于数据复制。 mysql> show variables like %log_bin%; -------------------------------------------------------------- | Variable_name | Value | ----------------------------------…

前端代码复用学习笔记:整洁架构与清晰架构

基础代码的复用往往比较简单&#xff0c;但是业务代码的复用通常是困难的&#xff0c;如果没有特殊的手段去治理项目会逐渐发展为难以维护的巨石应用&#xff0c;按照维基百科记载&#xff0c;代码的复用形式主要有三种&#xff0c;程序库&#xff0c;应用框架&#xff0c;设计…

【无标题】 6UVPX 总线架构的高性能实时信号处理

VPX630 是一款基于 6U VPX 总线架构的高速信号处理平台&#xff0c;该平台采用一片 Xilinx 的 Kintex UltraScale 系列 FPGA&#xff08;XCKU115&#xff09;作为主处理器&#xff0c;完成复杂的数据采集、回放以及实时信号处理算法。 采用一片带有 ARM内核的高性能嵌入式处理…