C++ 搜索二叉树

目录

1.二叉搜索树概念

 2. 实现=二叉搜索树

2.1. 二叉搜索树的插入

2.2查找

2.3删除节点

3.二叉树的应用（KV结构）

1.二叉搜索树概念

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

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

 2. 实现=二叉搜索树

这是一个二叉搜索树：

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

定义结构+初始化列表：

template<class K>
//定义节点
struct BSTreeNode
{
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;
	//初始化
	BSTreeNode(const K& key)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}
};

成员变量：

template<class K>
class BSTree
{
    typedef BSTreeNode<K> Node;
	
private:
	Node* _root = nullptr;
};

2.1. 二叉搜索树的插入

（默认定义，搜索二叉树数据不允许冗余）

代码：

bool Insert(const K& key)
{
	if (_root == nullptr)
	{
		_root = new Node(key);
		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);
	if (parent->_key < key)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}

	return true;
}


代码解释：

  1. 检查根节点是否为空：如果根节点为空，则创建一个新节点作为根节点并返回true。
  2. 遍历树以找到插入位置：使用parent和cur指针来遍历树，直到找到一个空位置（即cur为nullptr）或找到与key相等的节点。
  3. 处理重复键：如果找到与key相等的节点，函数返回false，表示插入失败（因为BST中通常不允许重复的键）。
  4. 插入新节点：在遍历结束后，根据parent节点的键值来决定新节点是应该作为左子节点还是右子节点。

测试用例:

此处中序遍历（有序），我们需要访问到_root，但root是私有的，要么提供一个get函数，或者把测试函数设置成友元（没必要），这里我们用的方法是将_InOrder函数套了一层，因为我们默认是从根开始访问：

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}

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


void BST1()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> t1;
	for (auto x : a)
	{
		t1.Insert(x);
	}
	t1.InOrder();
}

运行结果：

2.2查找

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

  • while (cur): 开始一个循环，只要cur不是nullptr（即当前节点存在），就继续执行循环体。

    • if (cur->_key < key): 如果当前节点的键小于给定的键，

      • cur = cur->_right;: 移动到当前节点的右子节点。

    • else if (cur->_key > key): 如果当前节点的键大于给定的键，

      • cur = cur->_left;: 移动到当前节点的左子节点。

    • else: 如果当前节点的键与给定的键相等，

      • return cur;: 返回当前节点的指针。

测试用例：

void BST1()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> t1;
	for (auto x : a)
	{
		t1.Insert(x);
	}
	t1.InOrder();
}

运行结果：

2.3删除节点

		bool Erase(const K& key)
		{
			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
				{
					// 删除
					// 左为空，父亲指向我的右
					if (cur->_left == nullptr)
					{
						//if(parent == nullptr)
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}

						delete cur;
					}
					else if (cur->_right == nullptr)
					{
						//if(parent == nullptr)
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							// 右为空，父亲指向我的左
							if (cur == parent->_left)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}

						delete cur;
					}
					else
					{
						// 左右都不为空，替换法删除
						// 
						// 查找右子树的最左节点替代删除
						Node* rightMinParent = cur;
						Node* rightMin = cur->_right;
						while (rightMin->_left)
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_left;
						}

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

						if (rightMinParent->_left == rightMin)
							rightMinParent->_left = rightMin->_right;
						else
							rightMinParent->_right = rightMin->_right;

						delete rightMin;
					}

					return true;
				}
			}

			return false;
		}
  1. 初始化:
    • parent：用于追踪当前节点cur的父节点。
    • cur：从根节点_root开始遍历。
  2. 查找过程:
    • 使用while循环遍历树，直到找到目标节点（键值为key的节点）或遍历到叶子节点的子节点为空。
    • 更新parent和cur以指向正确的节点。
  3. 删除逻辑:
    • 当找到目标节点时，有三种情况需要考虑：
      1. 目标节点没有左子节点（cur->_left == nullptr）：
        • 如果目标节点是根节点，则将根节点设置为右子节点。
        • 否则，根据目标节点是父节点的左子节点还是右子节点，更新父节点的对应指针。
        • 释放目标节点的内存。
      2. 目标节点没有右子节点（cur->_right == nullptr）：
        • 与情况1类似，但这次更新指向左子节点。
      3. 目标节点既有左子节点又有右子节点：
        • 在目标节点的右子树中找到最小的节点（即最左边的节点）。
        • 交换目标节点和最小节点的键值。
        • 删除右子树中的最小节点（现在具有目标节点的键值）。
  4. 返回值:
    • 如果成功找到并删除了目标节点，则返回true。
    • 如果遍历到叶子节点的子节点为空且未找到目标节点，则返回false。

