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

2024-09-04 23:04
文章标签 c++ 实现 数据结构 笔记 搜索 模型 二叉 17 kv

本文主要是介绍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。

相关文章

大模型研发全揭秘：客服工单数据标注的完整攻略

大模型研发全揭秘：客服工单数据标注的完整攻略

在人工智能（AI）领域，数据标注是模型训练过程中至关重要的一步。无论你是新手还是有经验的从业者，掌握数据标注的技术细节和常见问题的解决方案都能为你的AI项目增添不少价值。在电信运营商的客服系统中，工单数据是客户问题和解决方案的重要记录。通过对这些工单数据进行有效标注，不仅能够帮助提升客服自动化系统的智能化水平，还能优化客户服务流程，提高客户满意度。本文将详细介绍如何在电信运营商客服工单的背景下进行
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
hdu1240、hdu1253（三维搜索题）

hdu1240、hdu1253（三维搜索题）

1、从后往前输入，（x，y，z）; 2、从下往上输入，（y , z, x）; 3、从左往右输入，（z，x，y）； hdu1240代码如下： #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
Andrej Karpathy最新采访：认知核心模型10亿参数就够了，AI会打破教育不公的僵局

Andrej Karpathy最新采访：认知核心模型10亿参数就够了，AI会打破教育不公的僵局

夕小瑶科技说 原创  作者 | 海野 AI圈子的红人，AI大神Andrej Karpathy，曾是OpenAI联合创始人之一，特斯拉AI总监。上一次的动态是官宣创办一家名为 Eureka Labs 的人工智能+教育公司 ，宣布将长期致力于AI原生教育。 近日，Andrej Karpathy接受了No Priors（投资博客）的采访，与硅谷知名投资人 Sara Guo 和 Elad G
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2