C++的二叉搜索树

目录

基本概念

二叉搜索树的实现 

插入结点

查找结点

删除结点

删除结点左为空

删除结点右为空

基于特殊情况的优化

删除结点左右不为空

基于特殊情况的优化

完整代码 

二叉搜索树的实际应用

K和KV模型

改造二叉搜索树为为KV模型

基本概念

1、二叉搜索树又称二叉排序树

2、左子树上的所有值均小于根节点，右子树上的所有值均大于根节点

3、一个结点的左右子树均为二叉搜索树

二叉搜索树的实现 

插入结点

bool Insert(const T& 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;//成功插入返回true
}

查找结点

bool Find(const T& key)
{
	Node* cur = root;//从头结点开始查找
	while (cur)
	{
		if (cur->key< key)
		{
			cur = cur->right;
		}
		else if (cur->key> key)
		{
			cur = cur->left;
		}
		else
		{
			return true;//遍历找到了cur->key== key就返回true
		}
	}
	return false;//没找到就返回false
}

删除结点

删除结点左为空

//删除结点的左节点为空
if (cur->left == nullptr)
{
	if(cur == parent->left)
	{
		parent->left = cur->right;
	}
	else
	{
		parent->right = cur->left;
	}
	delete cur;
}

删除结点右为空

//删除结点的右节点为空
else if (cur->right == nullptr)
{
	if (cur == parent->left)
	{
		parent->left = cur->left;
	}
	else
	{
		parent->right = cur->left;
	}
	delete cur;
}

基于特殊情况的优化

//删除结点的左节点为空
if (cur->left == nullptr)
{
	//删除结点是根节点
	if (cur == root)
	{
		root = cur->right;
	}
	else
	{
		if(cur == parent->left)
		{
			parent->left = cur->right;
		}
		else
		{
			parent->right = cur->left;
		}
	}
	delete cur;
}

//删除结点的右节点为空
else if (cur->right == 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 = null;//记录交换结点的父亲结点
	Node* rightMin = cur->right;//记录交换节点

	//遍历寻找删除结点的右子树的最左结点
	while (rightMin->left)
	{
		rightMinParent = rightMin;
		rightMin = rightMin->left;
	}
				
	swap(cur->key, rightMin->key);
	rightMinParent->left = rightMin->right;//防止交换结点点还有右子树（交换结点不可能有左子树，
    //因为交换结点就是删除结点的右子树的最左结点，如果它还有左子树那么最左结点就不是它）
	delete rightMin;//rightMin负责找到交换结点，找到并交换后它没用了可以直接删除
}

基于特殊情况的优化

//删除结点的左右结点均不为空
else
{
	//查找右子树的最左结点替代删除
	Node* rightMinParent = cur;//如果要删除的是根节点，（即使不删除根节点，一旦进入循环则parent也会直接发生变化）
	Node* rightMin = cur->right;//记录交换节点
	//遍历寻找
	while (rightMin->left)
	{
		rightMinParent = rightMin;
		rightMin = rightMin->left;
	}
				
	swap(cur->value, rightMin->key);
    //rightMin是parent的左，就令parent的左指向rightMin的右
	if (rightMinParent->left == rightMin)//不删除根节点时都会满足该条件
		rightMinParent->left = rightMin->right;
    //rightMin是parent的右，就令parent的左指向rightMin的右
	else
		rightMinParent->right = rightMin->right;//处理删除根节点的特殊情况
	delete rightMin;
}

完整代码 

#pragma once
#include <iostream>
using namespace std;

template<class T>
struct  BSTreeNode
{
	BSTreeNode<T>* left;
	BSTreeNode<T>* right;
	T value;

	BSTreeNode(const T& key)
		:left(nullptr)
		,right(nullptr)
		,value(key)
	{}
};


