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

相关文章

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

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

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

Python+PyQt5实现多屏幕协同播放功能

《Python+PyQt5实现多屏幕协同播放功能》在现代会议展示、数字广告、展览展示等场景中,多屏幕协同播放已成为刚需,下面我们就来看看如何利用Python和PyQt5开发一套功能强大的跨屏播控系统吧... 目录一、项目概述:突破传统播放限制二、核心技术解析2.1 多屏管理机制2.2 播放引擎设计2.3 专

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI