C++/数据结构：二叉搜索树的实现与应用

目录

一、二叉搜索树简介

二、二叉搜索树的结构与实现

2.1二叉树的查找与插入

2.2二叉树的删除

2.3二叉搜索树的实现

2.3.1非递归实现

 2.3.2递归实现

三、二叉搜索树的k模型和kv模型

一、二叉搜索树简介

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:。
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
它的左右子树也分别为二叉搜索树。

二、二叉搜索树的结构与实现

2.1二叉树的查找与插入

int a [] = { 8 , 3 , 1 , 10 , 6 , 4 , 7 , 14 , 13 };
1. 二叉搜索树的查找
a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
b、最多查找高度次，走到到空，还没找到，这个值不存在。
2. 二叉搜索树的插入
插入的具体过程如下：
a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

2.2二叉树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情
况：
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程
如下：
情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点
中，再来处理该结点的删除问题--替换法删除。

2.3二叉搜索树的实现

2.3.1非递归实现

//二叉树节点的构建
template<class K>
	struct BSTreeNode
	{
		typedef BSTreeNode<K> Node;

		Node* _left;
		Node* _right;
		K _key;

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



	//class BinarySearchTree
	template<class K>
	class BSTree
	{
		typedef BSTreeNode<K> Node;
	public:
		// 强制生成默认构造
		BSTree() = default;

        //拷贝构造
		BSTree(const BSTree<K>& t)
		{
			_root = Copy(t._root);
		}
        
        //赋值拷贝
		BSTree<K>& operator=(BSTree<K> t)
		{
			swap(_root, t._root);
			return *this;
		}

        //析构函数
		~BSTree()
		{
			Destroy(_root);
		}
        
        
        ///
        //增删查改

        //插入数据
		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;
		}


        //查找数据
		bool 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 true;
				}
			}

			return false;
		}

        //删除数据
		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 (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_right)
							{
								parent->_right = cur->_right;
							}
							else
							{
								parent->_left = cur->_right;
							}
						}

						delete cur;
						return true;
					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (cur == parent->_right)
							{
								parent->_right = cur->_left;
							}
							else
							{
								parent->_left = cur->_left;
							}
						}

						delete cur;
						return true;
					}
					else
					{
						// 替换法
						Node* rightMinParent = cur;
						Node* rightMin = cur->_right;
						while (rightMin->_left)
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_left;
						}

						cur->_key = rightMin->_key;

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

						delete rightMin;
						return true;
					}
				}
			}

			return false;
		}

    private：
    Node* _root;
    };

 2.3.2递归实现

//二叉树节点的构建
template<class K>
	struct BSTreeNode
	{
		typedef BSTreeNode<K> Node;

		Node* _left;
		Node* _right;
		K _key;

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



	//class BinarySearchTree
	template<class K>
	class BSTree
	{
		typedef BSTreeNode<K> Node;
	public:
		// 强制生成默认构造
		BSTree() = default;

        //拷贝构造
		BSTree(const BSTree<K>& t)
		{
			_root = Copy(t._root);
		}
        
        //赋值拷贝
		BSTree<K>& operator=(BSTree<K> t)
		{
			swap(_root, t._root);
			return *this;
		}

        //析构函数
		~BSTree()
		{
			Destroy(_root);
		}
        
        
        ///
        //增删查改
        bool FindR(const K& key)
		{
			return _FindR(_root, key);
		}

		bool InsertR(const K& key)
		{
			return _InsertR(_root, key);
		}

		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}
        void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

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

			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}

		Node* Copy(Node* root)
		{
			if (root == nullptr)
				return nullptr;

			Node* newRoot = new Node(root->_key);
			newRoot->_left = Copy(root->_left);
			newRoot->_right = Copy(root->_right);
			return newRoot;
		}

        //借助引用可以更好的删除和更改数据节点，不需要再额外创建父节点来更改
		bool _EraseR(Node*& root, const K& key)
		{
			if (root == nullptr)
				return false;

			if (root->_key < key)
			{
				return _EraseR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _EraseR(root->_left, key);
			}
			else
			{
				Node* del = root;
				if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else
				{
					Node* rightMin = root->_right;
					while (rightMin->_left)
					{
						rightMin = rightMin->_left;
					}

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

					return _EraseR(root->_right, key);
				}

				delete del;
				return true;
			}
		}

		bool _InsertR(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				root = new Node(key);
				return true;
			}

			if (root->_key < key)
			{
				return _InsertR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _InsertR(root->_left, key);
			}
			else
			{
				return false;
			}
		}

		bool _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
				return false;

			if (root->_key < key)
			{
				return _FindR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _FindR(root->_left, key);
			}
			else
			{
				return true;
			}
		}

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

			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}

    Node* _root;
    };

三、二叉搜索树的k模型和kv模型

