【C++数据结构】二叉搜索树（超详细图解操作过程，超详细讲解代码实现）

目录

01.二叉搜索树的概念

02.二叉搜索树的操作过程

03.二叉搜索树的代码实现

（1）基本框架

（2）树的创建与销毁

（3）元素的查找

（4）元素的插入

（5）元素的删除

（6）中序遍历

01.二叉搜索树的概念

有一种查找方法，具有极高的查找效率，时间复杂度仅为 O(log⁡n)。在每一步查找过程中都会将搜索范围减半，这就是二分查找。

但是在实际应用中，我们并不经常使用二分查找。这是因为它只能在有序数组或有序数据结构上工作，如果数据是无序的，则需要先进行排序；而且它只适用于数组或连续存储的数据结构中。

在实际运用中，我们更常用的是二叉搜索树（Binary Search Tree, BST），其查找时间复杂度也是 O(log⁡n)，并且拥有高效的插入和删除操作。

二叉搜索树又称二叉排序树，它的定义如下：

1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

3.它的左右子树也分别为二叉搜索树

检验一个二叉树是否是二叉搜索树，不仅要检查每个节点的左右子节点的值是否满足条件，还要确保整个左子树的所有节点的值都小于根节点的值，整个右子树的所有节点的值都大于根节点的值。

02.二叉搜索树的操作过程

1.二叉搜索树的查找

        step1:从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

        step2:如果最终走到节点为空还没找到，则这个值不存在。

2.二叉树搜索树的插入

二叉搜索树的插入都是在叶子节点进行插入，第一个插入的元素就是根节点，后面插入的元素根据性质判断插入位置

3.二叉搜索树的删除

二叉搜索树的删除除了会在叶子结点进行删除外，还可能在中间结点进行删除，在中间结点进行删除时，就需要考虑它的孩子结点的情况，因此要分情况讨论：

case1.删除结点无孩子结点

case2.删除结点只有左孩子结点

case3.删除结点只有右孩子结点

case4.删除结点有左、右孩子结点

其实case1和case2或3可以结合起来，实际删除过程如下：

case2：删除该结点后，该父结点指向该左孩子结点

case3：删除该结点后，该父结点指向该右孩子结点

case4：需要在其子树中寻找一个结点替代该结点（左子树的值最大结点/右子树的值最小结点），替换后仍满足搜索树要求

比如上述例子中，可以用36（左子树的值最大结点）或50（右子树的值最小结点）对41进行替换，然后将替换的结点位置进行删除。

03.二叉搜索树的代码实现

（1）基本框架

身为一个二叉树，其结点内部包含左孩子结点指针、右孩子结点指针、数据，在二叉搜索树中，我们需要实现它的查找、插入、删除以及中序遍历操作。

为什么特意要实现中序遍历呢，因为根据二叉搜索树的特性（任意一个结点，其左子树的所有结点都小于该结点，右子树所有结点都大于该结点）中序遍历会以递增的方式访问树中的所有结点（先访问左子树-->根节点-->右子树），此时就可以按顺序输出所有节点，实现了排序的效果。

template<class T>
struct BSTNode
{BSTNode(const T& data = T()):_pLeft(nullptr), _pRight(nullptr), _data(data){}BSTNode<T>* _pLeft;BSTNode<T>* _pRight;T _data;
};
template<class T>
class BSTree
{typedef BSTNode<T> Node;typedef Node* PNode;
public:BSTree();//默认构造~BSTree();//析构PNode Find(const T& data);//查找元素bool Insert(const T& data);//插入元素bool Erase(const T& data);//删除元素void InOrder();//中序遍历
private:PNode _pRoot;
};

（2）树的创建与销毁

树的默认构造只需要在初始化列表中将成员变量根结点赋值为空即可。

析构过程与其他二叉树相同，需要递归地销毁每一个结点：对于每一个结点，首先递归销毁它的左子树，然后递归销毁销毁它的右子树，最后销毁该结点本身。这种顺序保证了我们在销毁父结点前已经销毁了它的所有子结点，防止内存泄漏。

