二叉搜索树（二叉排序树，二叉查找树）（附图详解+代码实现+应用分析）

2024-03-25 20:04
文章标签 分析 代码 实现 应用 详解 搜索 查找 排序 二叉 附图

本文主要是介绍二叉搜索树（二叉排序树，二叉查找树）（附图详解+代码实现+应用分析），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最近学习了有关搜索二叉树的相关知识，在此特意将该知识进行总结分享，希望对大家有所帮助。

文章目录

  • 一.二叉搜索树
    • 1.1二叉搜索树的概念
    • 1.2二叉搜索树的操作（含思路分析+代码实现）
        • 1.2.1二叉搜索树的查找（递归实现看最后总代码）
        • 1.2.2二叉搜索树的插入（递归实现看最后总代码）
        • 1.2.3二叉搜索树的删除（递归实现看最后总代码）
        • 总代码（含递归实现）：
  • 二. 二叉搜索树的应用
  • 三.二叉搜索树的性能分析

一.二叉搜索树

1.1二叉搜索树的概念

二叉搜索树又叫二叉排序树，二叉查找树，可以为空，也可以不为空，具体有以下的特性：

  1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
  2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
  3. 它的左右子树也分别为二叉搜索树

在这里插入图片描述

1.2二叉搜索树的操作（含思路分析+代码实现）

一个基本的二叉搜索树需要有哪些函数（接口）呢？

1.2.1二叉搜索树的查找（递归实现看最后总代码）

基于二叉搜索树的结构的特点：左节点小于根，右节点大于根
查找的思路分析：

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
b、最多查找高度次，走到到空，还没找到，这个值不存在。

图解：
在这里插入图片描述

代码实现：

	bool Find(const K& key)       //key为寻找关键字{if (_root == nullptr)    //如果为空，直接返回{return false;}else                      {Node* cur = _root;         //用cur迭代寻找while (cur){if (key > cur->_key)      //如果key比根节点的值大，则去右子树寻找{cur = cur->_right;}else if(key < cur->_key)   //如果key比根节点的值小，则去左子树寻找{cur = cur->_left;}else{return true;       //相等，返回true}} return false;          //出循环，还没找到，返回false}}
1.2.2二叉搜索树的插入（递归实现看最后总代码）

插入思路分析：

a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

图解：
在这里插入图片描述