1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到
的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
例如：小区停车场，只要可以搜索到车牌号就可以自由进出。
2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方
式在现实生活中非常常见：
比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英
文单词与其对应的中文<word, chinese>就构成一种键值对；
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出
现次数就是<word, count>就构成一种键值对。
例如：商场停车场，进去时记录车牌号，出来时查询是否缴费，如果缴费才可以出去。
改造搜素二叉树为kv结构： 
// 改造二叉搜索树为KV结构
template<class K, class V>
struct BSTNode
 {
 BSTNode(const K& key = K(), const V& value = V())
   : _pLeft(nullptr) , _pRight(nullptr), _key(key), _Value(value)
 {}
 BSTNode<T>* _pLeft;
 BSTNode<T>* _pRight;
 K _key;
    V _value
 };
template<class K, class V>
class BSTree
 {
 typedef BSTNode<K, V> Node;
 typedef Node* PNode;
public:
 BSTree(): _pRoot(nullptr){}
 PNode Find(const K& key);
 bool Insert(const K& key, const V& value)
 bool Erase(const K& key)
private:
 PNode _pRoot;
 };



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

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

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

相关文章

LeetCode刷题记录：（5）前K个高频元素

LeetCode刷题记录：（5）前K个高频元素

LeetCode传送通道 很好的一道题&#xff01; 核心知识点&#xff1a; …①map频率统计&#xff1b; …②优先级队列(不用的话见解法二) //解法一 class Solution {public int[] topKFrequent(int[] nums, int k) {int[] result new int[k];//1.次数统计mapMap<Integer,Inte…
阅读更多...
ElementUI Form：Input 输入框

ElementUI Form：Input 输入框

ElementUI安装与使用指南 Input 输入框 点击下载learnelementuispringboot项目源码 效果图 el-input.vue &#xff08;Input 输入框&#xff09;页面效果图 项目里el-input.vue代码 <script> export default {name: el_input,data() {return {input: ,input1: ,i…
阅读更多...
Mac内存清理的方法，Mac老用户都用这几种方法清理Mac内存

Mac内存清理的方法，Mac老用户都用这几种方法清理Mac内存

Mac磁盘空间又爆满了&#xff1f;系统运行又卡了&#xff1f;你的Mac需要清理内存啦&#xff01;如果你正在为“您的磁盘内存不足”的提示所困扰&#xff0c;或者你的Mac电脑突然运行缓慢和迟缓&#xff0c;那么你可能需要了解以下几种Mac释放内存的方法。 一、清理缓存 在配…
阅读更多...
正点原子--STM32中断系统学习笔记

正点原子--STM32中断系统学习笔记

1、什么是中断&#xff1f; 原子哥给出的概念是这样的&#xff1a;打断CPU正常执行的程序&#xff0c;转而处理紧急程序&#xff0c;然后返回原暂停的程序继续运行&#xff0c;就叫中断。 当发生中断时&#xff0c;当前执行的程序会被暂时中止&#xff0c;进而进入中断处理函…
阅读更多...
YIA主题如何关闭新版本升级提示？WordPress主题怎么取消升级提醒？

YIA主题如何关闭新版本升级提示？WordPress主题怎么取消升级提醒？

前两天YIA主题发布了升级到2.8版本&#xff0c;新增了一些功能&#xff0c;优化调整修复了一些功能&#xff0c;但是这些功能调整幅度不大&#xff0c;加上boke112百科使用的YIA主题已经进行了很多方面的个性化修改&#xff0c;所以就懒得升级了&#xff0c;但是每次进入WordPr…
阅读更多...
C++基础语法学习笔记

C++基础语法学习笔记

C Tutorial 1.基础语法 C 应用&#xff1a;操作系统、图形用户界面和嵌入式系统 C和C区别&#xff1a;C支持类和对象 C语法 #include <iostream> using namespace std;int main(){cout << "hello world!";return 0; }int main () { cout << &q…
阅读更多...
Flutter canvas 画一条会动的波浪线 进度条

Flutter canvas 画一条会动的波浪线 进度条

之前用 Flutter Canvas 画过一个三角三角形&#xff0c;html 的 Canvas 也画过一次类似的&#xff0c; 今天用 Flutter Canvas 试了下 感觉差不多&#xff1a; html 版本 大致效果如下&#xff1a; 思路和 html 实现的类似&#xff1a; 也就是找出点的位置&#xff0c;使用二阶…
阅读更多...
Linux部署DataEase数据分析工具并结合内网穿透实现任意设备远程查看数据

Linux部署DataEase数据分析工具并结合内网穿透实现任意设备远程查看数据

文章目录 前言1. 安装DataEase2. 本地访问测试3. 安装 cpolar内网穿透软件4. 配置DataEase公网访问地址5. 公网远程访问Data Ease6. 固定Data Ease公网地址 前言 DataEase 是开源的数据可视化分析工具&#xff0c;帮助用户快速分析数据并洞察业务趋势&#xff0c;从而实现业务…
阅读更多...
Docker安装MongoDB并做副本集群

Docker安装MongoDB并做副本集群

mongodb cluster 1. 创建外挂目录并授权 mkdir -p /home/mongo1/db /home/mongo1/log mkdir -p /home/mongo2/db /home/mongo2/log mkdir -p /home/mongo3/db /home/mongo3/log chmod 755 2. 拉取最新mongodb docker pull mongo3. 创建副本集结点 docker run -itd --namemong…
阅读更多...
代码随想录算法刷题训练营day21

