当前位置： 首页 > news >正文

【C++进阶】第3课—二叉搜索树

news 2025/5/12 12:54:40

文章目录

  • 1. 什么是二叉搜索树
  • 2. 二叉搜索树的性能
  • 3. 二叉搜索树的插入
  • 4. 二叉搜索树的查找
  • 5. 二叉搜索树的删除
  • 5. 二叉搜索树key和key/value的应用场景
    • 5.1 key搜索场景
    • 5.2 key/value应用场景

1. 什么是二叉搜索树

  • 二叉搜索树又称为二叉排序树，它可以是一颗空树，也可以是具有以下性质的二叉树：
  • 若它的左子树不为空，那么左子树上所有节点的值都 <= 根节点的值
  • 若它的右子树不为空，那么右子树上所有节点的值都 >= 根节点的值
  • 它的左右子树也分别为二叉搜索树

在这里插入图片描述

  • 二叉搜索树也支持插入相等的值，不过为了避免数据冗余，一般插入不相等的值，特殊的场景下会插入相等的值，根据场景而异。本节主要还是实现插入不等的值

在这里插入图片描述

2. 二叉搜索树的性能

  • 最优情况下，二叉搜索树为完全二叉树(或接近完全二叉树)，对于完全二叉树，若其高度为h，该二叉树的节点数为 n = 2 ^ h - 1,因此也可以推出完全二叉树的深度h = log2(n+1)(2为底，n+1为对数)，这也就说明在完全二叉搜索树中查找某个值的时间复杂度是 O(logN)
  • 最差的情况，二叉搜索树退化为单支树，其高度为 N，因此该类二叉搜索树的时间复杂度为O(N)
  • 综上，二叉搜索树的时间复杂度为O(N)

在这里插入图片描述

  • 显然这样的效率无法满足我们的需求，后续会讲到二叉树变形为平衡二叉搜索树AVL树和红黑树，两边都均衡，尽可能达到完全二叉树这样，时间复杂度就会靠近O(logN)
  • 另外二分查找也可以实现O( log ⁡ 2 N \log_2^N log2N​)的查找效率，但是它有两个缺陷：
  • 它需要存储在支持下标访问的结构中，并且还得是有序的
  • 插入和删除的效率很低，因为要挪动数据

3. 二叉搜索树的插入

  • 插入过程：
  • 如果树为空，则直接新增节点，然后赋值给根root指针
  • 如果树不为空，那么按照二叉搜索树的性质，如果要插入的值val比根节点的值大，则往右走，反之则往左走，找到空位置后，插入新节点
  • 如果支持插入相等的值，插入和当前节点值相同的值可以往右走，也可以往左走，但要保持一致，之后插入相等值时，要符合前面向左/向右走的趋势，然后找到空位置，插入新的节点

在这里插入图片描述

  • 假如现在要插入一个16，我们来分析详细的插入过程

在这里插入图片描述

//二叉搜索树节点
template<class K_Type>
class SearchBinaryTreeNode
{
public:K_Type _key;SearchBinaryTreeNode* _left;SearchBinaryTreeNode* _right;SearchBinaryTreeNode(const K_Type& key):_key(key),_left(nullptr),_right(nullptr){}
};//二叉搜索树
template<class K_Type>
class SearchBinaryTree
{typedef SearchBinaryTreeNode<K_Type> Node;
public://插入数据bool Insert(const K_Type& key){//如果树为空if (_root == nullptr){_root = new Node(key);return true;}//树不为空---双指针查找合适位置Node* parent = nullptr;Node* cur = _root;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}elsereturn false;}//找到空位置cur = new Node(key);//如果插入值比它父节点值大if (key > parent->_key) parent->_right = cur;elseparent->_left = cur;return true;}
private:Node* _root = nullptr;
};

4. 二叉搜索树的查找

  • 从根开始查找，如果比根的值大，那么就往右子树走，比根值小，就往左子树走
  • 最多查找高度次，走到为空还没找到，那么就不存在
  • 如果不支持插入相等的值，找到对应的值即可返回
  • 如果支持插入相等的值，那就意味着存在多个x，一般要查找中序第一个x