代码实现：

	bool insert(const K& key){if (_root == nullptr)    //如果为空树，直接插入{Node* newNode = new Node(key);    //new一个节点_root = newNode;                   //链接return true;      //插入成功，返回true}else{Node* parent = nullptr;     //因为要链接，所以需要记录父亲Node* cur = _root;   while (cur)                   //while循环和find函数类似，目的找到合适位置插入{if (key > cur->_key){parent = cur;    //记录父节点cur = cur->_right;}else if(key < cur->_key){parent = cur;cur = cur->_left;}else{return false;    //搜索二叉树里面的值不能重复,如果已经存在，则返回false}}//cur空，结束循环，代表找到位置了Node* newNode = new Node(key);      //new节点if (key < parent->_key)            parent->_left = newNode;if (key > parent->_key)          //判断是链接到父亲的左还是右parent->_right = newNode;return true;}}
1.2.3二叉搜索树的删除（递归实现看最后总代码）

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：

a. 要删除的结点无孩子结点 //直接删除
b. 要删除的结点只有左孩子结点 //托孤
c. 要删除的结点只有右孩子结点 //托孤
d. 要删除的结点有左、右孩子结点 //替换法删除

看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：

情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题–替换法删除

托孤发删除的原理:
假设我们要删除【图一】的22，它只有一个孩子，就可以使用托孤的方法，直接让父节点（15）指向它的孩子（17）；
该方法也可以在删除没有孩子的节点上使用（将它看作有一个为NULL的孩子即可），例如下【图二】，假设删除17；
在这里插入图片描述

在这里插入图片描述

替换法删除的原理：
方法作用于有两个孩子的节点:

a，找到该节点左子树的最右节点（即左子树最大的节点）或则右子树的最左节点（即右子树最小值）；
b，然后将待删除节点的值与找到的最大（或最小）节点的值进行交换，转化为删除找到的这个节点；
c，最后用上面的托孤的方法删除该节点

在这里插入图片描述

代码实现：

	bool Erase(const K& key){if (_root == nullptr)     //如果树为空，直接返回return false;else                     //树不为空{Node* parent = _root;Node* cur = _root;       while (cur)                 //while循环，先找到待删除节点以及记录它父节点{                           //该循环体与find和insert类似if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key) {parent = cur;cur = cur->_left;}else                             //找到该节点了，开始删除{//1.只有一个孩子或则没有孩子Node* del = cur;                    //保存要删除的这个节点，防止等下托孤后该节点找不到if (!(cur->_left && cur->_right))    //两个孩子都存在的逻反就是有一个孩子或则没有孩子{if (cur == _root)       //这里，判断如果该节点是头节点，直接将头节点置空，返回{_root = nullptr;         }if (parent->_left == cur)     //该删除节点为父节点的左子树，则将它的孩子连接到它父节点的左子树上{if (cur->_left)           //判断孩子是待删除节点的哪个孩子{parent->_left = cur->_left;}else{parent->_left = cur->_right;}return true;}else                        //和上面一样{if (cur->_left){parent->_right = cur->_left;}else{parent->_right = cur->_right;}return true;}}//2.待删除节点有两个孩子else                            //这里实现的是替换法中找右子树中最小的节点{Node* rightMinparent = cur;        //记录最小节点的父亲，因为等下需要托孤Node* rightMin = cur->_right;      //记录最小节点while (rightMin->_left){rightMinparent = rightMin;rightMin = rightMin->_left;}//到这里说明中找到了右树的最小节点swap(rightMin->_key, cur->_key);    //交换最小节点与待删除节点的值，转换为删除这个最小节点if (rightMinparent->_left==rightMin)     //下面的逻辑与上面的托孤一样{rightMinparent->_left = rightMin->_right;}else{rightMinparent->_right = rightMin->_right;}delete rightMin;                      //最后删除}return true;}}return false;}}
总代码（含递归实现）：
#pragma once
#include<iostream>using namespace std;template<class K>
struct Binary_Serach_TreeNode
{typedef Binary_Serach_TreeNode<K> Node;Node* _left;Node* _right;K _key;Binary_Serach_TreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}};template<class K>
class B_S_Tree
{
public:typedef Binary_Serach_TreeNode<K> Node;//B_S_Tree() = default;    //强制生成默认构造B_S_Tree():_root(nullptr){}B_S_Tree(B_S_Tree<K>& bst){_root = copy(bst._root);}Node* copy(Node* root){if (root == nullptr)return nullptr;Node* newroot = new Node(root->_key);newroot->_left = copy(root->_left);newroot->_right = copy(root->_right);return newroot;}B_S_Tree<K>& operator=(B_S_Tree<K> bst){std::swap(bst._root, _root);return *this;}bool insert(const K& key){if (_root == nullptr)    //如果为空树，直接插入{Node* newNode = new Node(key);    //new一个节点_root = newNode;                   //链接return true;      //插入成功，返回true}else{Node* parent = nullptr;     //因为要链接，所以需要记录父亲Node* cur = _root;   while (cur)                   //while循环和find函数类似，目的找到合适位置插入{if (key > cur->_key){parent = cur;    //记录父节点cur = cur->_right;}else if(key < cur->_key){parent = cur;cur = cur->_left;}else{return false;    //搜索二叉树里面的值不能重复,如果已经存在，则返回false}}//cur空，结束循环，代表找到位置了Node* newNode = new Node(key);      //new节点if (key < parent->_key)            parent->_left = newNode;if (key > parent->_key)          //判断是链接到父亲的左还是右parent->_right = newNode;return true;}}bool Erase(const K& key){if (_root == nullptr)     //如果树为空，直接返回return false;else                     //树不为空{Node* parent = _root;Node* cur = _root;       while (cur)                 //while循环，先找到待删除节点以及记录它父节点{                           //该循环体与find和insert类似if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key) {parent = cur;cur = cur->_left;}else                             //找到该节点了，开始删除{//1.只有一个孩子或则没有孩子Node* del = cur;                    //保存要删除的这个节点，防止等下托孤后该节点找不到if (!(cur->_left && cur->_right))    //两个孩子都存在的逻反就是有一个孩子或则没有孩子{if (cur == _root)       //这里，判断如果该节点是头节点，直接将头节点置空，返回{_root = nullptr;         }if (parent->_left == cur)     //该删除节点为父节点的左子树，则将它的孩子连接到它父节点的左子树上{if (cur->_left)           //判断孩子是待删除节点的哪个孩子{parent->_left = cur->_left;}else{parent->_left = cur->_right;}return true;}else                        //和上面一样{if (cur->_left){parent->_right = cur->_left;}else{parent->_right = cur->_right;}return true;}}//2.待删除节点有两个孩子else                            //这里实现的是替换法中找右子树中最小的节点{Node* rightMinparent = cur;        //记录最小节点的父亲，因为等下需要托孤Node* rightMin = cur->_right;      //记录最小节点while (rightMin->_left){rightMinparent = rightMin;rightMin = rightMin->_left;}//到这里说明中找到了右树的最小节点swap(rightMin->_key, cur->_key);    //交换最小节点与待删除节点的值，转换为删除这个最小节点if (rightMinparent->_left==rightMin)     //下面的逻辑与上面的托孤一样{rightMinparent->_left = rightMin->_right;}else{rightMinparent->_right = rightMin->_right;}delete rightMin;                      //最后删除}return true;}}return false;}}bool Find(const K& key)       //key为寻找关键字{if (_root == nullptr)    //如果为空，直接返回{return false;}else                      {Node* cur = _root;         //用cur迭代寻找while (cur){if (key > cur->_key)      //如果key比根节点的值大，则去右子树寻找{cur = cur->_right;}else if(key < cur->_key)   //如果key比根节点的值小，则去左子树寻找{cur = cur->_left;}else{return true;       //相等，返回true}} return false;          //出循环，还没找到，返回false}}bool insertR(const K& key){return _inserR(_root, key);}bool  FindR(const K& key){return _FindR(_root,key);}bool  EraseR(const K& key){return _EraseR(_root, key);}void OrdPrint(){_OrdPrint(_root);cout << endl;}~B_S_Tree(){//_Destory(_root);}
private:void _OrdPrint(Node* root){if (root == nullptr)return;_OrdPrint(root->_left);cout << root->_key <<' ';_OrdPrint(root->_right);}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);elsereturn true;}bool _inserR(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}if (key < root->_key)return _inserR(root->_left, key);else if (key > root->_key)return _inserR(root->_right, key);elsereturn false;}bool _EraseR(Node*& root,const K&  key){if (root == nullptr)return false;if (key < root->_key)_FindR(root->_left, key);else if (key < root->_key)_FindR(root->_right, key);else{Node* del = root;if (root->_left==nullptr)root = root->_right;else if(root->_right==nullptr)root = root->_left;else{Node* rightMinparent = root;Node* rightMin = root->_right;while (rightMin->_left){rightMinparent = rightMin;rightMin = rightMin->_left;}swap(root->_key, rightMin->_key);return _EraseR(root->_right, key);}delete del;return true;}}void _destory(Node* root){if (root == nullptr)return;else{_destory(root->_left);_destory(root->_right);delete root;}}private:Node* _root;
};

