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

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。

相关文章

MySQL 8 中的一个强大功能 JSON_TABLE示例详解

MySQL 8 中的一个强大功能 JSON_TABLE示例详解

《MySQL8中的一个强大功能JSON_TABLE示例详解》JSON_TABLE是MySQL8中引入的一个强大功能,它允许用户将JSON数据转换为关系表格式,从而可以更方便地在SQL查询中处理J... 目录基本语法示例示例查询解释应用场景不适用场景1. ‌jsON 数据结构过于复杂或动态变化‌2. ‌性能要
阅读更多...
Python实现终端清屏的几种方式详解

Python实现终端清屏的几种方式详解

《Python实现终端清屏的几种方式详解》在使用Python进行终端交互式编程时,我们经常需要清空当前终端屏幕的内容,本文为大家整理了几种常见的实现方法,有需要的小伙伴可以参考下... 目录方法一：使用 `os` 模块调用系统命令方法二：使用 `subprocess` 模块执行命令方法三：打印多个换行符模拟
阅读更多...
SpringBoot+EasyPOI轻松实现Excel和Word导出PDF

SpringBoot+EasyPOI轻松实现Excel和Word导出PDF

《SpringBoot+EasyPOI轻松实现Excel和Word导出PDF》在企业级开发中,将Excel和Word文档导出为PDF是常见需求,本文将结合​​EasyPOI和​​Aspose系列工具实... 目录一、环境准备与依赖配置1.1 方案选型1.2 依赖配置（商业库方案）二、Excel 导出 PDF
阅读更多...
Python实现MQTT通信的示例代码

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器（Broker）‌‌3. pytho
阅读更多...
MySQL字符串常用函数详解

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、
阅读更多...
Java中Arrays类和Collections类常用方法示例详解

Java中Arrays类和Collections类常用方法示例详解

《Java中Arrays类和Collections类常用方法示例详解》本文总结了Java中Arrays和Collections类的常用方法,涵盖数组填充、排序、搜索、复制、列表转换等操作,帮助开发者高... 目录Arrays.fill()相关用法Arrays.toString()Arrays.sort()A
阅读更多...
使用zip4j实现Java中的ZIP文件加密压缩的操作方法

使用zip4j实现Java中的ZIP文件加密压缩的操作方法

《使用zip4j实现Java中的ZIP文件加密压缩的操作方法》本文介绍如何通过Maven集成zip4j1.3.2库创建带密码保护的ZIP文件,涵盖依赖配置、代码示例及加密原理,确保数据安全性,感兴趣的... 目录1. zip4j库介绍和版本1.1 zip4j库概述1.2 zip4j的版本演变1.3 zip4
阅读更多...
Python 字典 (Dictionary)使用详解

Python 字典 (Dictionary)使用详解

《Python字典(Dictionary)使用详解》字典是python中最重要,最常用的数据结构之一,它提供了高效的键值对存储和查找能力,：本文主要介绍Python字典(Dictionary)... 目录字典1.基本特性2.创建字典3.访问元素4.修改字典5.删除元素6.字典遍历7.字典的高级特性默认字典
阅读更多...
MySQL进行数据库审计的详细步骤和示例代码

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java
阅读更多...
MySQL 主从复制部署及验证(示例详解)

MySQL 主从复制部署及验证(示例详解)

《MySQL主从复制部署及验证(示例详解)》本文介绍MySQL主从复制部署步骤及学校管理数据库创建脚本,包含表结构设计、示例数据插入和查询语句,用于验证主从同步功能,感兴趣的朋友一起看看吧... 目录mysql 主从复制部署指南部署步骤1.环境准备2. 主服务器配置3. 创建复制用户4. 获取主服务器状态5
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2