在这里插入图片描述

  • 这里只演示插入不相等的值的情况

在这里插入图片描述

5. 二叉搜索树的删除

  • 在讲二叉搜索树的删除操作之前，先来回顾一下二叉树的中序遍历:根左右

在这里插入图片描述

  • 二叉搜索树的删除分为4种情况：
  • 第一种是删除的节点N，它没有左右孩子节点，这种直接将N节点的父节点对应的孩子指针置空，然后delete节点N即可

在这里插入图片描述

  • 第二种是删除的节点N有左孩子节点，没有右孩子节点，这种直接让N节点的父节点的孩子指针指向N节点的左孩子
  • 第三种是删除的节点N有右孩子节点，没有左孩子节点，这种直接让N节点的父节点的孩子指针指向N节点的右孩子
  • 第一种情况也可以划分到这两种情况中

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

  • 第四种最麻烦，是删除的节点N左右孩子都有，那么这种情况就应该找一个节点来替代节点N，然后再删除N节点；这时候找节点N的左孩子中最大值的那个节点或者右孩子中最小值的节点来替代，都满足二叉搜索树

在这里插入图片描述

在这里插入图片描述

  • SearchBinaryTree.h代码
#pragma once
#include <iostream>
using namespace std;//二叉搜索树节点
template<class K_Type>
class SearchBinaryTreeNode
{
public:K_Type _key;SearchBinaryTreeNode* _left;SearchBinaryTreeNode* _right;SearchBinaryTreeNode(const K_Type& key):_key(key),_left(nullptr),_right(nullptr){}
};//二叉搜索树
template<class K_Type>
class SearchBinaryTree
{typedef SearchBinaryTreeNode<K_Type> Node;
public://插入数据bool Insert(const K_Type& key){//如果树为空if (_root == nullptr){_root = new Node(key);return true;}//树不为空---双指针查找合适位置Node* parent = nullptr;Node* cur = _root;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}elsereturn false;}//找到空位置cur = new Node(key);//如果插入值比它父节点值大if (key > parent->_key)parent->_right = cur;elseparent->_left = cur;return true;}//查找数据bool Find(const K_Type& key){if (_root == nullptr)return false;else{Node* cur = _root;while (cur){//如果查找的值比cur节点值大if (key > cur->_key){cur = cur->_right;}//如果查找的值比cur节点值小else if (key < cur->_key){cur = cur->_left;}//找到了elsereturn true;}//走到这，说明没找到return false;}}//中序遍历void Inorder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}//删除数据bool Erase(const K_Type& key){//如果二叉搜索树为空if (_root == nullptr)return false;else{//先找到要删除的节点Node* cur = _root;Node* parent = nullptr;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}//找到了，开始删除else{//若删除的节点N没有左孩子if (cur->_left == nullptr){//如果删除的是根节点if (cur == _root){_root = cur->_right;}//删除的节点非根节点，那么托付给删除节点N的父节点else{//若删除的节点N为其父节点的左孩子if (cur == parent->_left)parent->_left = cur->_right;//若删除的节点N为其父节点的右孩子elseparent->_right = cur->_right;}delete cur; //删除节点}//若删除的节点N没有右孩子else if(cur->_right == nullptr){//如果删除的是根节点if (cur == _root)_root = cur->_left;//删除的节点非根节点，托付给N的父节点else{//若删除的节点N为其父节点的左孩子if (cur == parent->_left)parent->_left = cur->_left;//若删除的节点N为其父节点的右孩子elseparent->_right = cur->_left;}delete cur; //删除节点}//若删除的节点N有左右孩子else{//找右孩子最小节点(最左节点)替代Node* replaceParent = cur;Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}swap(cur->_key, replace->_key);if (replaceParent->_left == replace)replaceParent->_left = replace->_right;elsereplaceParent->_right = replace->_right;delete replace;}return true;}}}return false;}
private:Node* _root = nullptr;
};
  • test.c代码