二. 二叉搜索树的应用

应用一：
K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

应用二：
KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。

三.二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)【如图左】，其平均比较次数为：log_2 N
最差情况下，二叉搜索树退化为单支树(或者类似单支)【如图右】，其平均比较次数为：N

在这里插入图片描述
本章完~看完觉得对你有用就点个赞吧！

这篇关于二叉搜索树（二叉排序树，二叉查找树）（附图详解+代码实现+应用分析）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/846102。

相关文章

Python中的魔术方法__new__详解

Python中的魔术方法__new__详解

《Python中的魔术方法__new__详解》：本文主要介绍Python中的魔术方法__new__的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、核心意义与机制1.1 构造过程原理1.2 与 __init__ 对比二、核心功能解析2.1 核心能力2.2
阅读更多...
在PyCharm中安装PyTorch、torchvision和OpenCV详解

在PyCharm中安装PyTorch、torchvision和OpenCV详解

《在PyCharm中安装PyTorch、torchvision和OpenCV详解》：本文主要介绍在PyCharm中安装PyTorch、torchvision和OpenCV方式,具有很好的参考价值,... 目录PyCharm安装PyTorch、torchvision和OpenCV安装python安装PyTor
阅读更多...
openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
MySQL 分区与分库分表策略应用小结

MySQL 分区与分库分表策略应用小结

