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

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。

相关文章

C++使用栈实现括号匹配的代码详解

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中，括号匹配是一个常见问题，尤其是在
阅读更多...
Java实现检查多个时间段是否有重合

Java实现检查多个时间段是否有重合

《Java实现检查多个时间段是否有重合》这篇文章主要为大家详细介绍了如何使用Java实现检查多个时间段是否有重合,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录流程概述步骤详解China编程步骤1：定义时间段类步骤2：添加时间段步骤3：检查时间段是否有重合步骤4：输出结果示例代码结语作
阅读更多...
使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
Java覆盖第三方jar包中的某一个类的实现方法

Java覆盖第三方jar包中的某一个类的实现方法

《Java覆盖第三方jar包中的某一个类的实现方法》在我们日常的开发中,经常需要使用第三方的jar包,有时候我们会发现第三方的jar包中的某一个类有问题,或者我们需要定制化修改其中的逻辑,那么应该如何... 目录一、需求描述二、示例描述三、操作步骤四、验证结果五、实现原理一、需求描述需求描述如下：需要在
阅读更多...
Debezium 与 Apache Kafka 的集成方式步骤详解

Debezium 与 Apache Kafka 的集成方式步骤详解

《Debezium与ApacheKafka的集成方式步骤详解》本文详细介绍了如何将Debezium与ApacheKafka集成,包括集成概述、步骤、注意事项等,通过KafkaConnect,D... 目录一、集成概述二、集成步骤1. 准备 Kafka 环境2. 配置 Kafka Connect3. 安装 D
阅读更多...
Java中ArrayList和LinkedList有什么区别举例详解

Java中ArrayList和LinkedList有什么区别举例详解

《Java中ArrayList和LinkedList有什么区别举例详解》：本文主要介绍Java中ArrayList和LinkedList区别的相关资料,包括数据结构特性、核心操作性能、内存与GC影... 目录一、底层数据结构二、核心操作性能对比三、内存与 GC 影响四、扩容机制五、线程安全与并发方案六、工程
阅读更多...
如何使用Java实现请求deepseek

如何使用Java实现请求deepseek

《如何使用Java实现请求deepseek》这篇文章主要为大家详细介绍了如何使用Java实现请求deepseek功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1.deepseek的api创建2.Java实现请求deepseek2.1 pom文件2.2 json转化文件2.2
阅读更多...
Java调用DeepSeek API的最佳实践及详细代码示例

Java调用DeepSeek API的最佳实践及详细代码示例

《Java调用DeepSeekAPI的最佳实践及详细代码示例》：本文主要介绍如何使用Java调用DeepSeekAPI,包括获取API密钥、添加HTTP客户端依赖、创建HTTP请求、处理响应、... 目录1. 获取API密钥2. 添加HTTP客户端依赖3. 创建HTTP请求4. 处理响应5. 错误处理6.
阅读更多...
python使用fastapi实现多语言国际化的操作指南

python使用fastapi实现多语言国际化的操作指南

《python使用fastapi实现多语言国际化的操作指南》本文介绍了使用Python和FastAPI实现多语言国际化的操作指南,包括多语言架构技术栈、翻译管理、前端本地化、语言切换机制以及常见陷阱和... 目录多语言国际化实现指南项目多语言架构技术栈目录结构翻译工作流1. 翻译数据存储2. 翻译生成脚本
阅读更多...
Spring Cloud LoadBalancer 负载均衡详解

Spring Cloud LoadBalancer 负载均衡详解

《SpringCloudLoadBalancer负载均衡详解》本文介绍了如何在SpringCloud中使用SpringCloudLoadBalancer实现客户端负载均衡,并详细讲解了轮询策略和... 目录1. 在 idea 上运行多个服务2. 问题引入3. 负载均衡4. Spring Cloud Load
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2