#include "SearchBinaryTree.h"int main()
{SearchBinaryTree<int> bs1;int arr[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto e : arr){bs1.Insert(e);}//cout << bs1.Find(10) << endl;//cout << bs1.Find(100) << endl;bs1.Inorder();//删除没有左孩子的节点bs1.Erase(1);bs1.Inorder();删除没有右孩子的节点bs1.Erase(14);bs1.Inorder();//删除有左右孩子的节点bs1.Erase(3);bs1.Inorder();//删除根节点bs1.Erase(8);bs1.Inorder();//删除所有节点for (auto e : arr){bs1.Erase(e);bs1.Inorder();}return 0;
}

5. 二叉搜索树key和key/value的应用场景

5.1 key搜索场景

  • 只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景实现的二叉树搜索树支持增删查，但是不支持修改，修改key破坏搜索树结构了
  • 场景1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入
  • 检查⼀篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示

5.2 key/value应用场景

  • 每⼀个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value，增/删/查还是以key为关键字走二叉搜索树的规则进行比较，可以快速查找到key对应的value。key/value的搜索场景实现的⼆叉树搜索树支持修改，但是不支持修改key，修改key破坏搜索树性质了，可以修改value。
  • 场景1：简单中英互译字典，树的结构中(结点)存储key(英文)和vlaue(中文)，搜索时输入英文，则同时查找到了英文对应的中文
  • 场景2：商场无人值守⻋库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，用当前时间-入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场
  • 场景3：统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在这个说明第一次出现，（单词，1），单词存在，则++单词对应的次数

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

  • key、value应用

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

  • 另外还有二叉搜索树的析构函数和拷贝构造函数

在这里插入图片描述

在这里插入图片描述

  • key、value完整代码
//key---value应用
//二叉搜索树节点
template<class K_Type, class V_Type>
class SearchBinaryTreeNode
{
public:K_Type _key;V_Type _value;SearchBinaryTreeNode* _left;SearchBinaryTreeNode* _right;SearchBinaryTreeNode(const K_Type& key, const V_Type& value):_key(key),_value(value), _left(nullptr), _right(nullptr){}
};//二叉搜索树
template<class K_Type, class V_Type>
class SearchBinaryTree
{typedef SearchBinaryTreeNode<K_Type, V_Type> Node;
public://插入数据bool Insert(const K_Type& key,const V_Type& value){//如果树为空if (_root == nullptr){_root = new Node(key, value);return true;}//树不为空---双指针查找合适位置Node* parent = nullptr;Node* cur = _root;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}elsereturn false;}//找到空位置cur = new Node(key, value);//如果插入值比它父节点值大if (key > parent->_key)parent->_right = cur;elseparent->_left = cur;return true;}//查找数据Node* Find(const K_Type& key){if (_root == nullptr)return nullptr;else{Node* cur = _root;while (cur){//如果查找的值比cur节点值大if (key > cur->_key){cur = cur->_right;}//如果查找的值比cur节点值小else if (key < cur->_key){cur = cur->_left;}//找到了elsereturn cur;}//走到这，说明没找到return nullptr;}}//中序遍历void Inorder(){_InOrder(_root);cout << endl;}//删除数据bool Erase(const K_Type& key){//如果二叉搜索树为空if (_root == nullptr)return false;else{//先找到要删除的节点Node* cur = _root;Node* parent = nullptr;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}//找到了，开始删除else{//若删除的节点N没有左孩子if (cur->_left == nullptr){//如果删除的是根节点if (cur == _root){_root = cur->_right;}//删除的节点非根节点，那么托付给删除节点N的父节点else{//若删除的节点N为其父节点的左孩子if (cur == parent->_left)parent->_left = cur->_right;//若删除的节点N为其父节点的右孩子elseparent->_right = cur->_right;}delete cur; //删除节点}//若删除的节点N没有右孩子else if (cur->_right == nullptr){//如果删除的是根节点if (cur == _root)_root = cur->_left;//删除的节点非根节点，托付给N的父节点else{//若删除的节点N为其父节点的左孩子if (cur == parent->_left)parent->_left = cur->_left;//若删除的节点N为其父节点的右孩子elseparent->_right = cur->_left;}delete cur; //删除节点}//若删除的节点N有左右孩子else{//找右孩子最小节点(最左节点)替代Node* replaceParent = cur;Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}swap(cur->_key, replace->_key);swap(cur->_value, replace->_value);if (replaceParent->_left == replace)replaceParent->_left = replace->_right;elsereplaceParent->_right = replace->_right;delete replace;}return true;}}}return false;}SearchBinaryTree() = default;//拷贝构造SearchBinaryTree(const SearchBinaryTree<K_Type, V_Type>& t){_root = Copy(t._root);}//析构函数~SearchBinaryTree(){Destroy(_root);_root = nullptr;}
private:Node* _root = nullptr;//中序遍历调用void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << "->" << root->_value << " ";_InOrder(root->_right);}//拷贝构造调用Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}//析构调用void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}
};
//测试key、value场景1
int main()
{SearchBinaryTree<string, string> dict;dict.Insert("诺基亚", "按键手机");dict.Insert("一加", "OPPO旗下智能手机");dict.Insert("Apple", "苹果手机");dict.Insert("红米", "小米旗下智能手机");//string str;//while (cin >> str)//{//	auto findStr = dict.Find(str);//	if (findStr)//		cout << "->" << findStr->_value << endl;//	else//		cout << "库里无此类型品牌手机" << endl;//}dict.Inorder();dict.Erase("一加");dict.Inorder();dict.Erase("Apple");dict.Inorder();dict.Erase("诺基亚");dict.Inorder();dict.Erase("红米");dict.Inorder();return 0;
}//测试key、value场景2
int main()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };SearchBinaryTree<string, int> countTree;for (const auto& str : arr){// 先查找⽔果在不在搜索树中// 1、不在，说明⽔果第⼀次出现，则插⼊<⽔果, 1>// 2、在，则查找到的结点中⽔果对应的次数++//SearchBinaryTreeNode<string, int>* ret = countTree.Find(str);auto ret = countTree.Find(str);if (ret == NULL)countTree.Insert(str, 1);elseret->_value++;}countTree.Inorder();auto bs(countTree);return 0;
}
http://www.xdnf.cn/news/397207.html

相关文章：

  • C++猴子摘桃 2024年信息素养大赛复赛 C++小学/初中组 算法创意实践挑战赛 真题详细解析
  • [超详细，推荐！！！]前端性能优化策略详解
  • VC++ 获取CPU信息的两种方法
  • POSIX信号量
  • 【软件测试】基于项目驱动的功能测试报告（持续更新）
  • k8s中ingress-nginx介绍
  • Spring Boot 中的重试机制
  • 【Python】Python类型标注革命：Annotated类型深度解析与实战
  • 匈牙利算法
  • 信息系统项目管理师-软考高级（软考高项）​​​​​​​​​​​2025最新（十七）
  • java中对象的比较
  • 【文献阅读】地方政府驱动企业参与乡村振兴的机制——乡村振兴注意力视角的分析
  • 【工作记录】crmeb后端项目打开、运行
  • 【Flask开发踩坑实录】pip 安装报错：“No matching distribution found” 的根本原因及解决方案！
  • 1688 开放平台接口对接实战：商品实时数据采集 API 开发全流程
  • cmake：test project
  • OSPF的特殊区域
  • P10225 [COCI 2023/2024 #3] Milano C.le|普及
  • LeetCode 热题 100 543. 二叉树的直径
  • RS485和RS232 通信配置
  • TikTok 运营干货：内容创作与 AI 增效
  • 【高数上册笔记01】：从集合映射到区间函数
  • istio in action之应用弹性与容错机制
  • Babel 插件与预设的区别及使用
  • 每日脚本 5.11 - 进制转换和ascii字符
  • FlySecAgent：——MCP全自动AI Agent的实战利器
  • 运算放大器稳定性分析
  • MyBatis源码解读4（2.3、MyBatis运行流程）
  • 当虚拟吞噬现实——《GTA6》结合技术
  • 每日算法-250511