C++笔记17•数据结构:二叉搜索树(K模型/KV模型实现)•

2024-09-04 23:04

本文主要是介绍C++笔记17•数据结构:二叉搜索树(K模型/KV模型实现)•,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

二叉搜索树

1.二叉搜索树

1. 二叉搜索树的查找
a 、从根开始比较,查找,比根大则往右边走查找,比根小则往左边走查找。
b 、最多查找高度次,走到到空,还没找到,这个值不存在。
2. 二叉搜索树的插入
插入的具体过程如下:
a. 树为空,则直接新增节点,赋值给 root 指针
b. 树不空,按二叉搜索树性质查找插入位置,插入新节点
3.二叉搜索树的删除
首先查找元素是否在二叉搜索树中,如果不存在,则返回 , 否则要删除的结点可能分下面四种情 况:
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有 4 中情况,实际情况 a 可以与情况 b 或者 c 合并起来,因此真正的删除过程如下:
情况 b :删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点 -- 直接删除
情况 c :删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点 -- 直接删除
情况 d:在它的右子树中寻找中序下的第一个结点( 也就是删除节点的左子树中最大的值或者删除节点的右子树中最小的值 ),用它的值填补到被删除节点 中,再来处理该结点的删除问题 -- 替换法删除

删除9、16、3、10节点

其中:节点9和16可以直接删除。3、10节点需要用替换法删除

节点3:需要用2节点或7节点来替换

