C++——二叉搜索树的实现

1、二叉搜索树的概念

二叉搜索树又叫做二叉排序树，他或者是一棵空树，或者具有以下性质：

若他的左子树不为空，则左子树的所有节点的值都小于根节点的值，

若他的右子树不为空，则右子树的所有节点的值都大于根节点的值，

他的左右子树也分别为二叉搜索树；

2、二叉搜索树的操作

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

1.二叉搜索树的查找

从根节点开始找，比根大往右边查找，比根小往左边查找，最多查找高度次，走到空还没找到，则该值不存在；

2.二叉搜索树的插入

若树为空，则新增节点，赋值给root指针，

若树不为空，按二叉搜索树查找插入位置，插入新节点

 3.二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回，如果存在，则分为以下四种情况：

a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
其实a情况可以和b c 情况合并起来，这样我们只需要考虑三种删除方式：
情况b: 删除该节点，并使该节点的父亲节点指向删除节点的左节点
情况c:删除该节点，并使该节点的父亲节点指向删除节点的右节点
情况d:替换法，找到该节点右子树的最小节点或者左子树的最大节点，与该节点替换，然后删除右子树的最小节点或左子树的最大节点；

4.二叉搜索树的实现

#pragma once

#include<iostream>
#include<string>
using namespace std;
namespace key
{
	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;
	public:
		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
				{
					cout << "true" << endl;
					return true;
				}
			}
			cout << "false" << endl;
			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 (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right=cur->_right;
							}
						}
						delete cur;
					}
					//右为空，父亲指向我的左
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_left == cur)
							{
								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 << " ";
			_InOrder(root->_right);
		}


		Node* _root = nullptr;
	};
	void TestBSTree1()
	{
		BSTree<int> b;
		b.Insert(1);
		b.Insert(2);
		b.Insert(3);
		b.Insert(4);
		b.Insert(5);
		b.Find(6);
		b.Find(3);
		b.Find(5);
		b.InOrder();

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

		/*t1.InOrder();
		t1.Erase(8);
		t1.InOrder();*/


		for (auto e : a)
		{
			t1.Erase(e);
			t1.InOrder();
		}
	}
}

namespace key_value
{
	template<class K,class V>
	struct BSTreeNode
	{
		BSTreeNode<K,V>* _left;
		BSTreeNode<K,V>* _right;
		K _key;
		V _value;
		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:
		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 (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}
						delete cur;
					}
					//右为空，父亲指向我的左
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_left == cur)
							{
								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 << " ";
			_InOrder(root->_right);
		}


		Node* _root = nullptr;
	};

	void TestBSTree3()
	{
		BSTree<string, string> dict;
		dict.Insert("string", "字符串");
		dict.Insert("left", "左边");
		dict.Insert("insert", "插入");

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

	void TestBSTree4()
	{
		// 统计次数
		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();
	}

}

5、二叉搜索树的应用

1.K模型：K模型只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值；

比如：给一个单词word，判断该单词是否拼写正确，

2.K-V模型：每一个关键码都对应一个Value，即<Key,value>的键值对，

比如：英汉字典中用英文与中文的对应关系，通过英文可以快速找到对应的中文，

6、二叉搜索树的性能分析

对于有n个节点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是高度次，但对于同一个关键码集合，如果插入的次序不同，可能得到不同结构的二叉树：

 

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：O(logN)
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为O(N);

 

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

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

相关文章

论文翻译：Rethinking Interpretability in the Era of Large Language Models

论文翻译：Rethinking Interpretability in the Era of Large Language Models

https://arxiv.org/abs/2402.01761 在大型语言模型时代的可解释性再思考 摘要 在过去十年中&#xff0c;随着越来越大的数据集和深度神经网络的兴起&#xff0c;可解释机器学习领域的兴趣迅速增长。同时&#xff0c;大型语言模型&#xff08;LLMs&#xff09;在广泛的任务中…
阅读更多...
JavaScript 中 await 永远不会 resolve 的 Promise 会导致内存泄露吗？

JavaScript 中 await 永远不会 resolve 的 Promise 会导致内存泄露吗？

前言 在 JavaScript 中&#xff0c;await 关键字用于等待一个 Promise 完成&#xff0c;它只能在异步函数&#xff08;async function&#xff09;内部使用。当 await 一个永远不会 resolve 的 Promise 时&#xff0c;它确实会阻塞异步函数的进一步执行&#xff0c;但不会直接…
阅读更多...
数据结构和算法（0-1）----递归

