33.C++二叉树进阶1（二叉搜索树两种模型及其应用）

ops/2025/3/6 6:11:15/

⭐上篇文章：32.C++二叉树进阶1（二叉搜索树）-CSDN博客

⭐本篇代码：c++学习/18.二叉树进阶-二叉搜索树 · 橘子真甜/c++-learning-of-yzc - 码云 - 开源中国 (gitee.com)

⭐标⭐是比较重要的部分

        在上篇文章中，实现了一个简单的二叉搜索树，包括插入数据，删除数据，查找数据，搜索二叉树的中序遍历。

        上篇文章中的二叉搜索树代码，其实就是key模型。

key 模型。每一个节点都只存储一个值。

key - value模型。每一个节点除了存储key以外，还存储一个value值

在key-value模型中，通过对应的key来获取它的value。key值一般用于插入，查找，删除，遍历的时候的比较。

目录

 

一. 二叉搜索树的key模型

二. 二叉搜索树的key - value 模型 

2.1 二叉搜索树节点

2.2 二叉搜索树类

2.3 查找

2.4 插入 

2.5 删除 

2.6 中序遍历 

 三. 二叉搜索树的应用与效率分析  

3.1 查找单词

3.2 统计次数

3.3 二叉搜索树的效率分析以及如何改进 

一. 二叉搜索树的key模型

内容可以见上篇文章：32.C++二叉树进阶1（二叉搜索树）-CSDN博客

代码如下：

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;//模板的声明和定义要放在一起
template <class K>
struct BSTreeNode	//Binary Search Tree Node
{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;//需要定义构造函数BSTreeNode(const K& k):_left(nullptr),_right(nullptr),_key(k){}
};template <class K>
class BSTree	//Binary Search Tree
{typedef BSTreeNode<K> Node;
private:Node* _root = nullptr;public://插入bool Insert(const K& key)//使用bool做返回值的目的是二叉搜索树是不允许有冗余的!{if (_root == nullptr){_root = new Node(key);return true;//成功插入}Node* cur = _root;//局部变量Node* parent = cur;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;//有一个一摸一样的值，返回false}}cur = new Node(key);//还没有将这个新的节点和其父亲链接起来if (parent->_key > key)//当前值比父亲小，在其左边parent->_left = cur;elseparent->_right = cur;return true;}//查找bool find(const K& key){Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return true;}}//出循环还没返回true，说明该树没有所查找的数据，返回falsereturn false;}//删除(最难的)bool Erase(const K& key){//1.没有孩子直接删除即可//2.有一个孩子的让其父亲指向其孩子，然后将其删除即可//3.有两个孩子的最麻烦，需要使用替换删除法//需要找到一个节点来替换这个节点！//可以找到左子树的最大节点，右子树的最小节点都能够替代Node* cur = _root;Node* parent = cur;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{//找到了,可以删除if (cur->_left == nullptr)//错误，留坑1{//左为空if (cur == _root)//当要删除的节点为根节点时，需要特判{_root = cur->_right;}else{if (cur == parent->_right){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;}else if (cur->_right == nullptr)//错误，留坑1{//右为空//同理，当删除节点为根节点时，需要特判if (cur == _root){_root = cur->_left;}else{if (cur == parent->_right){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}delete cur;}else{//找到左子树最大，或者右子树最小来替换我，然后删除//这里采用右子树的最小进行删除Node* rightMin = cur->_right;Node* rightMinParent = cur;//一直向左寻找即可while (rightMin->_left){rightMinParent = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;//然后将rightMin删除即可//要注意如果，rightMin没有左孩子（即righMin为要删除节点的右孩子）//此时只要让当前节点指向rightMin的右孩子即可if (rightMin == cur->_right)//错误，留坑2{cur->_right = rightMin->_right;}else{rightMinParent->_left = rightMin->_right;}delete rightMin;}return true;}}//找不到，返回falsereturn false;}//修改？，key模型搜索树是不能修改的！//key-value模型搜索树可以修改value//！！key不可修改//中序遍历void InOrder(){_InOrder(_root);cout << endl;}//前序遍历void PreOrder(){_PreOrder(_root);cout << endl;}void PostOrder(){_PostOrder(_root);cout << endl;}
private:void _PreOrder(Node* root){if (root == nullptr)return;cout << root->_key << " ";_PreOrder(root->_left);_PreOrder(root->_right);}	void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}void _PostOrder(Node* root){if (root == nullptr)return;_PostOrder(root->_left);_PostOrder(root->_right);cout << root->_key << " ";}
};

key模型中，我们不能修改任意的一个节点的值。

二. 二叉搜索树的key - value 模型 

        key-value模型中，我们可以修改对应的value值。