节点10:需要用9节点或12节点来替换

 2.二叉搜索树-K模型

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;//二叉搜索树BinarySearchTree
//struct BinarySearchTreeNodetemplate<class K>
struct BSTreeNode
{BSTreeNode<K>* _left;//一定不要写成BSTreeNode*<K>  _left;  这样编译器无法识别BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}
};template<class K>
class BSTree
{typedef struct 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;}}//准备从parent插入Node* node = new Node(key);if (parent->_key > key)//插左子树{parent->_left = node;}else//插右子树{parent->_right = node;}//cur = new Node(key);//if (parent->_key > key)//插左子树//{//	parent->_left = cur;//}//else//插右子树//{//	parent->_right = cur;//}return true;}void _Inorder(Node* root){if (root == nullptr){return;}_Inorder(root->_left);cout << root->_key << " ";_Inorder(root->_right);}void Inorder(){_Inorder(_root);cout << endl;}void find(const K& key){Node* cur = _root;while (cur){if (cur->_key == key){cout << "找到了!" << endl;return;}else if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}}cout << "找不到!" << endl;return;}bool erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else   //找到了开始删除  1.左为空  2.右为空  3.左右都不为空{if (cur->_left == nullptr) //1.左为空{if (cur == _root) //判断删除的节点是否是根节点 根的左为空 让根的右成为根就可以了 _root = cur->_right{_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else     //parent->_right == cur{parent->_right = cur->_right;}}delete cur;                   //不要忘记手动释放节点}else if (cur->_right == nullptr)//2.右为空{if (cur == _root)//判断删除的节点是否是根节点 根的右为空 让根的左成为根就可以了 _root = cur->_left{_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else   //parent->_right == cur{parent->_right = cur->_left;}}delete cur;}else   //3.左右都不为空 用删除节点的左子树中最大的值或者删除节点的右子树中最小的值  此处用删除节点的左子树最大值{//Node* Lbignode_pre = nullptr;//不能置空 后面如果直接跳出循环Lbignode_pre还是空,会出bug;Lbignode_pre->_right  空指针不能这样访问Node* Lbignode_pre = cur;Node* Lbignode = cur->_left;while (Lbignode->_right){Lbignode_pre = Lbignode;Lbignode = Lbignode->_right;}cur->_key = Lbignode->_key;//替换节点中的值,删除cur转换为删除Lbignodeif (Lbignode == Lbignode_pre->_right){Lbignode_pre->_right = Lbignode->_left;}else{Lbignode_pre->_left = Lbignode->_left;}delete Lbignode;}return true;}}return false;}private:Node* _root = nullptr;
};void test1()
{BSTree<int> bt;bt.insert(1);bt.insert(10);bt.insert(2);bt.insert(5);bt.insert(4);bt.insert(6);bt.insert(8);bt.insert(9);bt.insert(7);bt.insert(3);bt.insert(0);bt.insert(0);bt.Inorder();bt.find(8);bt.find(20);bt.erase(20);bt.erase(0);bt.erase(10);bt.erase(8);bt.Inorder();}
void test2()
{char arr[] = { 10,9,8,7,6,5,4,3,2,1,0 };BSTree<int> bt;for (auto e : arr){bt.insert(e);}cout << "插入:" << endl;bt.Inorder();cout << "依次删除:" << endl;for (auto e : arr){bt.erase(e);bt.Inorder();}
}
int main()
{//test1();test2();return 0;}

 3.二叉搜索树-KV模型

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
using namespace std;//二叉搜索树BinarySearchTree
//struct BinarySearchTreeNodetemplate<class K,class V>
struct BSTreeNode
{BSTreeNode<K,V>* _left;//一定不要写成BSTreeNode*<K>  _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 struct 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;}}//准备从parent插入Node* node = new Node(key, value);if (parent->_key > key)//插左子树{parent->_left = node;}else//插右子树{parent->_right = node;}//cur = new Node(key, value);//if (parent->_key > key)//插左子树//{//	parent->_left = cur;//}//else//插右子树//{//	parent->_right = cur;//}return true;}void _Inorder(Node* root){if (root == nullptr){return;}_Inorder(root->_left);cout << root->_key << ":"<<root->_value << endl;_Inorder(root->_right);}void Inorder(){_Inorder(_root);cout << endl;}Node* find(const K& key){Node* cur = _root;while (cur){if (cur->_key == key){//cout << "找到了!" << endl;return cur;}else if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}}//cout << "找不到!" << endl;return nullptr;}bool erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else   //找到了开始删除  1.左为空  2.右为空  3.左右都不为空{if (cur->_left == nullptr) //1.左为空{if (cur == _root) //判断删除的节点是否是根节点 根的左为空 让根的右成为根就可以了 _root = cur->_right{_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else     //parent->_right == cur{parent->_right = cur->_right;}}delete cur;                   //不要忘记手动释放节点}else if (cur->_right == nullptr)//2.右为空{if (cur == _root)//判断删除的节点是否是根节点 根的右为空 让根的左成为根就可以了 _root = cur->_left{_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else   //parent->_right == cur{parent->_right = cur->_left;}}delete cur;}else   //3.左右都不为空 用删除节点的左子树中最大的值或者删除节点的右子树中最小的值  此处用删除节点的左子树最大值{//Node* Lbignode_pre = nullptr;不能置空 后面如果直接跳出循环Lbignode_pre还是空,会出bug;Lbignode_pre->_right  空指针不能这样访问Node* Lbignode_pre = cur;Node* Lbignode = cur->_left;while (Lbignode->_right){Lbignode_pre = Lbignode;Lbignode = Lbignode->_right;}cur->_key = Lbignode->_key;//替换节点中的值,删除cur转换为删除Lbignodeif (Lbignode == Lbignode_pre->_right){Lbignode_pre->_right = Lbignode->_left;}else{Lbignode_pre->_left = Lbignode->_left;}delete Lbignode;}return true;}}return false;}private:Node* _root = nullptr;
};void test1()
{BSTree<string,string> Dictionary;Dictionary.insert("apple", "苹果");Dictionary.insert("pear", "梨");Dictionary.insert("left", "左");Dictionary.insert("right", "右");string str;while (cin >> str){BSTreeNode<string, string>* ret = Dictionary.find(str);if(ret)cout << ret->_value << endl;elsecout << "词典没有此单词!" << endl;}}
void test2()
{string arr[] = { "徐香猕猴桃","葡萄", "梨", "哈密瓜", "西瓜", "苹果", "橙子", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉"};BSTree<string, int> countfruit;BSTreeNode<string, int>* ret =nullptr;for (auto e : arr){//BSTreeNode<string, int>* ret =countfruit.find(e);ret = countfruit.find(e);if (ret == nullptr)countfruit.insert(e, 1);elseret->_value++;}delete ret;//这里可能会有双重释放节点 ret属于树节点 应在树中析构函数中进行节点的释放的管理,这里一般不需要自己手动释放,自己释放可能会遇到内存泄漏countfruit.Inorder();delete ret;
}
int main()
{//test1();test2();return 0;}

这篇关于C++笔记17•数据结构:二叉搜索树(K模型/KV模型实现)•的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1137284

相关文章

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

MySQL双主搭建+keepalived高可用的实现

《MySQL双主搭建+keepalived高可用的实现》本文主要介绍了MySQL双主搭建+keepalived高可用的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录一、测试环境准备二、主从搭建1.创建复制用户2.创建复制关系3.开启复制,确认复制是否成功4.同

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》:本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义