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

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。

相关文章

Linux系统性能检测命令详解

Linux系统性能检测命令详解

《Linux系统性能检测命令详解》本文介绍了Linux系统常用的监控命令（如top、vmstat、iostat、htop等）及其参数功能,涵盖进程状态、内存使用、磁盘I/O、系统负载等多维度资源监控,... 目录toppsuptimevmstatIOStatiotopslabtophtopdstatnmon
阅读更多...
Android kotlin中 Channel 和 Flow 的区别和选择使用场景分析

Android kotlin中 Channel 和 Flow 的区别和选择使用场景分析

《Androidkotlin中Channel和Flow的区别和选择使用场景分析》Kotlin协程中,Flow是冷数据流,按需触发,适合响应式数据处理；Channel是热数据流,持续发送,支持... 目录一、基本概念界定FlowChannel二、核心特性对比数据生产触发条件生产与消费的关系背压处理机制生命周期
阅读更多...
java使用protobuf-maven-plugin的插件编译proto文件详解

java使用protobuf-maven-plugin的插件编译proto文件详解

《java使用protobuf-maven-plugin的插件编译proto文件详解》：本文主要介绍java使用protobuf-maven-plugin的插件编译proto文件,具有很好的参考价... 目录protobuf文件作为数据传输和存储的协议主要介绍在Java使用maven编译proto文件的插件
阅读更多...
Android ClassLoader加载机制详解

Android ClassLoader加载机制详解

《AndroidClassLoader加载机制详解》Android的ClassLoader负责加载.dex文件,基于双亲委派模型,支持热修复和插件化,需注意类冲突、内存泄漏和兼容性问题,本文给大家介... 目录一、ClassLoader概述1.1 类加载的基本概念1.2 android与Java Class
阅读更多...
c++ 类成员变量默认初始值的实现

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中，如果使用类成员变量时未给定其初始值，那么它将被
阅读更多...
Java中的数组与集合基本用法详解

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问
阅读更多...
SpringBoot线程池配置使用示例详解

SpringBoot线程池配置使用示例详解

《SpringBoot线程池配置使用示例详解》SpringBoot集成@Async注解,支持线程池参数配置（核心数、队列容量、拒绝策略等）及生命周期管理,结合监控与任务装饰器,提升异步处理效率与系统... 目录一、核心特性二、添加依赖三、参数详解四、配置线程池五、应用实践代码说明拒绝策略（Rejected
阅读更多...
Qt使用QSqlDatabase连接MySQL实现增删改查功能

Qt使用QSqlDatabase连接MySQL实现增删改查功能

《Qt使用QSqlDatabase连接MySQL实现增删改查功能》这篇文章主要为大家详细介绍了Qt如何使用QSqlDatabase连接MySQL实现增删改查功能,文中的示例代码讲解详细,感兴趣的小伙伴... 目录一、创建数据表二、连接mysql数据库三、封装成一个完整的轻量级 ORM 风格类3.1 表结构
阅读更多...
基于Python实现一个图片拆分工具

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片，默认是输出到项目文件夹中，可以自己选择其他的文件夹，选择需要拆分的行数和列数，可以通过
阅读更多...
一文详解SpringBoot中控制器的动态注册与卸载

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2