template<class T>
class  BSTree
{
	typedef BSTreeNode<T> Node;
public:
bool Insert(const T& 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;//成功插入返回true
}

bool Find(const T& 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 T& key)
{
	Node* parent = nullptr;
	Node* cur = root;
	while (cur)
	{
		if (cur->key< key)
		{
			cur = cur->right;
		}
		else if (cur->key> key)
		{
			cur = cur->left;
		}
		//遍历寻找到要删除的值
		else
		{
			//删除结点的左节点为空
			if (cur->left == nullptr)
			{
				//删除结点是根节点
				if (cur == root)
				{
					root = cur->right;
				}
				else
				{
					if(cur == parent->left)
					{
					parent->left = cur->right;
					}
					else
					{
						parent->right = cur->left;
					}
				}
				delete cur;
			}

			//删除结点的右节点为空
			else if (cur->right == 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;
}

public:
	//套一层（友元、套一层、get三种方式获取类内的数据）
	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 test()
{
	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();
}

  • 时间复杂度：O（n）或 O（logn）
  • O（n）

  • O（logn）

二叉搜索树的实际应用

K和KV模型

K模型：只有key作为关键码，结构中只需存储key即可，key就是要搜索的值（以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误）

KV模型：每一个关键码key都有与之对应的值value，即<key,value>键值对（英汉词典中的中英文之间的对应关系<word,chinese>，通过中文可以快速找到对应的中文，统计单词的出现次数，统计成功后，给定某一个单词就能快速找到其出现的次数<word,count>）

查找的方式：

  • 二分查找
  • 二叉树搜索查找 -> AVL树和红黑树
  • 哈希查找
  • 跳表查找
  • 多叉搜索树查找：B树系列

改造二叉搜索树为为KV模型

//KV模型
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;//成功插入返回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)
		{
			cur = cur->right;
		}
		else if (cur->key > key)
		{
			cur = cur->left;
		}
		//遍历寻找到要删除的值
		else
		{
			//删除结点的左节点为空
			if (cur->left == nullptr)
			{
				//删除结点是根节点
				if (cur == root)
				{
					root = cur->right;
				}
				else
				{
					if (cur == parent->left)
					{
						parent->left = cur->right;
					}
					else
					{
						parent->right = cur->left;
					}
				}
				delete cur;
			}

			//删除结点的右节点为空
			else if (cur->right == 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;
}

public:
	//套一层（友元、套一层、get三种方式获取类内的数据）
	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;
};

	void test()
	{
		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);//Find函数的返回值变为了结点的指针
			if (ret)
			{
				cout << ret->_value << endl;
			}
			else
			{
				cout << "无此单词，请重新输入" << endl;
			}
		}
	}

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

~over~

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

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

相关文章

科技云报道：走入商业化拐点，大模型“开箱即用”或突破行业困局

科技云报道：走入商业化拐点，大模型“开箱即用”或突破行业困局

科技云报道原创。 大模型加速狂飙&#xff0c;AI商业化却陷入重重困境。 一方面&#xff0c;传统企业不知道怎么将AI融入原始业务&#xff0c;另一方面&#xff0c;AI企业难以找到合适的商业化路径。 纵观海外AI玩家&#xff0c;已经有许多企业趟出了自己的商业化道路。 微…
阅读更多...
Linux系统安全与应用【一】

Linux系统安全与应用【一】

目录 1.账号安全控制 1.1 系统账号清理 1.2 密码安全控制 1.3 命令历史限制 1.4 命令总结 2.系统引导和登录控制 2.1 使用su命令切换用户 2.2 限制使用su命令的用户 3.可插拔式认证模块PAM 3.1 linux中的PAM安全认证 3.2 PAM认证原理​编辑 3.3 PAM认证的构成 3.4 P…
阅读更多...
项目管理中常用的三个工具：甘特图、看板、燃尽图

项目管理中常用的三个工具：甘特图、看板、燃尽图

在日常项目管理的实践中&#xff0c;为了更有效地追踪项目进度、优化资源配置和提高团队协作效率&#xff0c;管理者常常会借助一些工具来辅助工作。这些工具的本质在于将抽象复杂的项目管理任务具象化、简单化&#xff0c;以更直观、方便的方式呈现出来。 以下介绍项目管理中…
阅读更多...
基于Springboot的在线动漫信息平台

基于Springboot的在线动漫信息平台

基于SpringbootVue的在线动漫信息平台的设计与实现 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringbootMybatis工具&#xff1a;IDEA、Maven、Navicat 系统展示 用户登录 首页 热门动漫 文章专栏 会员分享 论坛信息 动漫资讯 后台登录 动漫分类管…
阅读更多...
在Spring Boot应用中实现阿里云短信功能的整合

在Spring Boot应用中实现阿里云短信功能的整合

1.程序员必备程序网站 天梦星服务平台 (tmxkj.top)https://tmxkj.top/#/ 2.导入坐标 <dependency><groupId>com.aliyun</groupId><artifactId>aliyun-java-sdk-core</artifactId><version>4.5.0</version></dependency><…
阅读更多...
SpringCloud之Feign集成Ribbon

SpringCloud之Feign集成Ribbon

Feign定义【可跳过】 Spring Cloud Feign是一个声明式的伪Http客户端&#xff0c;它使得写Http客户端变得更简单。其英文表意为“假装&#xff0c;伪装&#xff0c;变形”&#xff0c;是一个http请求调用的轻量级框架&#xff0c;可以以Java接口注解的方式调用Http请求&#x…
阅读更多...
[Rust开发]在Rust中使用geos的空间索引编码实例

[Rust开发]在Rust中使用geos的空间索引编码实例

geos的空间索引用的是STRTree&#xff0c;这是一种基于STR算法的四叉树索引&#xff0c;有如下特点&#xff1a; 使用Sort-Tile-Recursive (STR) 算法创建的仅查询的R-tree空间索引 STR(Sort-Tile-Recursive,递归网格排序) 基本思想是将所有的矩形以“tile”的方式分配到r/n&a…
阅读更多...
netsh int ipv4 show dynamicport tcp动态端口port设置

netsh int ipv4 show dynamicport tcp动态端口port设置

netsh int ipv4 show dynamicport tcp netsh int ipv4 set dynamicport tcp start4000 num10000
阅读更多...
STM32_舵机的实战

STM32_舵机的实战

一、配置相应的管脚 二、写代码
阅读更多...
linux+ndk把jni制作成so库供apk使用(带线程的回调)

linux+ndk把jni制作成so库供apk使用(带线程的回调)

我们就不墨迹了,直接开始,往往我们需要jni给我们回调一些数据,并且是实时的回调,这里我们就需要多写一些东西了 1.先在安卓里面设置好接口以及回调,我自己给你们看源代码 package com.example.myndkapplicationimport android.os.Bundle import android.util.Log import androi…
阅读更多...
基于Python实现心脏病数据可视化DEA+预测【500010103.1】

基于Python实现心脏病数据可视化DEA+预测【500010103.1】

一、数据说明 该心脏病数据集是通过组合 5 个已经独立可用但以前未合并的流行心脏病数据集来策划的。在这个数据集中&#xff0c;5 个心脏数据集结合了 11 个共同特征&#xff0c;使其成为迄今为止可用于研究目的的最大心脏病数据集。 该数据集由 1190 个实例和 11 个特征组成…
阅读更多...
wstunnel (websocket模式ssh)

wstunnel (websocket模式ssh)

接上一篇 修改客户端运行参数 ssh -o ProxyCommand"./wstunnel client -L stdio://%h:%p ws://192.168.254.131:8080" 127.0.0.1 其中127.0.0.1为服务端的本地ssh访问&#xff0c;可以修改为通过服务端访问其他设备的ssh服务。例如&#xff1a; ssh -o ProxyComma…
阅读更多...
线性代数-行列式-p1 矩阵的秩

线性代数-行列式-p1 矩阵的秩

目录 1.定义 2. 计算矩阵的秩 3. 矩阵的秩性质 1.定义 2. 计算矩阵的秩 3. 矩阵的秩性质
阅读更多...
JavaEE——spring MVC请求处理

JavaEE——spring MVC请求处理

目录 主要目的&#xff1a; 1. Spring web 项目搭建 2. 添加依赖 3. 配置插件 4. 配置设置类 5. 编写controller层类 6. 编写测试的http请求 主要目的&#xff1a; 创建一个spring web项目&#xff1b; 创建控制类&#xff1b; 掌握如何配置MVC&#xff1b; 编写htt…
阅读更多...
HTTP 网络协议的请求头信息，响应头信息，具体详解（2024-04-26）

HTTP 网络协议的请求头信息，响应头信息，具体详解（2024-04-26）

1、通用头部 2、常见的 HTTP请求头信息 HTTP 响应头信息是服务器在响应客户端的HTTP请求时发送的一系列头字段&#xff0c;它们提供了关于响应的附加信息和服务器的指令。 3、常见的 HTTP 响应头信息 响应头向客户端提供一些额外信息&#xff0c;比如谁在发送响应、响应者的功…
阅读更多...
AI预测福彩3D第9套算法实战化测试第3弹2024年4月25日第3次测试

AI预测福彩3D第9套算法实战化测试第3弹2024年4月25日第3次测试

今天继续进行新算法的测试&#xff0c;今天是第3次测试。好了&#xff0c;废话不多说了&#xff0c;直接上图上结果。 2024年4月25日福彩3D预测结果 6码定位方案如下&#xff1a; 百位&#xff1a;6、4、3、7、2、8 十位&#xff1a;8、4、9、3、1、0 个位&#xff1a;7、6、9、…
阅读更多...
审稿快、出版效率高的8本检验医学中文期刊推荐！

审稿快、出版效率高的8本检验医学中文期刊推荐！

常笑医学整理了8本比较好投的检验医学中文期刊&#xff0c;以及期刊详细参数&#xff0c;供大家在论文投稿时参考。这些检验医学期刊&#xff0c;审稿快、出版效率高&#xff0c;有需要的赶紧收藏&#xff01; 1.《中华检验医学杂志》 &#xff08;详细投稿信息请点击刊物名称…
阅读更多...
【网站项目】考研助手

【网站项目】考研助手

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…
阅读更多...
uniapp-css:拼图（不规则图片拼插）、碎片

uniapp-css:拼图（不规则图片拼插）、碎片

拼图案例样式 高斯模糊的地方可以对应的使用fliter属性和opacity来调节样式。 其余碎片和图片对应： 这段代码实现了一个拼图效果的Vue组件。以下是对代码的详细解析： 模板部分： 在模板中使用v-for指令遍历imgs数组中的每个图片对象，为每个图片创建一个元素。 使用:cla…
阅读更多...
Day 31 贪心算法理论基础 455.分发饼干 376. 摆动序列 53. 最大子序和

Day 31 贪心算法理论基础 455.分发饼干 376. 摆动序列 53. 最大子序和

贪心算法理论基础 ​ 贪心算法的本质&#xff1a;选择每一个阶段的局部最优&#xff0c;从而达到系统的整体最优&#xff1b; ​ 贪心的套路就是没有套路&#xff0c;最好的策略就是举反例&#xff0c;因为大多数时候并不要求严格证明&#xff0c;只需要得到普遍性结论即可&a…
阅读更多...
最新文章

Copyright @ 2022~2023