二叉树进阶之二叉搜索树：一切的根源

前言：

在学完了简单的容器与C++面向对象的三大特性之后，我们首先接触的就是map与set两大容器，但是这两个容器底层实现的原理是什么呢？我们不而知，今天，主要来为学习map与set的底层原理而打好基础，而二叉搜索树，则是一切的开端......

一、二叉搜索树的定义与性质

1.1、什么是二叉搜索树：

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
1、若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2、若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3、它的左右子树也分别为二叉搜索树

1.2、二叉搜索树的性质：

  • 节点值关系: 对于每个节点 N，其左子树中所有节点的值都小于 N，右子树中所有节点的值都大于 N。
  • 中序遍历的顺序: 对二叉搜索树进行中序遍历（左-根-右）时，节点的值按升序排列。
  • 平均时间复杂度: 在平均情况下，查找、插入和删除操作的时间复杂度都是 O(log n)。
  • 最坏时间复杂度: 在最坏情况下（树退化为链表），查找、插入和删除操作的时间复杂度是 O(n)。

二、二叉搜索树的模拟实现

初步了解性质之后，我们就根据这些特点与所学二叉树的知识模拟实现一个简单的二叉搜索树结构。首先我们创建一个头文件，取名为BSTree.h

1、节点结构

结点是组成一个二叉树的基础，我们要写一个二叉树，首先就是定义好一个的节点结构，由于是二叉树，所以一个结点会有两个子节点，我们分别以right与left表示左右子节点。随后就是值了，我们用val来表示（注意：一般来说会有key与key-val两种模型，分别象征之后的set与map两种容器，我们这里先以简单的key模型为例子）。

template<class T>
struct BSTNode
{BSTNode(const T&data=T()):_val(data),left(nullptr),right(nullptr){}BSTNode<T>* right;BSTNode<T>* left;T _val;
};

再这样一串代码中，我们先定义一个结点结构，用之前学的模板知识将结点改造为一个模板。对与结点的默认构造，我们选择调用所存储数据类型的默认结构在初始化列表中给val值进行初始化，并且，给左右子节点的指针全部指向空。（data值直接调用的T这个数据类型自己的默认构造：包括内置类型与自定义类型）

2、二叉树的创建

随后，我们就在继续创建一个BSTree结构体模板，为了方便，先将结点进行重命名，随后将必要的构造函数，参数写上。一个BSTree参数只需要一个根节点就行。构造函数也只需要对根节点指针指向空就行。

template<class T>
class BSTree
{typedef BSTNode<T> Node;
public:BSTree():_root(nullptr){}private:Node* _root;
};

3、二叉树的查找

在实现插入这个接口之前得先实现查找，因为要插入一个节点，我们就需要先找到相应的位置。

倘若找不到这个节点，就返回nullptr,找到了，就返回指向这个结点的指针。

Node* Find(const T& data)
{Node* cur = _root;while (cur){if (cur->_val == data){return cur;}else if (cur->_val > data){cur = cur->right;}else{cur = cur->left;}}return nullptr;
}

4、二叉树的插入

接下来就是实现插入这个重要接口，由于二叉搜索树的独特性质，不能插入相同的元素，为了知道是否插入成功，我们需要给这个接口的返回值返回一个bool类型

bool Insert(const T& data)
{if (_root == nullptr)//如果是一个空树，就创建一个结点随后返回真，并把_root指向新创建的结点{_root = new Node(data);return true;}Node* cur == _root;Node* parent = nullptr;//记录cur的父节点while (cur){parent = cur;if (cur->_val > data){cur = cur->left;}else if (cur->_val < data){cur = cur->right;}else{return false;}}cur = new Node(data);if (cur->_val > parent->_val){parent->right = cur;}else{parent->left = cur;}return true;
}

5、二叉树的删除

在二叉搜索树中，删除节点的操作是最复杂的。删除操作需要保持二叉搜索树的性质，即在删除一个节点后，仍然能够保持左子树的所有节点值小于当前节点值，右子树的所有节点值大于当前节点值。如果我们想要删除的节点为叶子，那还比较轻松，但如果我们想要删除的节点仍然拥有子节点，那就麻烦许多了。

日常我们有两种思路解决，二者大同小异，一个是寻找左子树的最最右节点，一个是找右子树的最左节点，这里我就以右子树的最左节点为例。

bool Erase(const T& data)
{Node* parent = nullptr;Node* cur = _root;while (cur)//查找是否有这个节点{if (cur->_val > data){parent = cur;cur = cur->left;}else if (cur->_val < data){parent = cur;cur = cur->right;}else{break;}}if (cur == nullptr)//没有这个节点直接返回{return false;}if (cur->left == nullptr)//左为空或者右为空，或者都为空的情况下{if (cur == _root){_root = _root->right;}if (cur == parent->left){parent->left = cur->right;}else  {parent->right = cur->right;}delete cur;cur = nullptr;return true;}if (cur->right == nullptr){if (cur == _root){_root = _root->left;}if (cur == parent->left){parent->left = cur->left;}else{parent->right = cur->left;}delete cur;cur = nullptr;return true;}Node* pparent = cur;//两个子节点都在的情况下，需要找到右子树的最小节点，将两个的值进行交换，再删除右子树的最小节点，此时又是一个0/1子树的选择情况Node* pcur = cur->right;while (pcur->left){pparent = pcur;pcur = pcur->left;}cur->_val = pcur->_val;Node* p = pcur->right;if (pparent->left == pcur){pparent->left = p;}else{pparent->right = p;}delete pcur;pcur = nullptr;return true;}

大概的思路就是先找到要删除的节点，随后判断这个节点有几个非空子节点，0和1个空节点是一样的处理方法，二两个非空节点就需要用右子树的最小值或者左子树的最大值来替换，随后删除替换了值的那个节点。

6、二叉树的遍历

由于在外部，我们拿不到根节点，那么我们要怎么遍历一遍呢？这里就需要用到我们的套层艺术了！

首先我们先在private中写一个中序遍历的接口：

void order(Node*root)
{if (root == nullptr){return;}order(root->left);cout << root->_val << " ";order(root->right);
}

随后，我们在publci中写一个无参的_oeder函数来调用order就行了。

void _order()
{order(_root);cout<< endl;
}

我们写一个简单的用例测试一下

#include<iostream>
using namespace std;
#include"BSTree.h"int main()
{BSTree<int>Tree;Tree.Insert(6);Tree.Insert(3);Tree.Insert(2);Tree.Insert(1);Tree.Insert(4);Tree.Insert(7);Tree.Insert(9);Tree.Insert(8);Tree.Insert(5);Tree.Insert(10);Tree._order();for (int i = 1; i <= 10; ++i){Tree.Erase(i);Tree._order();}Tree._order();return 0;
}

输出结果没有问题：

7、二叉树的析构销毁

在上面的代码中，存在一个内存泄漏的问题，就是我们所有的节点都是自己new出来的，所以也需要我们自己手动去销毁，自动构建出来的析构函数自然就不行，所以必须要自己写析构函数。所以我们可以实现一个destroy函数，后序递归销毁二叉树，随后让析构函数调用destroy函数就行。

void Destroy(Node* root)
{if (root){Destroy(root->left);Destroy(root->right);delete root;}
}
~BSTree(){destroy(_root);}

8、由key模型向key-val模型的转化

接下来我们去实现一下两种模型之间的转化：

其实，二者并无太大区别，在插入销毁查找中判断仍然使用key值判断只不过是把以往的单独的T改成了T,K，把之前的_val改成_key。

只不过我们需要实现一个额外的构造函数，这个构造函数需要进行深拷贝来实现，也就是说我们要进行递归对这个二叉树进行深拷贝。

	BSTree(const BSTree<T,K>&t){_root=Copy(t._root);}Node* Copy(Node* root){if (root == nullptr){return nullptr;}Node* newRoot = new Node(root->_key, root->_val);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}

key模型整体的代码如下：

#pragma oncetemplate<class T>
struct BSTNode
{BSTNode(const T&data=T()):_val(data),left(nullptr),right(nullptr){}BSTNode<T>* right;BSTNode<T>* left;T _val;
};template<class T>
class BSTree
{typedef BSTNode<T> Node;
public:BSTree():_root(nullptr){}~BSTree(){destroy(_root);}Node* Find(const T& data){Node* cur = _root;while (cur){if (cur->_val == data){return cur;}else if (cur->_val > data){cur = cur->left;}else{cur = cur->right;}}return nullptr;}bool Insert(const T& data){if (_root == nullptr)//如果是一个空树，就创建一个结点随后返回真，并把_root指向新创建的结点{_root = new Node(data);return true;}Node* cur = _root;Node* parent = nullptr;//记录cur的父节点while (cur){parent = cur;if (cur->_val > data){cur = cur->left;}else if (cur->_val < data){cur = cur->right;}else{return false;}}cur = new Node(data);if (cur->_val > parent->_val){parent->right = cur;}else{parent->left = cur;}return true;}bool Erase(const T& data){Node* parent = nullptr;Node* cur = _root;while (cur)//查找是否有这个节点{if (cur->_val > data){parent = cur;cur = cur->left;}else if (cur->_val < data){parent = cur;cur = cur->right;}else{break;}}if (cur == nullptr)//没有这个节点直接返回{return false;}if (cur->left == nullptr)//左为空或者右为空，或者都为空的情况下{if (cur == _root){_root = _root->right;}else if (cur == parent->left){parent->left = cur->right;}else  {parent->right = cur->right;}delete cur;cur = nullptr;return true;}if (cur->right == nullptr){if (cur == _root){_root = _root->left;}else if (cur == parent->left){parent->left = cur->left;}else{parent->right = cur->left;}delete cur;cur = nullptr;return true;}Node* pparent = cur;//两个子节点都在的情况下，需要找到右子树的最小节点，将两个的值进行交换，再删除右子树的最小节点，此时又是一个0/1子树的选择情况Node* pcur = cur->right;while (pcur->left){pparent = pcur;pcur = pcur->left;}cur->_val = pcur->_val;Node* p = pcur->right;if (pparent->left == pcur){pparent->left = p;}else{pparent->right = p;}delete pcur;pcur = nullptr;return true;}void _order(){order(_root);cout<< endl;}
private:void order(Node*root){if (root == nullptr){return;}order(root->left);cout << root->_val << " ";order(root->right);}void Destroy(Node* root){if (root){Destroy(root->left);Destroy(root->right);delete root;}}Node* _root;
};

key-val的模型代码如下:


template<class T, class K>
struct BSTNode
{BSTNode(const T& key = T(), const K& val=K()):_key(key),_val(val), left(nullptr), right(nullptr){}BSTNode<T,K>* right;BSTNode<T,K>* left;T _key;K _val;
};template<class T,class K>
class BSTree
{typedef BSTNode<T,K> Node;
public:BSTree() = default;BSTree(const BSTree<T,K>&t){_root=Copy(t._root);}Node* Copy(Node* root){if (root == nullptr){return nullptr;}Node* newRoot = new Node(root->_key, root->_val);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}~BSTree(){Destroy(_root);}Node* Find(const T& key){Node* cur = _root;while (cur){if (cur->_key == key){return cur;}else if (cur->_key > key){cur = cur->left;}else{cur = cur->right;}}return nullptr;}bool Insert(const T& key,const K&val){if (_root == nullptr)//如果是一个空树，就创建一个结点随后返回真，并把_root指向新创建的结点{_root = new Node(key, val);return true;}Node* cur = _root;Node* parent = nullptr;//记录cur的父节点while (cur){parent = cur;if (cur->_key > key){cur = cur->left;}else if (cur->_key < key){cur = cur->right;}else{return false;}}cur = new Node(key,val);if (cur->_key > parent->_key){parent->right = cur;}else{parent->left = cur;}return true;}bool Erase(const T& 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{break;}}if (cur == nullptr)//没有这个节点直接返回{return false;}if (cur->left == nullptr)//左为空或者右为空，或者都为空的情况下{if (cur == _root){_root = _root->right;}else if (cur == parent->left){parent->left = cur->right;}else{parent->right = cur->right;}delete cur;cur = nullptr;return true;}if (cur->right == nullptr){if (cur == _root){_root = _root->left;}else if (cur == parent->left){parent->left = cur->left;}else{parent->right = cur->left;}delete cur;cur = nullptr;return true;}Node* pparent = cur;//两个子节点都在的情况下，需要找到右子树的最小节点，将两个的值进行交换，再删除右子树的最小节点，此时又是一个0/1子树的选择情况Node* pcur = cur->right;while (pcur->left){pparent = pcur;pcur = pcur->left;}cur->_key = pcur->_key;Node* p = pcur->right;if (pparent->left == pcur){pparent->left = p;}else{pparent->right = p;}delete pcur;pcur = nullptr;return true;}void _order(){order(_root);cout << endl;}
private:void order(Node* root){if (root == nullptr){return;}order(root->left);cout << root->_key << " " << root->_val << " ";order(root->right);}void Destroy(Node* root){if (root){Destroy(root->left);Destroy(root->right);delete root;}}Node* _root;
};

c测试用例如下：

#include<iostream>
using namespace std;
#include"BSTree.h"void TestBSTree()
{// 统计水果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };BSTree<string, int> countTree;for (const auto& str : arr){// 先查找水果在不在搜索树中// 1、不在，说明水果第一次出现，则插入<水果, 1>// 2、在，则查找到的节点中水果对应的次数++//BSTreeNode<string, int>* ret = countTree.Find(str);auto ret = countTree.Find(str);if (ret == NULL){countTree.Insert(str, 1);}else{ret->_val++;}}countTree._order();
}int main()
{BSTree<int,string>Tree;Tree.Insert(6, "six");Tree.Insert(3,"three");Tree.Insert(2,"two");Tree.Insert(1,"one");Tree.Insert(4,"four");Tree.Insert(7,"seven");Tree.Insert(9,"nine");Tree.Insert(8,"eight");Tree.Insert(5,"five");Tree.Insert(10,"ten");Tree._order();for (int i = 1; i <= 10; ++i){Tree.Erase(i);Tree._order();}Tree._order();cout << endl;TestBSTree(); return 0;
}

三.、小结

二叉搜索树是一种重要的数据结构，具有良好的查找、插入和删除性能。但它也存在潜在的不平衡问题，因此在实际应用中，常常需要通过自平衡的二叉搜索树（如AVL树、红黑树）来保证性能。

希望本文对基础的二叉搜索树的探索能对您产生帮助！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/403160.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

面试官：Java虚拟机是什么，Java虚拟机的内存模型是什么样子的？

面试官：Java虚拟机是什么，Java虚拟机的内存模型是什么样子的？

哈喽&#xff01;大家好&#xff0c;我是小奇&#xff0c;一个专给面试官添堵的撑序员 小奇打算以轻松幽默的对话方式来分享一些技术&#xff0c;如果你觉得通过小奇的文章学到了东西&#xff0c;那就给小奇一个赞吧 文章持续更新&#xff0c;可以微信搜索【小奇JAVA面试】第一…
阅读更多...
基于WEB的旅游推荐系统设计与实现

基于WEB的旅游推荐系统设计与实现

TOC springboot280基于WEB的旅游推荐系统设计与实现 第1章 绪论 1.1选题动因 当前的网络技术&#xff0c;软件技术等都具备成熟的理论基础&#xff0c;市场上也出现各种技术开发的软件&#xff0c;这些软件都被用于各个领域&#xff0c;包括生活和工作的领域。随着电脑和笔…
阅读更多...
SVN权限控制解析

SVN权限控制解析

一、基础数据说明 1. 代码目录存在多级 图1-1 SVN目录 如图1-1&#xff1a; 第一级目录是 科顺&#xff0c;代表 科顺项目&#xff0c;项目文件包括 文档、代码等等。第二级目录 分别是 2.1 resources 用于存放文档&#xff0c;开发和实施均需…
阅读更多...
Qt登录窗口

Qt登录窗口

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget),btn(new QPushButton("取消", this)),login_btn(new QPushButton("登录", this)) { ui->setupUi(this);thi…
阅读更多...
Llama 3.1深度解析：405B、70B及8B模型的多语言与长上下文处理能力

Llama 3.1深度解析：405B、70B及8B模型的多语言与长上下文处理能力

Llama 3.1 发布了&#xff01;今天我们迎来了 Llama 家族的新成员 Llama 3.1 进入 Hugging Face 平台。我们很高兴与 Meta 合作&#xff0c;确保在 Hugging Face 生态系统中实现最佳集成。Hub 上现有八个开源权重模型 (3 个基础模型和 5 个微调模型)。 Llama 3.1 有三种规格: …
阅读更多...
法线纹理贴图计算（切线空间世界空间）

法线纹理贴图计算（切线空间世界空间）

效率&#xff1a; 在切线空间中计算&#xff0c;效率更高&#xff0c;因为可以在顶点着色器中就完成对光照、视角方向的矩 阵变换&#xff0c;计算量相对较小。( 矩阵变换在顶点着色器中计算) 在世界空间中计算&#xff0c;效率较低&#xff0c;由于需要对法线贴图进行采样&a…
阅读更多...
mybatis druid postgresql statement超时原理原理

mybatis druid postgresql statement超时原理原理

yaml设置超时 mybatis-plus:mapper-locations: classpath:/mapper/*.xml # MyBatis Mapper XML文件的位置type-aliases-package: com.company.mi.entity # 实体类所在的包configuration:default-statement-timeout: 10 configuration 设置超时 BaseStatementHandler设置超时 …
阅读更多...
Thread 类的基本用法

Thread 类的基本用法

目录 什么是线程&#xff1f; 编写多线程程序 线程创建的方式 继承 Thread 类&#xff0c;重写 run 方法 实现 Runnable 接口&#xff0c;重写 run 方法 匿名内部类创建 Thread 子类 匿名内部类创建 Runnable 子类对象 lambda表达式 Thread 类和常用方法 Thread 的常…
阅读更多...
node.js part1

node.js part1

Node.js Node.js 是一个跨平台JavaScript 运行环境&#xff0c;使开发者可以搭建服务器端的 JavaScript 应用程序。作用&#xff1a;使用Node.js编写服务器端程序 编写数据接口&#xff0c;提供网页资源浏览功能等等 前端工程化&#xff1a;为后续学习Vue和React等框架做铺垫. …
阅读更多...
基于CDIO概念的人工智能物联网系统开发与实施的人才培养研究

基于CDIO概念的人工智能物联网系统开发与实施的人才培养研究

目录 1. 引言&#xff08;Introduction&#xff09; 2. AIoT技术及其培训特点&#xff08;The Characteristics of AIOT and Its Training&#xff09; 3. 基于CDIO概念的AIoT课程改革&#xff08;CDIO Concept-based Reform of AIOT Course&#xff09; 4. AIoT课程内容安…
阅读更多...
Idea里配置Maven版本

Idea里配置Maven版本

一、安装Maven 1. 官网下载maven地址&#xff1a; Maven – Download Apache Maven Binary是可执行版本&#xff0c;已经编译好可以直接使用。 Source是源代码版本&#xff0c;需要自己编译成可执行软件才可使用。tar.gz和zip两种压缩格式,其实这两个压缩文件里面包含的内容是…
阅读更多...
Verilog刷题笔记50

Verilog刷题笔记50

题目&#xff1a; Given the following state machine with 1 input and 2 outputs: 解题&#xff1a; module top_module(input in,input [9:0] state,output [9:0] next_state,output out1,output out2);assign next_state[0]~in&(state[0]|state[1]|state[2]|state[3]…
阅读更多...
Java方法01：什么是方法

Java方法01：什么是方法

本节视频链接&#xff1a;Java方法01&#xff1a;什么是方法&#xff1f;_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV12J41137hu?p45&vd_sourceb5775c3a4ea16a5306db9c7c1c1486b5 Java中的‌方法‌是一段执行特定任务的代码片段&#xff0c;‌它是程序的基本构…
阅读更多...
C#中的S7协议

C#中的S7协议

S7协议-S7COMM S7COMM 进行写 CTOP->PDU type已知枚举值 0X0E连接请求0x0d连接确认0x08断开请求0x0c断开确认0x05拒绝访问0x01加急数据0x02加急数据确认0x04用户数据0x07TPDU错误0x0f数据传输 S7Header->ROSCTR已知枚举值 0X01JOB REQUEST。主站发送请求0x02Ack。从站…
阅读更多...
Android MediaRecorder 视频录制及报错解决

Android MediaRecorder 视频录制及报错解决

目录 一、start failed: -19 二、使用MediaRecorder录制视频 2.1 申请权限 2.2 布局文件 2.3 MediaRecordActivity 2.4 运行结果 三、拓展 3.1 录制视频模糊(解决) 3.2 阿里云OSS上传文件 3.2.1 权限(刚需) 3.2.2 安装SDK 3.2.3 使用 相关链接 一、start failed…
阅读更多...
基于spring boot的小型诊疗预约平台的设计与开发

基于spring boot的小型诊疗预约平台的设计与开发

TOC springboot262基于spring boot的小型诊疗预约平台的设计与开发 绪论 1.1 研究背景 当前社会各行业领域竞争压力非常大&#xff0c;随着当前时代的信息化&#xff0c;科学化发展&#xff0c;让社会各行业领域都争相使用新的信息技术&#xff0c;对行业内的各种相关数据进…
阅读更多...
C++之模版初阶

C++之模版初阶

目录 前言 1.泛型编程 2.函数模版 2.1函数模版概念 2.2函数模版格式 2.3函数模版的原理 2.4函数模版的实例化 2.5模版参数的匹配原则 3.类模版 3.1类模版的定义格式 3.2类模版的实例化 结束语 前言 前面我们学习了C的类与对象和内存管理&#xff0c;接下来我们继续学习…
阅读更多...
【等保测评】Mysql测评中使用的命令汇总

【等保测评】Mysql测评中使用的命令汇总

一、身份鉴别 a) 应对登录的用户进行身份标识和鉴别&#xff0c;身份标识具有唯一性&#xff0c;身份鉴别信息具有复杂度要求并定期更换&#xff1b; mysql -uroot -p 查看登录是否需要输入口令鉴别用户身份 select user,host from mysql.user 查看是否存在相同账户…
阅读更多...
苹果手机怎么清理重复照片的解决方案

苹果手机怎么清理重复照片的解决方案

随着智能手机摄像头技术的飞速发展&#xff0c;我们越来越依赖iPhone来记录生活中的点点滴滴。不可避免地&#xff0c;这也导致了大量重复照片的产生&#xff0c;这些重复照片不仅占用了宝贵的存储空间&#xff0c;还使得照片库显得混乱无序。本文将介绍苹果手机怎么清理重复照…
阅读更多...
【项目实战】C++视频共享点播系统

【项目实战】C++视频共享点播系统

目录 一、项目介绍 1.1 对视频共享点播系统的认识 1.2服务端程序负责功能 1.3 服务端功能模块划分 1.4 项目界面演示 1.5预备知识 二.环境搭建 2.1 安装 Jsoncpp 库 2.1.1 使用jsoncpp 2.2 引入httplib库 2.2.1 安装Git&#xff08;如果你的系统尚未安装Git&#xf…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023