BSTree() : _pRoot(nullptr){}
~BSTree()
{destory(_pRoot);_pRoot = nullptr;
}
void destory(const PNode& node)
{if (node == nullptr)return;destory(node->_pLeft);destory(node->_pRight);delete node;
}

（3）元素的查找

首先将要查找的值与当前节点进行比较，根据比较结果选择路径：

  • 比当前节点小，则移向当前节点的左子节点。
  • 比当前节点大，则移向当前节点的右子节点。
  • 等于当前节点，则查找成功，返回当前节点。
  • 遍历到结点为空还没找到，则该值不存在，返回空。
    PNode Find(const T& data){Node* cur = _pRoot;while (cur != nullptr){if (data < cur->_data)cur = cur->_pLeft;else if (data > cur->_data)cur = cur->_pRight;elsereturn cur;}return nullptr;}

（4）元素的插入

将待插入的值与当前节点进行比较：

  • 比当前节点小，则移向当前节点的左子节点，。
  • 比当前节点的值大，则移向当前节点的右子节点。
  • 等于当前节点的值，则不能进行插入，返回false。
  • 遍历到节点为空，则当前位置就是要插入位置

我们可以定义两个指针，一个记录当前遍历节点位置，一个记录父节点位置，这样在找到插入位置时就可以直接进行插入。

    bool Insert(const T& data){// 如果树为空，直接插入if (nullptr == _pRoot){_pRoot = new Node(data);return true;}// 按照二叉搜索树的性质查找data在树中的插入位置PNode pCur = _pRoot;// 记录pCur的双亲，因为新元素最终插入在pCur双亲左右孩子的位置PNode pParent = nullptr;while (pCur){pParent = pCur;if (data < pCur->_data)pCur = pCur->_pLeft;else if (data > pCur->_data)pCur = pCur->_pRight;elsereturn false; // 元素已经在树中存在}// 插入元素pCur = new Node(data);if (data < pParent->_data)pParent->_pLeft = pCur;elsepParent->_pRight = pCur;return true;}

以上方法我们需要显式的管理父节点指针，过程略显繁琐，有没有什么办法可以直接修改当前节点指针呢，我们观察以下这段代码：

    bool Insert(const T& data){InsertR(_pRoot,data);return true;}   void InsertR(PNode& node, const T& data){if (nullptr == node) {node = new Node(data);return;}if (node->_data == data)return;if (data < node->_data)InsertR(node->_pLeft, data);elseInsertR(node->_pRight, data);return;}

在这段代码中，我们依旧将data值与当前节点进行比较，比较之后，我们选择递归地将data插入到左或右子树当中，并且在递归过程中通过引用传参，可以直接修改节点指针，就不需要用到父节点指针了。

这种引用传参的递归方法，巧妙地化简了插入过程，并且在每个递归调用中自然地处理了边界情况，逻辑更为直观。

（5）元素的删除

根据上面的分析过程，分情况进行讨论

a：删除该结点后，该父结点指向该左孩子结点

b：删除该结点后，该父结点指向该右孩子结点

在a和b情况中，我们直接将父节点中指向当前节点的指针改为指向该节点的下一节点，然后对该节点进行销毁即可。

c：需要在其子树中寻找一个结点替代该结点（左子树的值最大结点/右子树的值最小结点），替换后仍满足搜索树要求

第三种情况处理起来就复杂许多，我们需要先找到替代节点（左子树最大或右子树最小，这里我们选择左子树最大这种情况），找到后还需要考虑替代节点是否含有左子树（不需要考虑右子树，因为最大值肯定没有右子树），如果有，我们需要将替代节点的左子树接到替代节点的父节点上，因此我们还需要定义一个父节点指针变量。

代码呈现如下：

    bool Erase(const T& data){// 如果树为空，删除失败if (nullptr == _pRoot)return false;// 查找在data在树中的位置PNode pCur = _pRoot;PNode pParent = nullptr;while (pCur){if (data == pCur->_data)break;else if (data < pCur->_data){pParent = pCur;pCur = pCur->_pLeft;}else{pParent = pCur;pCur = pCur->_pRight;}}// data不在二叉搜索树中，无法删除if (nullptr == pCur)return false;// 分以下情况进行删除if (nullptr == pCur->_pRight){// 当前节点只有左孩子或者左孩子为空---可直接删除if (pParent->_pLeft == pCur)pParent->_pLeft = pCur->_pLeft;elsepParent->_pRight = pCur->_pLeft;delete pCur;}else if (nullptr == pCur->_pLeft){// 当前节点只有右孩子---可直接删除if (pParent->_pLeft == pCur)pParent->_pLeft = pCur->_pRight;elsepParent->_pRight = pCur->_pRight;delete pCur;}else{// 当前节点同时具有左右孩子Node* leftmax = pCur->_pLeft;Node* pre = pCur;while (leftmax->_pRight) {pre = leftmax;leftmax = leftmax->_pRight;}pCur->_data = leftmax->_data;if (leftmax->_pLeft)pre->_pRight = leftmax->_pLeft;else if (pre == pCur)pCur->_pLeft = nullptr;elsepre->_pRight = nullptr;delete leftmax;leftmax = nullptr;}return true;}

这里我们还是可以考虑用引用传参递归的方法简化过程

但要注意的是，与插入操作不同，删除操作后，返回值是更新后的子树的根节点，这是因为在删除某些节点时，子树的根节点可能会发生变化，比如左子树或右子树的新根节点替代了被删除的节点。而插入操作则不需要，因为树的结构是自然地扩展的。

   PNode EraseR(PNode& node, const T& data){if (nullptr == node)return node;if (data == node->_data){if (!node->_pRight)return node->_pLeft;else if (!node->_pLeft)return node->_pRight;else {if (!node->_pRight) {PNode temp = node->_pLeft;delete node;return temp;}else if (!node->_pLeft) {PNode temp = node->_pRight;delete node;return temp;}else {PNode minNode = FindMin(node->_pRight);node->_data = minNode->_data;node->_pRight = EraseR(node->_pRight, minNode->_data);}}}if (data < node->_data)node->_pLeft = EraseR(node->_pLeft, data);else if (data > node->_data)node->_pRight = EraseR(node->_pRight, data);return node;}PNode FindMin(PNode node) const {while (node && node->_pLeft != nullptr)node = node->_pLeft;return node;}

（6）中序遍历

中序遍历的顺序是：左子树 -> 根节点 -> 右子树，我们使用递归方法来实现：

1.递归左子树：首先递归访问左子树，确保左子树的所有节点值被访问和打印。

2.打印当前节点：然后打印当前节点的值。

3.递归右子树：最后递归访问右子树，确保右子树的所有节点值被访问和打印。

    void InOrder(){print(_pRoot);cout << endl;} void print(PNode node){if (node == nullptr)return;print(node->_pLeft);cout << node->_data << " ";print(node->_pRight);}

最后附上完整代码：

#include<iostream>
using namespace std;template<class T>
struct BSTNode
{BSTNode(const T& data = T()):_pLeft(nullptr), _pRight(nullptr), _data(data){}BSTNode<T>* _pLeft;BSTNode<T>* _pRight;T _data;
};
template<class T>
class BSTree
{typedef BSTNode<T> Node;typedef Node* PNode;
public:BSTree() : _pRoot(nullptr){}~BSTree(){destory(_pRoot);_pRoot = nullptr;}PNode Find(const T& data){Node* cur = _pRoot;while (cur != nullptr){if (data < cur->_data)cur = cur->_pLeft;else if (data > cur->_data)cur = cur->_pRight;elsereturn cur;}return nullptr;}bool Insert(const T& data){// 如果树为空，直接插入if (nullptr == _pRoot){_pRoot = new Node(data);return true;}// 按照二叉搜索树的性质查找data在树中的插入位置PNode pCur = _pRoot;// 记录pCur的双亲，因为新元素最终插入在pCur双亲左右孩子的位置PNode pParent = nullptr;while (pCur){pParent = pCur;if (data < pCur->_data)pCur = pCur->_pLeft;else if (data > pCur->_data)pCur = pCur->_pRight;elsereturn false; // 元素已经在树中存在}// 插入元素pCur = new Node(data);if (data < pParent->_data)pParent->_pLeft = pCur;elsepParent->_pRight = pCur;return true;/*InsertR(_pRoot,data);return true;*/}bool Erase(const T& data){// 如果树为空，删除失败if (nullptr == _pRoot)return false;// 查找在data在树中的位置PNode pCur = _pRoot;PNode pParent = nullptr;while (pCur){if (data == pCur->_data)break;else if (data < pCur->_data){pParent = pCur;pCur = pCur->_pLeft;}else{pParent = pCur;pCur = pCur->_pRight;}}// data不在二叉搜索树中，无法删除if (nullptr == pCur)return false;// 分以下情况进行删除if (nullptr == pCur->_pRight){// 当前节点只有左孩子或者左孩子为空---可直接删除if (pParent->_pLeft == pCur)pParent->_pLeft = pCur->_pLeft;elsepParent->_pRight = pCur->_pLeft;delete pCur;}else if (nullptr == pCur->_pLeft){// 当前节点只有右孩子---可直接删除if (pParent->_pLeft == pCur)pParent->_pLeft = pCur->_pRight;elsepParent->_pRight = pCur->_pRight;delete pCur;}else{Node* leftmax = pCur->_pLeft;Node* pre = pCur;while (leftmax->_pRight) {pre = leftmax;leftmax = leftmax->_pRight;}pCur->_data = leftmax->_data;if (leftmax->_pLeft)pre->_pRight = leftmax->_pLeft;else if (pre == pCur)pCur->_pLeft = nullptr;elsepre->_pRight = nullptr;delete leftmax;leftmax = nullptr;}return true;//EraseR(_pRoot, data);//return true;}void InOrder(){print(_pRoot);cout << endl;} 
private:PNode _pRoot;void InsertR(PNode& node, const T& data){if (nullptr == node) {node = new Node(data);return;}if (node->_data == data)return;if (data < node->_data)InsertR(node->_pLeft, data);elseInsertR(node->_pRight, data);return;}PNode EraseR(PNode& node, const T& data){if (nullptr == node)return node;if (data == node->_data){if (!node->_pRight)return node->_pLeft;else if (!node->_pLeft)return node->_pRight;else {if (!node->_pRight) {PNode temp = node->_pLeft;delete node;return temp;}else if (!node->_pLeft) {PNode temp = node->_pRight;delete node;return temp;}else {PNode minNode = FindMin(node->_pRight);node->_data = minNode->_data;node->_pRight = EraseR(node->_pRight, minNode->_data);}}}if (data < node->_data)node->_pLeft = EraseR(node->_pLeft, data);else if (data > node->_data)node->_pRight = EraseR(node->_pRight, data);return node;}PNode FindMin(PNode node) const {while (node && node->_pLeft != nullptr)node = node->_pLeft;return node;}void destory(const PNode& node){if (node == nullptr)return;destory(node->_pLeft);destory(node->_pRight);delete node;}void print(PNode node){if (node == nullptr)return;print(node->_pLeft);cout << node->_data << " ";print(node->_pRight);}
};

以上就是二叉搜索树的图解与完整实现过程，欢迎在评论区留言，觉得这篇博客对你有帮助的，可以点赞收藏关注支持一波~😉

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

Day71 代码随想录打卡|回溯算法篇---全排列

Day71 代码随想录打卡|回溯算法篇---全排列

题目&#xff08;leecode T46&#xff09;&#xff1a; 给定一个不含重复数字的数组 nums &#xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 方法&#xff1a;全排列是数学中的基础问题&#xff0c;也是回溯算法能解决的经典问题。全排列因为每个元素都会…
阅读更多...
卷积神经网络学习问题总结

卷积神经网络学习问题总结

问题一&#xff1a; 深度学习中的损失函数和应用场景 回归任务&#xff1a; 均方误差函数&#xff08;MSE&#xff09;适用于回归任务&#xff0c;如预测房价、预测股票价格等。 import torch.nn as nn loss_fn nn.MSELoss() 分类任务&#xff1a; 交叉熵损失函数&…
阅读更多...
AI算法19-偏最小二乘法回归算法Partial Least Squares Regression | PLS

AI算法19-偏最小二乘法回归算法Partial Least Squares Regression | PLS

偏最小二乘法回归算法简介 算法概述 偏最小二乘法模型可分为偏最小二乘回归模型和偏最小二乘路径模型。其中偏最小二乘回归模型是一种新型的多元统计方法&#xff0c;它集中了主成分分析、典型相关分析和线性回归的特点&#xff0c;特别在解决回归中的共线性问题具有无可比拟…
阅读更多...
PX4 运行 make px4_sitl_default gazebo 报错

PX4 运行 make px4_sitl_default gazebo 报错

报错原因&#xff1a;最开始我把依赖一直都是在base环境下安装的&#xff0c;没有conda deactivate&#xff0c;而pip install的东西应该装在系统环境&#xff0c;不能装在base环境下&#xff0c;sudo apt 是装在系统环境的 1.检查ros 用鱼香ros安装 wget http://fishros.…
阅读更多...
日活2.5亿的Twitter 使用了哪些数据库？

日活2.5亿的Twitter 使用了哪些数据库？

Twitter 使用什么数据库存储用户每天发送的数亿条推文&#xff1f;是 SQL、NoSQL 还是其它持久化存储系统&#xff1f; Twitter 使用什么数据库&#xff1f; 任何一个稍微有点规模的系统其存储层绝不会只使用一种数据库&#xff0c;服务于数以亿计用户的Twitter更是如此。Twit…
阅读更多...
《YOLOv10改进实战专栏》专栏介绍 专栏目录

《YOLOv10改进实战专栏》专栏介绍 专栏目录

《YOLOv10改进实战专栏》介绍及目录 YOLOv10官方仓库地址 专栏地址&#xff1a;点击跳转 专栏导航如下&#xff1a; &#x1f380;基础入门篇&#x1f380; 万字长文&#xff0c;小白新手怎么开始做YOLO实验&#xff0c;从零开始教&#xff01;整体思路在这里&#xff0c;科研指…
阅读更多...
Vue学习---vue cli 项目创建

Vue学习---vue cli 项目创建

使用的编辑工具webStorm 创建例子: hello vue create hello 选择 vue3 进行创建 运行 npm run serve 测试访问&#xff1a;http://localhost:8080 改动内容重新编译&#xff1a; npm run build dist 目录就是编译后的可运行内容
阅读更多...
浅谈C嘎嘎类与对象

浅谈C嘎嘎类与对象

本篇文章与大家浅谈一下C嘎嘎的类与对象知识点 类的定义 关键字&#xff1a;class 语法格式&#xff1a; class 类名 { }&#xff1b;//这里的分号不能少 此外&#xff0c;class有三个属性分别是private、public、protected&#xff0c;这三个属性是干啥的&#xff0c;相…
阅读更多...
MSPM0G3507——时钟主频拉到80MHZ

MSPM0G3507——时钟主频拉到80MHZ

先点开使用时钟树 在配置时钟界面这样配置
阅读更多...
Ghost Browser指纹浏览器年+IPXProxy代理IP组合：SheIn卖家必看

Ghost Browser指纹浏览器年+IPXProxy代理IP组合：SheIn卖家必看

SheIn是一家时尚电商公司&#xff0c;其用户数量近年来增长迅速&#xff0c;在全球的知名度越来越高。SheIn跨境电商卖家想要提升店铺曝光和排名&#xff0c;从而增加销量和信誉的话&#xff0c;就需要满足独立IP、模拟设备参数、独立环境等条件。同时满足这些条件的话就需要用…
阅读更多...
生成式人工智能（AI）的未来

生成式人工智能（AI）的未来

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…
阅读更多...
windows qt编译报错 无法打开包括文件: “EGL/egl.h”: No such file or directory

windows qt编译报错 无法打开包括文件: “EGL/egl.h”: No such file or directory

windows mingw32 qt creator QtAV 推荐ffmpeg依赖包 QT5.14.2 如果出现&#xff1a;无法打开包括文件: “EGL/egl.h”: No such file or directory 可能是Qt6的问题.在QT5上安装。 编译步骤&#xff1a; git clone https://github.com/wang-bin/QtAV.git cd QtAV &&…
阅读更多...
【深度学习教程】

【深度学习教程】

文章目录 pytorch官方教程知识蒸馏&#xff1a;https://pytorch.org/tutorials/beginner/knowledge_distillation_tutorial.html 李宏毅-机器学习/深度学习https://speech.ee.ntu.edu.tw/~hylee/ml/2021-spring.phphttps://speech.ee.ntu.edu.tw/~hylee/ml/2022-spring.phphttp…
阅读更多...
最新Qt6的下载与成功安装详细介绍

最新Qt6的下载与成功安装详细介绍

引言 Qt6 是一款强大的跨平台应用程序开发框架&#xff0c;支持多种编程语言&#xff0c;最常用的是C。Qt6带来了许多改进和新功能&#xff0c;包括对C17的支持、增强的QML和UI技术、新的图形架构&#xff0c;以及构建系统方面的革新。本文将指导你如何在Windows平台上下载和安…
阅读更多...
第五章：卷-将磁盘挂载到容器

第五章：卷-将磁盘挂载到容器

本章内容包括&#xff1a; 创建多容器pod创建一个可在容器间共享磁盘存储的卷在pod中使用git仓库将持久性存储挂载到pod使用预先配置的持久性存储动态调配持久存储 在前面说过&#xff0c;pod类似逻辑主机&#xff0c;在逻辑主机中运行的进程共享如CPU、RAM、网络接口等资源&am…
阅读更多...
一分钟了解什么是1U，2U服务器？

一分钟了解什么是1U，2U服务器？

一、什么是1U&#xff0c;2U服务器&#xff1f; 什么是1U服务器呢&#xff1f;所谓的1U服务器就是一种高可用高密度的低成本服务器平台&#xff0c;U是服务器机箱的高度 1U等于4.45厘米 &#xff0c;那3U就是3x4.5CM了。 u(unit的缩略语)是一种表示组合式机架外部尺寸的单位&a…
阅读更多...
【时时三省】tessy 集成测试：小白入门指导手册

【时时三省】tessy 集成测试：小白入门指导手册

目录 1，创建集成测试模块且分析源文件 2，设置测试环境 3，TIE界面设置相关函数 4，SCE界面增加用例 5，编辑数据 6，用例所对应的测试函数序列 7，添加 work task 函数 8，为测试场景添加函数 9，为函数赋值 10，编辑时间序列的数值 11，执行用例 12，其他注意事项…
阅读更多...
【论文阅读】（StemGNN）多元时间序列预测的谱时间图神经网络

【论文阅读】（StemGNN）多元时间序列预测的谱时间图神经网络

&#xff08;StemGNN&#xff09;Spectral Temporal Graph Neural Network for Multivariate Time-series Forecasting 引用&#xff1a; Cao D , Wang Y , Duan J ,et al.Spectral Temporal Graph Neural Network for Multivariate Time-series Forecasting[J]. 2021.DOI:10.…
阅读更多...
DockerHub无法拉取镜像怎么办

DockerHub无法拉取镜像怎么办

快速构建企业级AIGC项目 LangChat是Java生态下企业级AIGC项目解决方案&#xff0c;在RBAC权限体系的基础上&#xff0c;集成AIGC大模型功能&#xff0c;帮助企业快速定制知识库、企业机器人。 网站文档&#xff1a;Index – LangChat 后台地址&#xff1a;LangChain Chat 前台…
阅读更多...
【深度学习入门篇 ⑧】关于卷积神经网络

【深度学习入门篇 ⑧】关于卷积神经网络

【&#x1f34a;易编橙&#xff1a;一个帮助编程小伙伴少走弯路的终身成长社群&#x1f34a;】 大家好&#xff0c;我是小森( &#xfe61;ˆoˆ&#xfe61; ) &#xff01; 易编橙终身成长社群创始团队嘉宾&#xff0c;橙似锦计划领衔成员、阿里云专家博主、腾讯云内容共创官…
阅读更多...
最新文章

Copyright @ 2022~2023