2.1 二叉搜索树节点

        对于节点来说，需要再模板中增加一个V值，然后再结构体中新增一个_value

//模板的声明和定义要放在一起
template <class K, class V>
struct BSTreeNode	//Binary Search Tree Node
{BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;K _key;V _value;//需要定义构造函数BSTreeNode(const K& k, const V& v):_left(nullptr), _right(nullptr), _key(k),_value(v){}
};

2.2 二叉搜索树类

         同理要更新模板和节点


template <class K,class V>
class BSTree	//Binary Search Tree
{typedef BSTreeNode<K, V> Node;
private:Node* _root = nullptr;
};

2.3 查找

        对于查找来说，不再是返回true/false 而是返回这个节点的指针，若二叉搜索树中没有该节点返回nullptr即可

	//查找Node* find(const K& key){Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return Node;}}return nullptr;}

2.4 插入 

        这里的插入，是在函数内部构造节点，所有要新增一个value参数。如果参数的已经创建好的节点，则不需要改变。

	//插入bool Insert(const K& key, const V& value)//使用bool做返回值的目的是二叉搜索树是不允许有冗余的!{if (_root == nullptr){_root = new Node(key, value);return true;//成功插入}Node* cur = _root;//局部变量Node* parent = cur;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;//有一个一摸一样的值，返回false}}cur = new Node(key, value);//还没有将这个新的节点和其父亲链接起来if (parent->_key > key)//当前值比父亲小，在其左边parent->_left = cur;elseparent->_right = cur;return true;}

2.5 删除 

        由于我们不需要构造节点，所以这里的删除和key模型是一样的。

bool Erase(const K& key){//1.没有孩子直接删除即可//2.有一个孩子的让其父亲指向其孩子，然后将其删除即可//3.有两个孩子的最麻烦，需要使用替换删除法//需要找到一个节点来替换这个节点！//可以找到左子树的最大节点，右子树的最小节点都能够替代Node* cur = _root;Node* parent = cur;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{//找到了,可以删除if (cur->_left == nullptr)//错误，留坑1{//左为空if (cur == _root)//当要删除的节点为根节点时，需要特判{_root = cur->_right;}else{if (cur == parent->_right){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;}else if (cur->_right == nullptr)//错误，留坑1{//右为空//同理，当删除节点为根节点时，需要特判if (cur == _root){_root = cur->_left;}else{if (cur == parent->_right){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}delete cur;}else{//找到左子树最大，或者右子树最小来替换我，然后删除//这里采用右子树的最小进行删除Node* rightMin = cur->_right;Node* rightMinParent = cur;//一直向左寻找即可while (rightMin->_left){rightMinParent = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;//然后将rightMin删除即可//要注意如果，rightMin没有左孩子（即righMin为要删除节点的右孩子）//此时只要让当前节点指向rightMin的右孩子即可if (rightMin == cur->_right)//错误，留坑2{cur->_right = rightMin->_right;}else{rightMinParent->_left = rightMin->_right;}delete rightMin;}return true;}}//找不到，返回falsereturn false;}

2.6 中序遍历 

        中序遍历除了打印key值，还需要打印对应的value

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);}

 三. 二叉搜索树的应用与效率分析  

3.1 查找单词

#define _CRT_SECURE_NO_WARNINGS 1
#include "test.h"
#include <iostream>
#include <vector>
using namespace std;//1.查找单词
void test1()
{BSTree<string, string> dict;dict.Insert("string", "字符串");dict.Insert("print", "打印");dict.Insert("sort", "排序");dict.Insert("apple", "苹果");dict.Insert("world", "世界");dict.Insert("tree", "树");while (1){cout << "请输入你需要查找的单词:";string word; cin >> word;BSTreeNode<string, string>* node = dict.find(word);if (node){cout << "中文为:" << node->_value << endl;}elsecout << "单词错误，或者该单词不在该字典中" << endl;}}int main()
{test1();return 0;
}

运行结果如下：

可以看到，成功的查找到了加载的单词

3.2 统计次数

        如果将key值定义为需要统计的类型，value值定义为int。这样就能够统计次数

//统计次数
void test2()
{string s = "1234asdjh@#$#@%ns$#^%**&(*__+daigo`123~+_)(*&^%$#@!{}|: < > ? , / .;p[]\ vughw4895WEFyWERuoei328750`4u3;[. / .za`~!@#$";BSTree<char, int> counttree;for (int i = 0; i < s.size(); i++){BSTreeNode<char, int>* node = counttree.find(s[i]);if (node == nullptr)counttree.Insert(s[i], 1);elsenode->_value++;}counttree.InOrder();
}int main()
{//test1();test2();return 0;
}