注意：

  • 在处理根节点时，直接比较cur == _root，这是正确的。但在注释掉的代码部分（//if(parent == nullptr)），检查parent是否为nullptr是不必要的，因为当cur是根节点时，parent始终为nullptr。

测试用例：

void BST3()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> t1;
	for (auto x : a)
	{
		t1.Insert(x);
	}
	t1.InOrder();
	cout << endl;
	t1.Erase(8);
	t1.InOrder();
}

运行结果：

3.二叉树的应用（KV结构）

1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

  • 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
  • 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方
式在现实生活中非常常见：

  • 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对。
  • 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。

这是搜索二叉树的KV模型：

实际每个节点，就是多了一个与key关联的值，搜索二叉树的实现逻辑只是与key有关。

	template<class K, class V>
	struct BSTreeNode
	{
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
		K _key;
		V _value;

		// pair<K, V> _kv;

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

	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:
		// logN
		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 cur;
		}

		bool Erase(const K& key)
		{
			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
				{
					// 删除
					// 左为空，父亲指向我的右
					if (cur->_left == nullptr)
					{
						//if(parent == nullptr)
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}

						delete cur;
					}
					else if (cur->_right == nullptr)
					{
						//if(parent == nullptr)
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							// 右为空，父亲指向我的左
							if (cur == parent->_left)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}

						delete cur;
					}
					else
					{
						// 左右都不为空，替换法删除
						// 
						// 查找右子树的最左节点替代删除
						Node* rightMinParent = cur;
						Node* rightMin = cur->_right;
						while (rightMin->_left)
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_left;
						}

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

						if (rightMinParent->_left == rightMin)
							rightMinParent->_left = rightMin->_right;
						else
							rightMinParent->_right = rightMin->_right;

						delete rightMin;
					}

					return true;
				}
			}

			return false;
		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}

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

测试案例：使用BSTree<string, int>来统计一个字符串数组中各个字符串的出现次数。

遍历字符串数组arr，对于数组中的每一个字符串str：

  1. 调用countTree的Find方法，查找该字符串是否已经存在于树中。
  2. 如果Find方法返回nullptr（或者类似表示未找到的值），说明这个字符串还没有被统计过，因此调用Insert方法将它插入到树中，并设置其值为1（表示这是第一次出现）。
  3. 如果Find方法返回了一个非nullptr的值（表示找到了对应的节点），说明这个字符串已经存在于树中，那么就将该节点对应的值（即出现次数）自增1。

	void TestBSTree()
	{
		// 统计次数
		string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };
		BSTree<string, int> countTree;
		for (const auto& str : arr)
		{
			auto ret = countTree.Find(str);
			if (ret == nullptr)
			{
				countTree.Insert(str, 1);
			}
			else
			{
				ret->_value++;
			}
		}

		countTree.InOrder();
	}
}

运行结果：

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

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

相关文章

AutoCAD中密集的填充打散后消失的问题

AutoCAD中密集的填充打散后消失的问题

有时候在AutoCAD中&#xff0c;图案填充的填充面积过大或填充太过密集时&#xff0c;将该填充打散&#xff0c;也就是执行Explode时&#xff0c;会发现填充图案消失了。 原因是打散后线条太大&#xff0c;系统就不显示了。可以通过设置&#xff1a;HPMAXLINES 值&#xff0c;来…
阅读更多...
奇诡 matlab 小 bug matlab git需要记录的改动太多

奇诡 matlab 小 bug matlab git需要记录的改动太多

似乎是我有一次添加了太多的路径之后的事情。但是不敢说一定是这个导致的&#xff1a; 症状&#xff1a;只要对文本进行任何编辑操作&#xff0c;工作区就会出现"Processing … Cancel"的提示&#xff0c;如果不管的话这个提示不会消失&#xff0c;同时matlab变得越来…
阅读更多...
Minimal-Supervised Medical Image Segmentation via Vector Quantization Memory

