二叉树搜索树(下)

二叉树搜索树(下)

在这里插入图片描述

二叉搜索树key和key/value使用场景

key搜索场景

只有key作为关键码,结构中只需要存储key即可,关键码即为需要搜索到的值,搜索场景只需要判断 key在不在。key的搜索场景实现的二叉树搜索树支持增删查,但是不支持修改,修改key破坏搜索树结构了。

场景1:⼩区无⼈值守⻋库,⼩区⻋库买了⻋位的业主⻋才能进⼩区,那么物业会把买了⻋位的业主的⻋牌号录⼊后台系统,⻋辆进⼊时扫描⻋牌在不在系统中,在则抬杆,不在则提⽰⾮本⼩区⻋辆,⽆法进⼊。

场景2:检查⼀篇英⽂⽂章单词拼写是否正确,将词库中所有单词放⼊二叉搜索树,读取文章中的单词,查找是否在二叉搜索树中,不在则波浪线标红提示。

可以通俗地说,只有key作为关键码,就是判断在不在的问题。

key/value搜索场景

每⼀个关键码key,都有与之对应的值value,value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value,增/删/查还是以key为关键字⾛二叉搜索树的规则进⾏⽐较,可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树⽀持修改,但是不⽀持修改key,修改key破坏搜索树结构了,可以修改value

场景1:简单中英互译字典,树的结构中(结点)存储key(英⽂)和vlaue(中⽂),搜索时输⼊英⽂,则同时查找到了英⽂对应的中⽂。

场景2:商场⽆⼈值守⻋库,⼊⼝进场时扫描⻋牌,记录⻋牌和⼊场时间,出⼝离场时,扫描⻋牌,查找⼊场时间,⽤当前时间-⼊场时间计算出停⻋时⻓,计算出停⻋费⽤,缴费后抬杆,⻋辆离场。

场景3:统计⼀篇⽂章中单词出现的次数,读取⼀个单词,查找单词是否存在,不存在这个说明第⼀次出现,(单词,1),单词存在,则++单词对应的次数。

我们可以用命名空间将我们之前写的只有key的搜索二叉树的代码进行隔离,再用另一个命名空间将接下来要写的key/value二叉搜索树的代码进行隔离。

参考代码

namespace key
{
    //之前写的只有key的二叉搜索树结构和方法定义代码
}
namespace key_value
{
	template<class K,class V>
	struct BSTNode
	{
		K _key;
		V _value;

		BSTNode<K,V>* _left;
		BSTNode<K,V>* _right; 

		BSTNode(const K& key,const V& value)
			:_key(key)
			,_value(value)
			, _left(nullptr)
			, _right(nullptr)
		{}

	};

	template<class K,class V>
	class BSTree
	{
		using Node = BSTNode<K,V>;
	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 (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
					return false;//避免冗余
			}
			//到这里说明cur已经找到空位置了,但是不知道是从右走的还是往左走的,得再比一次
			cur = new Node(key,value);
			if (key < parent->_key)
			{
				parent->_left = cur;
			}
			else
			{
				parent->_right = cur;
			}
			return true;
		}

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

		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;//返回结点指针,方便以后修改value
				}
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					if (cur->_left == nullptr)
					{
						//父为空,也就是说要删的是头结点
						if (parent == nullptr)
						{
							_root = cur->_right;
						}
						else
						{
							//要判断父节点的左还是右指针指向cur的孩子
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}
						delete cur;
						return true;
					}
					//cur的右孩子为空,把cur的左孩子给父
					else if (cur->_right == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_left;
						}
						else
						{
							//判断父节点的左还是右指针指向cur孩子
							if (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}
						delete cur;
						return true;
					}
					else//现在是cur的左右孩子都不为空
					{
						//第一步,找R(这里采用cur的右子树的最小结点/也就是最左结点)
						Node* p = cur;//这里如果初始给空,后面如果不进循环,会造成对空指针的解引用
						Node* r = cur->_right;
						while (r->_left)
						{
							p = r;
							r = r->_left;
						}
						//第二步,进行交换(但不用真的把cur的值再去给r)
						cur->_key = r->_key;
						//第三步,删除R——很容易考虑不全面!!删除R又要把删除的问题考虑全面,但这里不能用递归,会找不到
						//在删除R时要把R的右孩子(只可能是右孩子)给给父,但是父的左还是右指针不确定
						if (p->_right == r)
						{
							p->_right = r->_right;
						}
						else
						{
							p->_left = r->_right;
						}
						delete r;
						return true;
					}
				}
			}

			return false;
		}

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

		Node* _root = nullptr;
	};
}
词典

然后我们再通过一段程序来测试一下key_value版本二叉搜索树的代码是否有误:

key_value::BSTree<string, string> dict;
dict.Insert("abandon", "抛弃");
dict.Insert("mania", "狂热");
dict.Insert("disc", "唱片");
dict.Insert("vain", "徒劳");

string str;
while (cin >> str)
{
	auto ret = dict.Find(str);
	if (ret)
	{
		cout << "->" << ret->_value << endl;
	}
	else
	{
		cout << "无此单词,请重新输入" << endl;
	}
}

这段程序里,我们通过key_value版本的二叉搜索树创建除了一个词典,然后while(cin>>str)里,cin>>str的返回值是istream类型的,可以通过operator bool转化成布尔类型(大致如此)。

总之,效果是我们可以输入多个(个数不确定)string类型的数据,然后程序在这棵树(这本词典)里查找,如果找到了,就把它的value值也就是中文名打印出来,如果找不到会提示,想要退出就按ctrl+z(相当于给流设置了一个错误标志)。

统计次数

然后我们再来一段程序,来用key_value版本的二叉搜索树进行次数的统计:

string arr[] = {"apple","melon","apple","melon","apple","apple","melon","banana","apple","banana"};
key_value::BSTree<string, int> countTree;

for (const auto& str : arr)//通过使用引用,减少赋值消耗
{
	//先查找水果在不在搜索树
	//1.不在,说明水果第一次出现,则插入<水果,1>
	//2.在,则查找到的结点中水果对应的次数++
	auto ret = countTree.Find(str);
	if (ret == __nullptr)
	{
		countTree.Insert(str, 1);
	}
	else
	{
        //修改value
		ret->_value++;
	}
}
countTree.InOrder();

搜索二叉树的拷贝问题

key_value::BSTree<string, int> copy = countTree;
copy.InOrder();

可以看到,copy和countTree里面的_root地址是一样的,说明是浅拷贝,而浅拷贝析构时会出问题(崩溃),我们需要的是深拷贝。

搜索树的析构有很多种写法,可以用循环去层序遍历地析构,但比较麻烦(析构一层的时候还得保存它的孩子)。

递归析构会简单一些。

public:
	~BSTree()
	{
		Destroy(_root);
        _root = nullptr;//别忘了
	}

private:
	void Destroy(Node* root)
	{
		if (root == nullptr)
			return;

		//后序析构
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}

这样写完析构之后,我们可以看看,在这样浅拷贝的情况下,析构时会崩溃:

要实现深拷贝,这里借助拷贝构造不好搞。

老老实实使用前序进行拷贝。

一个个插入不行,如果使用中序遍历一个个插入,形状就变了。

BSTree(const BSTree& t)
{
	_root = Copy(t._root);
}

Node* Copy(Node* root)
{
	if (root == nullptr)
		return nullptr;
	//前序
	Node* newRoot = new Node(root->_key, root->_value);
	newRoot->_left = Copy(root->_left);
	newRoot->_right = Copy(root->_right);
	return newRoot;
}

这时我们还有一个报错:没有合适的默认构造可以用。因为默认构造生成的前提是我们没有写任何的构造,而现在我们写了拷贝构造。

C++11为我们提供了关键字default:

BSTree() = default;

然后是赋值重载,这我们就可以考虑用现代写法了:

BSTree& operator=(BSTree tmp)
{
	swap(_root, tmp._root);
	return *this;
}

这里我们将要赋的值传值传参给tmp,传值传参会调用拷贝构造,tmp就是我们要的,我们将其root与 *this的root直接交换,在这个函数结束后tmp会自动销毁,把tmp现在的root也就是 *this原本的root带走。最后我们选择返回引用类型,减少消耗。

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

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

