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

相关文章

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl

C# foreach 循环中获取索引的实现方式

《C#foreach循环中获取索引的实现方式》:本文主要介绍C#foreach循环中获取索引的实现方式,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、手动维护索引变量二、LINQ Select + 元组解构三、扩展方法封装索引四、使用 for 循环替代

Spring Security+JWT如何实现前后端分离权限控制

《SpringSecurity+JWT如何实现前后端分离权限控制》本篇将手把手教你用SpringSecurity+JWT搭建一套完整的登录认证与权限控制体系,具有很好的参考价值,希望对大家... 目录Spring Security+JWT实现前后端分离权限控制实战一、为什么要用 JWT?二、JWT 基本结构

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Android实现两台手机屏幕共享和远程控制功能

《Android实现两台手机屏幕共享和远程控制功能》在远程协助、在线教学、技术支持等多种场景下,实时获得另一部移动设备的屏幕画面,并对其进行操作,具有极高的应用价值,本项目旨在实现两台Android手... 目录一、项目概述二、相关知识2.1 MediaProjection API2.2 Socket 网络

使用Python实现图像LBP特征提取的操作方法

《使用Python实现图像LBP特征提取的操作方法》LBP特征叫做局部二值模式,常用于纹理特征提取,并在纹理分类中具有较强的区分能力,本文给大家介绍了如何使用Python实现图像LBP特征提取的操作方... 目录一、LBP特征介绍二、LBP特征描述三、一些改进版本的LBP1.圆形LBP算子2.旋转不变的LB

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

C# Where 泛型约束的实现

《C#Where泛型约束的实现》本文主要介绍了C#Where泛型约束的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录使用的对象约束分类where T : structwhere T : classwhere T : ne

将Java程序打包成EXE文件的实现方式

《将Java程序打包成EXE文件的实现方式》:本文主要介绍将Java程序打包成EXE文件的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录如何将Java程序编程打包成EXE文件1.准备Java程序2.生成JAR包3.选择并安装打包工具4.配置Launch4