Minimal-Supervised Medical Image Segmentation via Vector Quantization Memory

文章目录 Minimal-Supervised Medical Image Segmentation via Vector Quantization Memory摘要方法实验结果 Minimal-Supervised Medical Image Segmentation via Vector Quantization Memory 摘要 辅助重构分支&#xff1a;该分支通过提供额外的监督并产生学习视觉表示所需…
阅读更多...
2025COSP深圳户外展已定档招商工作正式启动！抢占先机，领跑华南市场

2025COSP深圳户外展已定档招商工作正式启动！抢占先机，领跑华南市场

想开拓全国最具消费能力的华南市场&#xff1f; 想招到优质的实力经销商&#xff1f; 想快速的提高品牌知名度&#xff1f; 2025-COSP深圳国际户外展会将于2025年2月27-3月1日在深圳福田会展中心盛大开幕&#xff01; 回顾过去 2024-COSP深圳国际户外展我们取得了较好的成绩…
阅读更多...
UEC++ FString做为参数取值时报错error：C4840

UEC++ FString做为参数取值时报错error：C4840

问题描述 用来取FString类型的变量时报错&#xff1a; 问题解决 点击错误位置&#xff0c;跳转到代码&#xff1a; void AMyDelegateActor::TwoParamDelegateFunc(int32 param1, FString param2) {UE_LOG(LogTemp, Warning, TEXT("Two Param1:%d Param2:%s"), param…
阅读更多...
流量分析（一)

流量分析（一)

数据库类流量分析 MySQL流量 常规操作&#xff0c;查找flag ctfhub{} 注意要选择字符集 Redis流量 查找ctfhub结果没找到 尝试把其变成十六进制继续进行查找 看到了前半段flag 接着往下看 找到了后半段的flag MongoDB流量 还是一样查找ctfhub 字符串没找到 转成十六进制也没…
阅读更多...
【算法】二叉树中的dfs

【算法】二叉树中的dfs

快乐的流畅&#xff1a;个人主页 个人专栏&#xff1a;《算法神殿》《数据结构世界》《进击的C》 远方有一堆篝火&#xff0c;在为久候之人燃烧&#xff01; 文章目录 引言一、计算布尔二叉树的值二、求根节点到叶节点数字之和三、二叉树剪枝四、验证搜索二叉树五、二叉搜索树中…
阅读更多...
U盘文件剪切丢失怎么办？揭秘原因并给出恢复方法

U盘文件剪切丢失怎么办？揭秘原因并给出恢复方法

在日常生活和工作中&#xff0c;U盘已成为我们不可或缺的数据存储和传输工具。但有时候&#xff0c;我们在对U盘中的文件进行剪切操作时&#xff0c;会遇到文件丢失的情况。这种突如其来的数据消失往往会让人感到惊慌和困惑。那么&#xff0c;为什么U盘剪切时文件会丢失呢&…
阅读更多...
详解GaussDB(DWS)中的行执行引擎

详解GaussDB(DWS)中的行执行引擎

1.前言 GaussDB&#xff08;DWS&#xff09;包含三大引擎&#xff0c;一是SQL执行引擎&#xff0c;用来解析用户输入的SQL语句&#xff0c;生成执行计划&#xff0c;供执行引擎来执行&#xff1b;二是执行引擎&#xff0c;其中包含了行执行引擎和列执行引擎&#xff0c;执行引擎…
阅读更多...
DataLab-数据分析的Ai辅助工具

DataLab-数据分析的Ai辅助工具

添加图片注释&#xff0c;不超过 140 字&#xff08;可选&#xff09;DataLab是一个由DataCamp提供的强大在线数据分析平台&#xff0c;它通过AI技术简化了数据处理流程&#xff0c;使得用户无需编程或数据分析的高级技能即可快速获取数据洞察。它支持多种数据源&#xff0c;包…
阅读更多...
路由器、交换机和网卡

路由器、交换机和网卡

大家使用VMware安装镜像之后&#xff0c;是不是都会考虑虚拟机的镜像系统怎么连上网的&#xff0c;它的连接方式是什么&#xff0c;它ip是什么&#xff1f; 路由器、交换机和网卡 1.路由器 一般有几个功能&#xff0c;第一个是网关、第二个是扩展有线网络端口、第三个是WiFi功…
阅读更多...
显影不干净如何解决？

