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

C++数据结构 —— 二叉搜索树

目录

1.二叉搜索树的基本概念

1.1二叉搜索树的基本特征

 2.二叉搜索树的实现

2.1数据的插入(迭代实现)

2.2数据的搜索(迭代实现)

2.3中序遍历(递归实现)

2.4数据的删除(迭代实现)

2.5数据的搜索(递归实现)

2.6数据的插入(递归实现)

2.7数据的删除(递归实现)

2.8类的完善

3.二叉搜索树的应用

4.完整代码

 二叉搜索树

1.二叉搜索树的基本概念

二叉搜索树又称二叉排序树,它可以是一颗空树。二叉搜索树的作用是搜索,排序(二叉搜索树的中序遍历是一组递增有序数据)。

1.1二叉搜索树的基本特征

如果某颗二叉树(包括空树)满足以下性质,可以作为一颗二叉搜索树:

        1.如果左子树不为空,其键值应小于根节点的键值。

        2.如果右子树不为空,其键值应大于根节点的键值。

        3.左右子树都满足上述条件。

没有二叉搜索树之前,常用的查找算法为二分查找。但是二分查找是有局限性的(必须针对有序数组)。二叉搜索树因其特性,例如我们需要查找Key值,只需要与根节点的键值做比较:若Key小于根节点的键值,则往根节点的左子树遍历;若Key值大于根节点的键值,则往根节点的右子树遍历。经计算,查找的次数等于二叉搜索树的深度。正因为如此,二叉搜索树并不是一个优秀的数据结构,因为一但碰到极端情况,二叉搜索树的搜索效率将会大打折扣。所以在往后的章节中,将会使其平衡。

 2.二叉搜索树的实现

 将二叉搜索树定义为一个类,现在将展示类的框架。往后所有的演示代码,都可以直接加入其中:

// 节点
template <class K>
struct BST_node
{BST_node<K>* _left;		//左子树BST_node<K>* _right;	//右子树K _key;BST_node(const K& _key):_key(key),_left(nullptr),_right(nullptr){}
};template <class K>		//节点键值的数据类型
class BST
{typedef BST_node<K> Node;
public:private:Node* _root;	//根节点
};

2.1数据的插入(迭代实现)

bool insert(const K& key)
{if (_root == nullptr){_root = new Node(key);return true;}Node* prev = nullptr;	// cur的父节点Node* cur = _root;while (cur){if (key < cur->_key)	//如果比根节点的键值小{prev = cur;cur = cur->_left;}else if(key > cur->_key)	//如果比根节点的键值大{prev = cur;cur = cur->_right;}else{// 我们不允许插入重复的数据return false;}}// 直到遍历到空,才施行插入cur = new Node(key);if (key < prev->_key){prev->_left = cur;}else if (key > prev->_key){prev->_right = cur;}return true;
}

2.2数据的搜索(迭代实现)

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

2.3中序遍历(递归实现)

void MidTraval()	//此接口作公有
{__MidTraval(_root);cout << endl;
}void __MidTraval(Node* root)	//此接口做私有
{if (root == nullptr){return;}__MidTraval(root->_left);cout << root->_key << " ";__MidTraval(root->_right);
}

2.4数据的删除(迭代实现)

需要注意,要删除二叉搜索树的节点,就必须分两种情况讨论:

        1.要删除节点的左子树或右子树为空。

        2.要删除节点的左、右子树都不为空。

bool erase(const K& key)
{if (_root == nullptr){return false;}Node* prev = _root;Node* cur = _root;while (cur){if (key < cur->_key){prev = cur;cur = cur->_left;}else if (key > cur->_key){prev = cur;cur = cur->_right;}else{// 如果左子树为空if (cur->_left == nullptr){// 假设右子树不为空,则将右子树托孤给父节点if (_root == cur){_root = _root->_right;}else if (prev->_left == cur){prev->_left = cur->_right;}else if (prev->_right == cur){prev->_right = cur->_right;}delete cur;return true;}// 如果右子树为空else if (cur->_right == nullptr){//假设左子树不为空,则将左子树托孤给父节点if (_root == cur){_root = _root->_left;}else if (prev->_left == cur){prev->_left = cur->_left;}else if (prev->_right == cur){prev->_right = cur->_left;}delete cur;return true;}// 如果左右子树都不为空else{// 假设使用右子树的最小值替代Node* prev = _root;Node* minRight = cur->_right;while (minRight->_left)		//二叉树特性,越往左越小{prev = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;// 替换好后,就要删除minRightif (prev->_left == minRight){prev->_left = minRight->_right;}else if (prev->_right == minRight){prev->_right = minRight->_right;}delete minRight;return true;}}}return false;
}

2.5数据的搜索(递归实现)

bool findR(const K& key)
{return __findR(_root, key);
}bool __findR(Node* root, const K& key)	//此接口作私有
{if (root == nullptr){return false;}if (key < root->_key){return __findR(root->_left, key);}else if (key > root->_key){return __findR(root->_right, key);}return true;
}

2.6数据的插入(递归实现)

bool insertR(const K& key)
{return __insertR(_root, key);
}bool __insertR(Node*& root, const K& key)	//此接口作私有
{if (root == nullptr){root = new Node(key);	//注意引用传参,root相当于root->left或root->right的别名return true;}if (key < root->_key){return __insertR(root->_left, key);}else if (key > root->_key){return __insertR(root->_right, key);}return false;
}

2.7数据的删除(递归实现)

bool eraseR(const K& key)
{return __eraseR(_root, key);
}bool __eraseR(Node*& root, const K& key)	//此接口作私有
{if (root == nullptr){return false;}if (key < root->_key){return __eraseR(root->_left, key);}else if (key > root->_key){return __eraseR(root->_right, key);}else{Node* del = root;if (root->_left == nullptr){// 此时root就是要删除的节点,并且是root的父节点的子节点的引用(root == root->_left...)root = root->_right;delete del;return true;}else if (root->_right == nullptr){root = root->_left;delete del;return true;}else{Node* prev = _root;Node* minRight = root->_right;while (minRight->_left)		//二叉树特性,越往左越小{prev = minRight;minRight = minRight->_left;}root->_key = minRight->_key;// 替换好后,就要删除minRightif (prev->_left == minRight){prev->_left = minRight->_right;}else if (prev->_right == minRight){prev->_right = minRight->_right;}delete minRight;return true;}}return false;
}

2.8类的完善

BST():_root(nullptr)
{}~BST()
{Destructor(_root);_root = nullptr;
}void Destructor(Node* root)	//此函数作私有
{if (root == nullptr){return;}// 后序删除Destructor(root->_left);Destructor(root->_right);delete root;
}BST(const BST<K>& t)
{_root = Copy(t._root);
}Node* Copy(Node* root)	//此接口作私有
{if (root == nullptr){return nullptr;}Node* ret = new Node(root->_key);ret->_left = Copy(root->_left);ret->_right = Copy(root->_right);return ret;
}BST<K>& operator==(BST<K> t)	//现代写法
{swap(_root, t._root);return *this;
}

3.二叉搜索树的应用

1.K模型:

        K模型即只有key作为关键码,结构中只需要存储Key即可,关键码即为需要搜索到的值。上面模拟实现的搜索就是K模型。

        例如将英文字典所有的英文单词存储二叉搜索树这个数据结构,那么可将英文单词看作关键码Key,假设我们想查找"hello"这个单词,直接去数据结构找即可。

2.KV模型:

        每一个关键码key,都有与之对应的值Value,即<Key, Value>的键值对。该种方式在现实生活中非常常见。

        例如英汉互译,一个英文单词对应了多个汉语翻译。我们将<英文单词,中文翻译的数组>这样的键值对放入二叉搜索树中。例如查找"hello"这个单词的中文翻译,只需要查找键值对的英文单词即可。

KV模型例题:

给定下面数组,求每种水果出现的次数:

string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };

第一步:先实现二叉搜索树(为了方便,这里只保留插入数据、查找和中序遍历的接口):

namespace KV
{// 节点template <class Key,class Val>struct BST_node{BST_node<Key,Val>* _left;		//左子树BST_node<Key,Val>* _right;	//右子树Key _key;Val _val;BST_node(const Key& key,const Val& val):_key(key), _val(val),_left(nullptr), _right(nullptr){}};template <class Key,class Val>class BST{typedef BST_node<Key,Val> Node;public:bool insert(const Key& key,const Val& val){if (_root == nullptr){_root = new Node(key,val);return true;}Node* prev = nullptr;Node* cur = _root;while (cur){if (key < cur->_key){prev = cur;cur = cur->_left;}else if (key > cur->_key){prev = cur;cur = cur->_right;}else{return false;}}cur = new Node(key,val);if (key < prev->_key){prev->_left = cur;}else if (key > prev->_key){prev->_right = cur;}return true;}Node* find(const Key& key){if (_root == nullptr){return nullptr;}Node* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}else{// 找到了return cur;}}return nullptr;}bool erase(const Key& key){if (_root == nullptr){return false;}Node* prev = _root;Node* cur = _root;while (cur){if (key < cur->_key){prev = cur;cur = cur->_left;}else if (key > cur->_key){prev = cur;cur = cur->_right;}else{if (cur->_left == nullptr){if (_root == cur){_root = _root->_right;}else if (prev->_left == cur){prev->_left = cur->_right;}else if (prev->_right == cur){prev->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){if (_root == cur){_root = _root->_left;}else if (prev->_left == cur){prev->_left = cur->_left;}else if (prev->_right == cur){prev->_right = cur->_left;}delete cur;return true;}else{Node* prev = _root;Node* minRight = cur->_right;while (minRight->_left){prev = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (prev->_left == minRight){prev->_left = minRight->_right;}else if (prev->_right == minRight){prev->_right = minRight->_right;}delete minRight;return true;}}}return false;}void MidTraval()	{__MidTraval(_root);cout << endl;}private:Node* _root = nullptr;void __MidTraval(Node* root){if (root == nullptr){return;}__MidTraval(root->_left);cout << root->_key << ":" << root->_val << endl;__MidTraval(root->_right);}};
}

第二步:算法实现:

void test_count()
{KV::BST<string, int> bt;string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };for (auto& e : arr){KV::BST_node<string, int>* ret = bt.find(e);if (ret)	//不为空,证明数据结构已有{ret->_val++;	//次数++}else{bt.insert(e, 1);}}bt.MidTraval();
}

4.完整代码

 二叉搜索树

相关文章:

C++数据结构 —— 二叉搜索树

目录 1.二叉搜索树的基本概念 1.1二叉搜索树的基本特征 2.二叉搜索树的实现 2.1数据的插入(迭代实现) 2.2数据的搜索(迭代实现) 2.3中序遍历(递归实现) 2.4数据的删除(迭代实现) 2.5数据的搜索(递归实现) 2.6数据的插入(递归实现) 2.7数据的删除(递归实现) 2.8类的完…...

Maven面试题及答案

1、Maven有哪些优点和缺点 优点&#xff1a; 1、简化项目依赖管理 2、方便与持续集成工具(Jenkins)整合 3、有助于多模块项目开发&#xff0c;比如一个模块开发好后发布到仓库&#xff0c;依赖该模块时可以直接从远程仓库更新&#xff0c;不用自己手动去编译 4、有很多插件&am…...

WebRTC系列-Qos系列之接收放RTX处理

文章目录 1. RTX详解1.1 RTX包头解析1.2 RTX包中的OSN2. RTX在WebRTC中处理2.1 组包2.2 解包2.3 发送及接收处理流程2.3.1 发送流程2.3.2 rtx标记的设置流程2.3.3 解析流程2.3.4 RTX解包在上一篇 WebRTC系列-Qos系列之接收NACK文章中分析了接收到nack后解析的主要流程。在WebR…...

国内能否炒伦敦金,2023国际十大正规伦敦金交易平台排名

在目前的投资市场环境中&#xff0c;现货黄金是一种屡见不鲜的投资选择&#xff0c;它依靠国际化的投资环境&#xff0c;成为了世界范围内投资者的重要选择对象。进行现货黄金投资&#xff0c;人们除了要认识市场发展基本现状之外&#xff0c;更要做好基本面和技术面分析工作&a…...

react路由 - react-router-dom

react路由 现代的前端应用大多都是 SPA&#xff08;单页应用程序&#xff09;&#xff0c;也就是只有一个 HTML 页面的应用程序。因为它的用户体验更好、对服务器的压力更小&#xff0c;所以更受欢迎。为了有效的使用单个页面来管理原来多页面的功能&#xff0c;前端路由应运而…...

01-RTOS

对于裸机而言&#xff0c;对于RTOS而言即&#xff1a;对于裸机&#xff0c;打游戏意味着不能回消息 回消息意味着不能打游戏对于RTOS 打游戏和裸机的切换只需要一个时间片节拍 1ms 从宏观来看 就是同时进行的两件事&#xff08;但要在这两件事情的优先级一样的情况下&#xff0…...

信息安全管理

信息安全管理信息安全管理信息安全风险管理信息安全管理体系应急响应与灾难恢复应急响应概况信息系统灾难修复灾难恢复相关技术信息安全管理 管理概念&#xff1a;组织、协调、控制的活动&#xff0c;核心过程的管理控制 管理对象和组成&#xff1a;包括人员在内相关资产&…...

深度学习tips

1、datasets_make函数中最后全部转化为numpy形式 datanp.array(data)否则会出现问题&#xff0c;比如数据是103216&#xff0c;经过trainloader生成tensor后&#xff08;batch_size为30&#xff09;&#xff0c;发现生成的数据为&#xff1a; data.shape #(10,) data[0].shape…...

2023-2-13 刷题情况

替换子串得到平衡字符串 题目描述 有一个只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符&#xff0c;且长度为 n 的字符串。 假如在该字符串中&#xff0c;这四个字符都恰好出现 n/4 次&#xff0c;那么它就是一个「平衡字符串」。 给你一个这样的字符串 s&#xff0c;请通过…...

[HSCSEC 2023] rev,pwn,crypto,Ancient-MISC部分

比赛后有讲解&#xff0c;没赶上&#xff0c;前20比赛完1小时提交WP&#xff0c;谁会大半夜的起来写WP。总的感觉pwn,crypto过于简单&#xff0c;rev有2个难的不会&#xff0c;其它不是我的方向都感觉过于难&#xff0c;一个都没作。revDECOMPILEONEOONE入门题&#xff0c;一个…...

SpringBoot 接入 Spark

本文主要介绍 SpringBoot 与 Spark 如何对接&#xff0c;具体使用可以参考文章 SpringBoot 使用 Spark pom 文件添加 maven 依赖 spark-core&#xff1a;spark 的核心库&#xff0c;如&#xff1a;SparkConfspark-sql&#xff1a;spark 的 sql 库&#xff0c;如&#xff1a;s…...

在线支付系列【23】支付宝开放平台产品介绍

有道无术&#xff0c;术尚可求&#xff0c;有术无道&#xff0c;止于术。 文章目录前言支付产品App 支付手机网站支付电脑网站支付新当面资金授权当面付营销产品营销活动送红包会员产品App 支付宝登录人脸认证信用产品芝麻 GO芝麻先享芝麻免押芝麻工作证安全产品交易安全防护其…...

Python绝对路径和相对路径详解

在介绍绝对路径和相对路径之前&#xff0c;先要了解一下什么是当前工作目录。什么是当前工作目录每个运行在计算机上的程序&#xff0c;都有一个“当前工作目录”&#xff08;或 cwd&#xff09;。所有没有从根文件夹开始的文件名或路径&#xff0c;都假定在当前工作目录下。注…...

基于多进程的并发编程

一&#xff1a;不同平台基于多进程并发编程的实现 1.Windows平台 参考博文&#xff1a;Windows 编程&#xff08;多进程&#xff09; 更多API: 1&#xff09;waitForSingleObject&#xff1a;等待一个内核对象变为已通知状态 2&#xff09;GetExitCodeProcess&#xff1a;获取…...

Flask入门(4):CBV和FBV

目录4.CBV和FBV4.1 继承 views.View4.2 继承 views.MethodView4.CBV和FBV 前面的例子中&#xff0c;都是基于视图函数构建视图&#xff08;FBV&#xff09;&#xff0c;和Django一样&#xff0c;Flask也有基于类构建视图&#xff08;CBV&#xff09;的方法。这种方式用的不多&…...

Qt OpenGL(三十九)——Qt OpenGL 核心模式-在雷达坐标系中绘制飞行的飞机

提示:本系列文章的索引目录在下面文章的链接里(点击下面可以跳转查看): Qt OpenGL 核心模式版本文章目录 Qt OpenGL(三十九)——Qt OpenGL 核心模式-在雷达坐标系中绘制飞行的飞机 一、场景 在之前绘制完毕雷达显示图之后,这时候,我们能匹配的场景就更广泛了,比如说…...

系统应用 odex 转 dex

说下为什会有这个需求&#xff0c;以某系统应用为例&#xff0c;我们通过 adb 获取到的 apk 反编译查看只有少部分代码和资源&#xff0c;关键代码看不到。 经过一系列操作&#xff0c;把 odex 转换为 dex 可以看到源码。 工具下载 Smali 下载 1、使用 adb shell pm list pa…...

【GPLT 三阶题目集】L3-013 非常弹的球

刚上高一的森森为了学好物理&#xff0c;买了一个“非常弹”的球。虽然说是非常弹的球&#xff0c;其实也就是一般的弹力球而已。森森玩了一会儿弹力球后突然想到&#xff0c;假如他在地上用力弹球&#xff0c;球最远能弹到多远去呢&#xff1f;他不太会&#xff0c;你能帮他解…...

vue项目第三天

论坛项目动态路由菜单以及渲染用户登录全局前置拦截器获取用户的菜单以及接口执行过程解析菜单数据&#xff0c;渲染伟动态路由。菜单数据将数据源解析为类似路由配置对象的格式&#xff08;./xxx/xxx 这种格式&#xff09;。下方是路由实例的代码,后面封装了很多方法这里也需要…...

【渝偲医药】实验室关于核磁共振波谱NMR的知识(原理、用途、分析、问题)

核磁共振波谱法&#xff08;Nuclear Magnetic Resonance&#xff0c;简写为NMR&#xff09;与紫外吸收光谱、红外吸收光谱、质谱被人们称为“四谱"&#xff0c;是对各种有机和无机物的成分、结构进行定性分析的强有力的工具之一&#xff0c;亦可进行定量分析。 核磁共振&…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

ubuntu22.04有线网络无法连接,图标也没了

今天突然无法有线网络无法连接任何设备&#xff0c;并且图标都没了 错误案例 往上一顿搜索&#xff0c;试了很多博客都不行&#xff0c;比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动&#xff0c;重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...

6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础

第三周 Day 3 &#x1f3af; 今日目标 理解类&#xff08;class&#xff09;和对象&#xff08;object&#xff09;的关系学会定义类的属性、方法和构造函数&#xff08;init&#xff09;掌握对象的创建与使用初识封装、继承和多态的基本概念&#xff08;预告&#xff09; &a…...

数据库——redis

一、Redis 介绍 1. 概述 Redis&#xff08;Remote Dictionary Server&#xff09;是一个开源的、高性能的内存键值数据库系统&#xff0c;具有以下核心特点&#xff1a; 内存存储架构&#xff1a;数据主要存储在内存中&#xff0c;提供微秒级的读写响应 多数据结构支持&…...

【1】跨越技术栈鸿沟:字节跳动开源TRAE AI编程IDE的实战体验

2024年初&#xff0c;人工智能编程工具领域发生了一次静默的变革。当字节跳动宣布退出其TRAE项目&#xff08;一款融合大型语言模型能力的云端AI编程IDE&#xff09;时&#xff0c;技术社区曾短暂叹息。然而这一退场并非终点——通过开源社区的接力&#xff0c;TRAE在WayToAGI等…...

基于Java项目的Karate API测试

Karate 实现了可以只编写Feature 文件进行测试,但是对于熟悉Java语言的开发或是测试人员,可以通过编程方式集成 Karate 丰富的自动化和数据断言功能。 本篇快速介绍在Java Maven项目中编写和运行测试的示例。 创建Maven项目 最简单的创建项目的方式就是创建一个目录,里面…...