《MySQL分区与分库分表策略应用小结》在大数据量、复杂查询和高并发的应用场景下,单一数据库往往难以满足性能和扩展性的要求,本文将详细介绍这两种策略的基本概念、实现方法及优缺点,并通过实际案例展示如... 目录mysql 分区与分库分表策略1. 数据库水平拆分的背景2. MySQL 分区策略2.1 分区概念
阅读更多...
SpringBoot条件注解核心作用与使用场景详解

SpringBoot条件注解核心作用与使用场景详解

《SpringBoot条件注解核心作用与使用场景详解》SpringBoot的条件注解为开发者提供了强大的动态配置能力,理解其原理和适用场景是构建灵活、可扩展应用的关键,本文将系统梳理所有常用的条件注... 目录引言一、条件注解的核心机制二、SpringBoot内置条件注解详解1、@ConditionalOn
阅读更多...
OpenCV图像形态学的实现

OpenCV图像形态学的实现

《OpenCV图像形态学的实现》本文主要介绍了OpenCV图像形态学的实现,包括腐蚀、膨胀、开运算、闭运算、梯度运算、顶帽运算和黑帽运算,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起... 目录一、图像形态学简介二、腐蚀（Erosion）1. 原理2. OpenCV 实现三、膨胀China编程（
阅读更多...
通过Spring层面进行事务回滚的实现

通过Spring层面进行事务回滚的实现

《通过Spring层面进行事务回滚的实现》本文主要介绍了通过Spring层面进行事务回滚的实现,包括声明式事务和编程式事务,具有一定的参考价值,感兴趣的可以了解一下... 目录声明式事务回滚：1. 基础注解配置2. 指定回滚异常类型3. ​不回滚特殊场景编程式事务回滚：1. ​使用 TransactionT
阅读更多...
Android实现打开本地pdf文件的两种方式

Android实现打开本地pdf文件的两种方式

《Android实现打开本地pdf文件的两种方式》在现代应用中,PDF格式因其跨平台、稳定性好、展示内容一致等特点,在Android平台上,如何高效地打开本地PDF文件,不仅关系到用户体验,也直接影响... 目录一、项目概述二、相关知识2.1 PDF文件基本概述2.2 android 文件访问与存储权限2.
阅读更多...
使用Python实现全能手机虚拟键盘的示例代码

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景：会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作？今天我要分享的Pyth... 目录一、项目概述：不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求
阅读更多...
Spring Shell 命令行实现交互式Shell应用开发

Spring Shell 命令行实现交互式Shell应用开发

《SpringShell命令行实现交互式Shell应用开发》本文主要介绍了SpringShell命令行实现交互式Shell应用开发,能够帮助开发者快速构建功能丰富的命令行应用程序,具有一定的参考价... 目录引言一、Spring Shell概述二、创建命令类三、命令参数处理四、命令分组与帮助系统五、自定义S
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2