数据结构和算法（0-1）----递归

定义​ 递归是一种在程序设计中常用的技术&#xff0c;它允许一个函数调用自身来解决问题。递归通常用于解决那些可以被分解为相似的子问题的问题&#xff0c;这些问题的解决方式具有自相似性。在数据结构和算法中&#xff0c;递归是一种重要的解决问题的方法&#xff0c;尤其是…
阅读更多...
从实时监控到风险智能预警：EasyCVR视频AI智能监控技术在工业制造中的应用

从实时监控到风险智能预警：EasyCVR视频AI智能监控技术在工业制造中的应用

随着科技的不断进步和工业制造领域的持续发展&#xff0c;传统的生产管理方式正逐渐转型&#xff0c;迈向更加智能、高效和安全的新阶段。在这个变革过程中&#xff0c;视频智能监控技术凭借其独特的优势&#xff0c;成为工业制造领域的管理新引擎&#xff0c;推动着从“制造”…
阅读更多...
前端直连小票打印机，前端静默打印，js静默打印解决方案

前端直连小票打印机，前端静默打印，js静默打印解决方案

最近公司开发了一个vue3收银系统&#xff0c;需要使用小票打印机打印小票&#xff0c;但是又不想结账的时候弹出打印预览&#xff0c;找了很多方案&#xff0c;解决不了js打印弹出的打印预览窗口&#xff01; 没办法&#xff0c;自己写了一个winform版本的静默打印软件&#xf…
阅读更多...
我的智能辅助大师-办公小浣熊

我的智能辅助大师-办公小浣熊

一、基本介绍 随着2022年ChatGPT为代表的AI工具对互联网领域进行第一次冲击后&#xff0c;作为一名对编程领域涉足不算特别深的一名程序员&#xff0c;对AI大模型的接触也真的不能算少了&#xff0c;这是时代的必然趋势。在此之前也曾接触过很多的AI工具&#xff0c;他们都能在…
阅读更多...
神经网络以及简单的神经网络模型实现

神经网络以及简单的神经网络模型实现

神经网络基本概念&#xff1a; 神经元&#xff08;Neuron&#xff09;&#xff1a; 神经网络的基本单元&#xff0c;接收输入&#xff0c;应用权重并通过激活函数生成输出。 层&#xff08;Layer&#xff09;&#xff1a; 神经网络由多层神经元组成。常见的层包括输入层、隐藏层…
阅读更多...
React18+Redux+antd 项目实战 JS

React18+Redux+antd 项目实战 JS

React18Reduxantd 项目实战 js Ant Design插件官网 Axios官网 (可配置请求拦截器和响应拦截器) JavaScript官网 Echarts官网 一、项目前期准备 1.创建新项目 hotel-manager npx create-react-app hotel-manager2.安装依赖 //安装路由 npm i react-router-domnpm i aixos /…
阅读更多...
manim学习笔记04：使用manim，表示向量和加法。

manim学习笔记04：使用manim，表示向量和加法。

manim学习笔记04&#xff1a;使用manim&#xff0c;表示向量和加法。 一&#xff0c;相关定义 1.有向线段&#xff1a; 规定若线段 AB的端点为起点为A&#xff0c;B为终点&#xff0c;则线段就具有了从起点 A到终点 B的方向和长度。具有方向和长度的线段叫做有向线段。 接下…
阅读更多...
练习9.5 彩票分析

练习9.5 彩票分析

练习 9.14&#xff1a;彩票 创建⼀个列表或元素&#xff0c;其中包含 10 个数和 5 个字 ⺟。从这个列表或元组中随机选择 4 个数或字⺟&#xff0c;并打印⼀条消息&#xff0c; 指出只要彩票上是这 4 个数或字⺟&#xff0c;就中⼤奖了。 练习 9.15&#xff1a;彩票分析 可以使…
阅读更多...
【Qt 基础】绘图

【Qt 基础】绘图

画笔 QPen pen; pen.setWidth(3); // 线条宽度 pen.setColor(Qt::red);// 画笔颜色 pen.setStyle(Qt::DashLine);// 线条样式 pen.setCapStyle(Qt::RoundCap);// 线端样式 pen.setJoinStyle(Qt::BevelJoin);// 连接样式 painter.setPen(pen);线条 线端 连接 画刷 QBrush bru…
阅读更多...
​前端Vue自定义签到获取积分弹框组件设计与实现