显影不干净如何解决？

知识星球&#xff08;星球名&#xff1a;芯片制造与封测社区&#xff0c;星球号&#xff1a;63559049&#xff09;里的学员问&#xff1a;光刻工序完成后&#xff0c;晶圆表面有部分图形容易出现显影不净是什么原因&#xff1f;有什么好的解决办法吗&#xff1f; 光刻工序流程 …
阅读更多...
SQL常用函数

SQL常用函数

一、日期相关函数 1、CURDATE() / CURRENT_DATE 返回当前日期 2、CURRENT_TIME()/CURTIME() 返回当前时间 3、CURRENT_TIMESTAMP 返回当前日期时间 4、DATE()从日期或日期时间表达式中提取日期值 5、DATEDIFF(d1,d2)计算日期 d1->d2 之间相隔的天数 6、DATE_FORMAT按表达式…
阅读更多...
求职网络安全：这个领域的就业机会正在增长

求职网络安全：这个领域的就业机会正在增长

随着大安全时代的到来&#xff0c;网络安全已经从虚拟空间延伸到现实空间。当今网络战愈演愈烈&#xff0c;网络军备赛即将来临。网络空间领域的战争归根到底还是人才的竞争。面对新形势,建立高效的网络安全人才培养体系对中国信息安全产业发展和保证国家安全来讲都至关重要! 目…
阅读更多...
实战中使用 QEMU 进行内网穿透

实战中使用 QEMU 进行内网穿透

前言 阅读 https://xz.aliyun.com/t/14052 《使用 QEMU 进行内网穿透&#xff1f;》 https://securelist.com/network-tunneling-with-qemu/111803/ 《Network tunneling with… QEMU?》 我将此项技术应用到实战中&#xff0c;取得不错的效果&#xff0c;但是也遇到很多坑&am…
阅读更多...
【机器学习】AI时代的核心驱动力

【机器学习】AI时代的核心驱动力

机器学习&#xff1a;AI时代的核心驱动力 一、引言二、机器学习的基本原理与应用三、机器学习算法概览四、代码实例&#xff1a;线性回归的Python实现 一、引言 在数字化浪潮席卷全球的今天&#xff0c;人工智能&#xff08;AI&#xff09;已经不再是科幻小说中的遥远概念&…
阅读更多...
优先队列——大小堆—— priority_queue

优先队列——大小堆—— priority_queue

本人博客主页 本篇博客相关博客 二叉树--讲解 文章目录 目录 文章目录 前言 一、priority_queue是什么&#xff1f; 二、priority_queue的使用 1、相关函数 2、代码使用 3、堆的插入删除 三、模拟实现 1、大框架 2、仿函数 3、向下调整 4、向下调整 总结 前言 在我们学习二叉…
阅读更多...
2024年小程序视频如何下载到电脑上

2024年小程序视频如何下载到电脑上

随着2024年的到来&#xff0c;将小程序视频无缝下载到电脑上&#xff0c;从此让精彩内容触手可及&#xff0c;不受时间和网络的限制&#xff0c;随时随地启发你的生活和工作。 小程序视频我已经打包好了&#xff0c;有需要的自己下载 小程序视频下载工具打包链接&#xff1a;…
阅读更多...
如何理解VMware中的网络模式（NAT、桥接、仅主机）

如何理解VMware中的网络模式（NAT、桥接、仅主机）

目录 Ⅰ.NAT模式 Ⅱ.仅主机模式 Ⅲ.桥接模式 Ⅰ.NAT模式 NAT模式&#xff1a;将物理机的网卡作为虚拟交换机的上线链路&#xff0c;将vmware的私有网络转成可以上网的地址进行网络访问&#xff0c;因此在NAT模式下虚拟机是可以访问外部网络的&#xff08;图一&#xff09; …
阅读更多...
目标检测算法YOLOv8简介

目标检测算法YOLOv8简介

YOLOv8论文尚未发布&#xff0c;YOLOv8由Ultralytics公司推出并维护&#xff0c;源码见&#xff1a;https://github.com/ultralytics/ultralytics &#xff0c;于2024年1月发布v8.1.0版本&#xff0c;最新发布版本为v8.2.0&#xff0c;License为AGPL-3.0。 以下内容主要来自&am…
阅读更多...
最新文章

Copyright @ 2022~2023