代码随想录算法刷题训练营day21

代码随想录算法刷题训练营day21&#xff1a;LeetCode(501)二叉搜索树中的众数、LeetCode(530)二叉搜索树的最小绝对差 LeetCode(501)二叉搜索树中的众数 题目 代码 import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map;/*…
阅读更多...
一些大语言模型（LLM）相关的开源项目

一些大语言模型（LLM）相关的开源项目

一些大语言模型&#xff08;LLM&#xff09;相关的开源项目 更多文章访问: https://www.cyisme.top 因为站内限制问题&#xff0c;有些图片无法显示&#xff0c;导致阅读体验较差&#xff0c;可以访问原文&#xff1a;《一些大语言模型&#xff08;LLM&#xff09;相关的开源项…
阅读更多...
Linux逻辑卷（LV）扩容

Linux逻辑卷（LV）扩容

Linux逻辑卷&#xff08;LV&#xff09;扩容 1、准备物理磁盘&#xff08;分区和不分区都行&#xff09;&#xff0c;可以使用lsblk命令查看新增的磁盘&#xff0c;如下图sde就是我们新增磁盘&#xff0c;容量为600G。 2、将新磁盘变成物理卷&#xff08;PV&#xff09; pvcr…
阅读更多...
疾控中心污水采样器的招标参数有哪些

疾控中心污水采样器的招标参数有哪些

技术指标 1 采样程序&#xff1a;可以预先编制 10 种采样程序&#xff0c;一键式启动&#xff1b; 2 采样方式&#xff1a;平行采样、 定时定量采样、定流定量采样、 定时比例采样、液位比例采样、即时定量采样等&#xff1b; 3 采样记录&#xff1a;可保存 10000 条采样记录…
阅读更多...
dockerpipwork相关测试过程

dockerpipwork相关测试过程

pipework可以减轻docker实施过程中的工作量&#xff0c;在网上也找了几篇类似的文章&#xff0c;按照相应配置&#xff0c;结果并不相同 如下测试过程记录下&#xff1a; docker run -it --rm --name c1 busybox docker run -it --rm --name c2 busyboxpipework br1 c1 192…
阅读更多...
Springboot集成Javamelody

Springboot集成Javamelody

JavaMelody的目标是监视QA和生产环境中的Java或Java EE应用服务器。它不是模拟用户请求的工具&#xff0c;而是根据用户对应用程序的使用情况来衡量和计算应用程序实际操作的统计信息的工具。JavaMelody主要基于请求统计和演化图。 它允许改进QA和生产中的应用程序&#xff0c…
阅读更多...
Servlet服务器端的小程序

Servlet服务器端的小程序

Servlet 概述 Servlet applet 运行在服务器端的小程序&#xff0c;Servlet 就是一个接口&#xff0c;定义了 Java 类被浏览器访问到的规则(Tomcat能识别)&#xff0c;我们自定义一个类&#xff0c;实现 Servlet 接口&#xff0c;复写接口中的方法。 访问流程 快速入门 创建…
阅读更多...
Uniapp登录页面获取头像、昵称的最新方法的简单使用

Uniapp登录页面获取头像、昵称的最新方法的简单使用

前言 写小程序写到登录页面的时候&#xff0c;发现官方文档中原来的wx.getUserInfo和wx.getUserProfile不太能用了&#xff0c;学习了相对比较新的方法&#xff0c;这种方法的文档链接如下&#xff1a; https://developers.weixin.qq.com/miniprogram/dev/framework/open-abil…
阅读更多...
搜维尔科技：第九届元宇宙数字人大赛，参赛小组报名确认公告！

搜维尔科技：第九届元宇宙数字人大赛，参赛小组报名确认公告！

各位参赛选手大家好&#xff0c;近期已收到新增报名信息如下表&#xff0c;请各位参赛选手确认&#xff0c;如果信息有误或信息不完整请电话联系赛务组工作人员进行更正 随着元宇宙时代的来临&#xff0c;数字人设计成为了创新前沿领域之一。为了提高大学生元宇宙虚拟人角色策划…
阅读更多...
1.31学习总结

1.31学习总结

1.31 1.线段树 2.Bad Hair Day S&#xff08;单调栈&#xff09; 3.01迷宫(BFS连通块问题剪枝)&#xff08;连通性问题的并查集解法&#xff09; 4.健康的荷斯坦奶牛 Healthy Holsteins&#xff08;DFS&#xff09; 线段树与树状数组 线段树和树状数组的功能相似&#xff0c;但…
阅读更多...
校园二手交易小程序|基于微信小程序的闲置物品交易平台设计与实现(源码+数据库+文档)

校园二手交易小程序|基于微信小程序的闲置物品交易平台设计与实现(源码+数据库+文档)

校园二手交易小程序目录 目录 基于微信小程序的闲置物品交易平台设计与实现 一、前言 二、系统功能设计 三、系统实现 1、用户信息管理 2、商品信息管理 3、公告信息管理 4、论坛信息管理 四、数据库设计 1、实体ER图 五、核心代码 六、论文参考 七、最新计算机毕…
阅读更多...
最新文章

Copyright @ 2022~2023