相关文章

Web项目版本更新及时通知

背景 单页应用&#xff0c;项目更新时&#xff0c;部分用户会出更新不及时&#xff0c;导致异常的问题。 技术方案 给出版本号&#xff0c;项目每次更新时通知用户&#xff0c;版本已经更新需要刷新页面。 版本号更新方案版本号变更后通知用户哪些用户需要通知&#xff1f;…

D64【python 接口自动化学习】- python基础之数据库

day64 SQL-DQL-基础查询 学习日期&#xff1a;20241110 学习目标&#xff1a;MySQL数据库-- 133 SQL-DQL-基础查询 学习笔记&#xff1a; 基础数据查询 基础数据查询-过滤 总结 基础查询的语法&#xff1a;select 字段列表|* from 表过滤查询的语法&#xff1a;select 字段…

Unity插件-Smart Inspector 免费的,接近虚幻引擎的蓝图Tab管理

习惯了虚幻的一张蓝图&#xff0c;关联所有Tab &#xff08;才发现Unity&#xff0c;的Component一直被人吐槽&#xff0c;但实际上是&#xff1a;本身结构Unity 的GameObject-Comp结构&#xff0c;是好的不能再好了&#xff0c;只是配上 smart Inspector就更清晰了&#xff0…

2024 年Postman 如何安装汉化中文版?

2024 年 Postman 的汉化中文版安装教程

单元测试、集成测试、系统测试、验收测试、压力测试、性能测试、安全性测试、兼容性测试、回归测试(超详细的分类介绍及教学)

目录 1.单元测试 实现单元测试的方法&#xff1a; 注意事项&#xff1a; 2.集成测试 需注意事项&#xff1a; 实现集成测试的方法&#xff1a; 如何实现高效且可靠的集成测试&#xff1a; 3.系统测试 实现系统测试的方法: 须知注意事项&#xff1a; 4.验收测试 实现验…

MySQL 忘记 root 密码,使用跳过密码验证进行登录

操作系统版本&#xff1a;CentOS 7 MySQL 忘记 root 密码&#xff0c;使用跳过密码验证进行登录 修改 /etc/my.cnf 配置文件&#xff0c;在 [mysqld] 后面任意一行添加 skip-grant-tables vim /etc/my.cnf 重启 MySQL systemctl restart mysqld 登录 MySQL&#xff08;无 -…

3D Web渲染引擎HOOPS Communicator:助力企业打造定制化3D可视化产品的强大工具

HOOPS Communicator为开发人员提供了多样化的定制手段&#xff0c;使其在3D网页可视化领域保持领先地位。很多潜在客户都关心如何利用HOOPS Communicator将其打造成自己产品的独特解决方案。展示我们现有合作伙伴的成功案例正是分享此信息的最佳方式。 每家合作伙伴都在产品中…

【stablediffusion】阿里发布新ID保持项目EcomID, 可从单个ID参考图像生成定制的保ID图像,ComfyUI可使用。

今天&#xff0c;我们将向您介绍一款令人兴奋的更新——阿里发布的ID保持项目EcomID。这是一款基于Stable Diffusion技术的AI绘画工具&#xff0c;旨在为您提供一键式生成高质量保ID图像的便捷体验。无论您是AI绘画的新手还是专业人士&#xff0c;这个工具都能为您带来极大的便…

计算机网络(11)和流量控制补充

这一篇对数据链路层中的和流量控制进行详细学习 流量控制&#xff08;Flow Control&#xff09;是计算机网络中确保数据流平稳传输的技术&#xff0c;旨在防止数据发送方发送过多数据&#xff0c;导致接收方的缓冲区溢出&#xff0c;进而造成数据丢失或传输失败。流量控制通常…

【VLANPWN】一款针对VLAN的安全研究和渗透测试工具

关于VLANPWN VLANPWN是一款针对VLAN的安全研究和渗透测试工具&#xff0c;该工具可以帮助广大研究人员通过对VLAN执行渗透测试&#xff0c;来研究和分析目标VLAN的安全状况。该工具专为红队研究人员和安全学习爱好者设计&#xff0c;旨在训练网络工程师提升网络的安全性能&…