​前端Vue自定义签到获取积分弹框组件设计与实现

摘要 随着前端技术的不断演进&#xff0c;开发的复杂性日益凸显。传统的整体式开发方式在面临功能迭代和修改时&#xff0c;常常牵一发而动全身&#xff0c;导致开发效率低下和维护成本高昂。组件化开发作为一种解决方案&#xff0c;通过实现模块的独立开发和维护&#xff0c;…
阅读更多...
【零基础】学JS之APIS第四天

【零基础】学JS之APIS第四天

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 非常期待和您一起在这个小…
阅读更多...
（补充）：java各种进制、原码、反码、补码和文本、图像、音频在计算机中的存储方式

（补充）：java各种进制、原码、反码、补码和文本、图像、音频在计算机中的存储方式

文章目录 前言一、进制1 逢几进一2 常见进制在java中的表示3 进制中的转换（1）任意进制转十进制（2）十进制转其他进制二、计算机中的存储1 计算机的存储规则(文本数据)（1）ASCII码表（2）编码规则的发展演化2 计算机的存储规则(图片数据)（1）分辨率、像素（2）黑白图与灰度…
阅读更多...
澳门建筑插画：成都亚恒丰创教育科技有限公司

澳门建筑插画：成都亚恒丰创教育科技有限公司

澳门建筑插画&#xff1a;绘就东方之珠的斑斓画卷 在浩瀚的中华大地上&#xff0c;澳门以其独特的地理位置和丰富的历史文化&#xff0c;如同一颗璀璨的明珠镶嵌在南国海疆。这座城市&#xff0c;不仅是东西方文化交融的典范&#xff0c;更是建筑艺术的宝库。当画笔轻触纸面&a…
阅读更多...
装饰模式(大话设计模式)C/C++版本

装饰模式(大话设计模式)C/C++版本

装饰模式 需求分析&#xff1a; 1. 选择服饰 > 服饰类 2. 输出结果 对象是人 > 人类将Person类中一大堆服饰功能抽象出服饰类&#xff0c;然后通过Person类聚合服饰属性&#xff0c;通过Set行为来设置服饰属性&#xff0c;最后达到灵活打扮的效果 装饰模式 动态地给一个…
阅读更多...
【Java--数据结构】栈：不仅仅是数据存储，它是编程的艺术

【Java--数据结构】栈：不仅仅是数据存储，它是编程的艺术

欢迎关注个人主页&#xff1a;逸狼 创造不易&#xff0c;可以点点赞吗~ 如有错误&#xff0c;欢迎指出~ 目录 栈 栈的方法介绍 入栈push 出栈pop和 瞄一眼peek 判空isEmpty和判满isFull 模拟实现栈 push入栈 pop出栈和peek 测试 使用泛型实现栈 测试 使用链表实现栈&#xff08…
阅读更多...
【leetcode】整数反转

【leetcode】整数反转

给你一个 32 位的有符号整数 x &#xff0c;返回将 x 中的数字部分反转后的结果。 如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] &#xff0c;就返回 0。 假设环境不允许存储 64 位整数&#xff08;有符号或无符号&#xff09;。 示例 1&#xff1a; …
阅读更多...
运动控制问题

运动控制问题

第一类运动控制问题是指被控制对象的空间位置或轨迹运动发生改变的运动控制系统的控制问题。这类运动控制问题在理论上完全遵循牛顿力学定律和运动学原则。 1、运动控制问题 第1类运动控制的核心是研究被控对象的运动轨迹 、分析运动路径、运动速度、加速度与时间的关系，常用…
阅读更多...
【香菇带你学Linux】Linux环境下gcc编译安装【建议收藏】

【香菇带你学Linux】Linux环境下gcc编译安装【建议收藏】

文章目录 0. 前言1. 安装前准备工作1.1 创建weihu用户1.2 安装依赖包1.2.1 安装 GMP1.2.2 安装MPFR1.2.3 安装MPC 2. gcc10.0.1版本安装3. 报错解决3. 1. wget下载报错 4. 参考文档 0. 前言 gcc&#xff08;GNU Compiler Collection&#xff09;是GNU项目的一部分&#xff0c;…
阅读更多...
最新文章

Copyright @ 2022~2023