运行结果如下：

3.3 二叉搜索树的效率分析以及如何改进 

        根据二叉树的性质，如果一颗二叉树为满二叉树，那么其搜索效率为O(logN)，因为此时根据大小判断可以直接去除一半的节点。

        但是在极端的情况下，二叉搜索树可能会退化为链表(比如插入的数据是有序的时候)，此时效率为O(N)。

想要解决这个问题需要使用平衡二叉搜索树，常见的平衡二叉搜索树有：

1 AVL树

2 红黑树


http://www.ppmy.cn/ops/163518.html

相关文章

紧跟 Web3 热潮，RuleOS 如何成为行业新宠？

紧跟 Web3 热潮，RuleOS 如何成为行业新宠？

Web3 热潮正以汹涌之势席卷全球。从金融领域的创新应用到供应链管理的变革&#xff0c;从社交媒体的去中心化尝试到游戏产业的全新玩法探索&#xff0c;Web3 凭借其去中心化、安全性和用户赋权等特性&#xff0c;为各个行业带来了前所未有的机遇。在这股热潮中&#xff0c;Rule…
阅读更多...
Kylin麒麟操作系统服务部署 | NFS服务部署

Kylin麒麟操作系统服务部署 | NFS服务部署

以下所使用的环境为&#xff1a; 虚拟化软件&#xff1a;VMware Workstation 17 Pro 麒麟系统版本&#xff1a;Kylin-Server-V10-SP3-2403-Release-20240426-x86_64 一、 NFS服务概述 NFS&#xff08;Network File System&#xff09;&#xff0c;即网络文件系统。是一种使用于…
阅读更多...
一篇文章讲解清楚ARM9芯片启动流程

一篇文章讲解清楚ARM9芯片启动流程

SAM9X60 ARM9 boot启动流程关键词介绍&#xff1a; 第一级bootloader - 也叫boot ROM&#xff0c;是集成在MPU内部的ROM里面 它的主要功能是执行对MPU的基本初始化和配置&#xff0c;查找并将第二级bootloader从外部NVM中读取出来并放到MPU内部的SRAM. 可以让MPU强制停留在第一…
阅读更多...
计算机网络基础：服务器远程连接管理（Telnet命令）

计算机网络基础：服务器远程连接管理（Telnet命令）

目录 1. 服务器远程管理 2. 图形化连接 3. Telnet 连接 4. 查看端口 1. 服务器远程管理 两种远程管理&#xff1a;图形化、命令行 远程的条件&#xff1a; 1. 能ping 通 2. 服务器开了远程服务 3. 拥有远程管理权限&#xff08;组&#xff09;的用户 2. 图形化连接 图形化…
阅读更多...
基于java SSM springboot学生信息管理系统设计和实现

基于java SSM springboot学生信息管理系统设计和实现

基于java SSM springboot学生信息管理系统设计和实现 &#x1f345; 作者主页 网顺技术团队 &#x1f345; 欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; &#x1f345; 文末获取源码联系方式 &#x1f4dd; &#x1f345; 查看下方微信号获取联系方式 承接各种定制系统 …
阅读更多...
Tomcat原理：HTTP协议与HTTPS协议

Tomcat原理：HTTP协议与HTTPS协议

一、URL统一资源定位符 在介绍HTTP协议与HTTPS协议之前&#xff0c;我们首先要了解统一资源定位符URL&#xff0c;用来表示从互联网上得到的资源位置和访问这些资源的方法。 &#xff08;一&#xff09;表示方法 URL分为以下几个部分&#xff1a;协议://主机地址:端口号//文件…
阅读更多...
MetaGPT发布的MGX与Devin深度对比

MetaGPT发布的MGX与Devin深度对比

家人们&#xff0c;搞编程的都知道&#xff0c;工具选对了&#xff0c;效率能翻倍&#xff01;今天必须给大伙唠唠MetaGPT发布的MGX编程助手和Devin编程助手 。 先看MGX&#xff0c;简直是编程界的王炸&#xff01;它就像一个超神的虚拟开发团队&#xff0c;一堆智能助手分工明…
阅读更多...
在Qt中使用QFont设置字体样式

在Qt中使用QFont设置字体样式

在Qt中使用QFont设置字体样式的步骤如下&#xff1a; 1. 创建QFont对象 QFont font;2. 设置字体属性 字体家族&#xff1a;使用setFamily()方法&#xff0c;建议提供备选字体。 font.setFamily("Arial, sans-serif"); // 备选通用字体字体大小&#xff1a; 点大小&…
阅读更多...
最新文章

Copyright @ 2022~2023