ES6代理和反射新特性,详细讲解

代理与反射 es6新增了代理和反射特性&#xff0c;这两个特性为开发者提供了拦截并向基本操作嵌入额外行为的能力。 代理基础 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta charset"UTF-8"&g…

MYSQL 精通索引【快速理解】

目录 1、什么是索引&#xff1f; 2、索引结构 1.为什么不使用二叉树呢&#xff1f; 2.B树数据结果 3.B树 4.Hash结构 3、索引语法 1.创建索引 2.查看索引 3.删除索引 4、SQL性能分析 1.SQL执行频次 2.慢查询日志 3.profile详情 4.EXPLAIN 5、索引规则 1.最左前缀法则 2.索…

光驱验证 MD5 校验和

步骤 1&#xff1a;在 Ubuntu 上打包文件并生成 MD5 校验和 打包文件 使用 tar 命令将文件夹打包成 tar.gz 文件&#xff1a; tar -czvf my_files.tar.gz /path/to/folder 生成 MD5 校验和 使用 md5sum 命令生成打包文件的 MD5 校验和&#xff1a; md5sum my_files.tar.g…

《网络数据安全管理条例》将于2025年1月1日起正式施行,从业者应如何解读?

2024年9月&#xff0c;国务院总理李强签署国务院令&#xff0c;公布了《网络数据安全管理条例》&#xff08;以下简称《条例》&#xff09;&#xff0c;该条例将于2025年1月1日起正式施行。 这一条例的出台&#xff0c;标志着我国在网络数据安全领域的管理迈上了新的台阶&#…

【MMIN】缺失模态想象网络用于不确定缺失模态的情绪识别

代码地址&#xff1a;https://github.com/AIM3RUC/MMIN abstract&#xff1a; 在以往的研究中&#xff0c;多模态融合已被证明可以提高情绪识别的性能。然而&#xff0c;在实际应用中&#xff0c;我们经常会遇到模态丢失的问题&#xff0c;而哪些模态会丢失是不确定的。这使得…

【Java Web】监听器类型及其使用

文章目录 监听器使用监听器类型ServletContextListenerHttpSessionListenerServletRequestListenerServletContextAttributeListenerHttpSessionAttributeListenerServletRequestAttributeListenerHttpSessionBindingListener 监听器&#xff08;Listener&#xff09;组件用于监…

conda创建 、查看、 激活、删除 python 虚拟环境

1、创建 python 虚拟环境 ,假设该环境命名为 “name”。 conda create -n name python3.11 2、查看 python 虚拟环境。 conda info -e 3、激活使用 python 虚拟环境。 conda activate name 4、删除 python 虚拟环境 conda remove -n name --all ​​ 助力快速掌握数据集…

LaTeX之四:如何兼容中文(上手中文简历和中文论文)、在win/mac上安装新字体。

改成中文版 如果你已经修改了.cls文件和主文档&#xff0c;但编译后的PDF仍然显示英文版本&#xff0c;可能有以下几个原因&#xff1a; 编译器问题&#xff1a;确保你使用的是XeLaTeX或LuaLaTeX进行编译&#xff0c;因为它们对Unicode和中文支持更好。你可以在你的LaTeX编辑器…

视频遥控打药履带机器人技术详解

视频遥控打药履带机器人技术是一种集成了遥控操作、视频监控和履带行走系统的现代化农业植保技术。以下是对该技术的详细解析&#xff1a; 一、技术概述 视频遥控打药履带机器人主要由履带行走系统、药箱、喷雾系统、遥控系统以及视频监控系统等部分组成。通过遥控操作&#…

BB1-NHS ester被用于将各种生物活性分子与蛋白质或其他生物大分子进行共轭连接,2082771-52-4

CAS号&#xff1a;2082771-52-4 中文名&#xff1a;BB1-琥珀酰亚胺酯&#xff0c;BB1-活性酯 英文名&#xff1a;BB1-NHS ester&#xff0c;或BB1-Succinimidyl Ester 分子式&#xff1a;C32H32N6O4 分子量&#xff1a;564.63 纯度&#xff1a;≥95% 供应商&#xff1a;陕…