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

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管理工具之conda安装部署及使用详解

python管理工具之conda安装部署及使用详解

《python管理工具之conda安装部署及使用详解》这篇文章详细介绍了如何安装和使用conda来管理Python环境,它涵盖了从安装部署、镜像源配置到具体的conda使用方法,包括创建、激活、安装包... 目录pytpshheraerUhon管理工具：conda部署+使用一、安装部署1、 下载2、 安装3
阅读更多...
详解Java如何向http/https接口发出请求

详解Java如何向http/https接口发出请求

《详解Java如何向http/https接口发出请求》这篇文章主要为大家详细介绍了Java如何实现向http/https接口发出请求,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 用Java发送web请求所用到的包都在java.net下，在具体使用时可以用如下代码，你可以把它封装成一
阅读更多...
使用Python实现在Word中添加或删除超链接

使用Python实现在Word中添加或删除超链接

《使用Python实现在Word中添加或删除超链接》在Word文档中,超链接是一种将文本或图像连接到其他文档、网页或同一文档中不同部分的功能,本文将为大家介绍一下Python如何实现在Word中添加或... 在Word文档中，超链接是一种将文本或图像连接到其他文档、网页或同一文档中不同部分的功能。通过添加超
阅读更多...
windos server2022里的DFS配置的实现

windos server2022里的DFS配置的实现

《windosserver2022里的DFS配置的实现》DFS是WindowsServer操作系统提供的一种功能,用于在多台服务器上集中管理共享文件夹和文件的分布式存储解决方案,本文就来介绍一下wi... 目录什么是DFS？优势：应用场景：DFS配置步骤什么是DFS？DFS指的是分布式文件系统（Distr
阅读更多...
NFS实现多服务器文件的共享的方法步骤

NFS实现多服务器文件的共享的方法步骤

《NFS实现多服务器文件的共享的方法步骤》NFS允许网络中的计算机之间共享资源,客户端可以透明地读写远端NFS服务器上的文件,本文就来介绍一下NFS实现多服务器文件的共享的方法步骤,感兴趣的可以了解一... 目录一、简介二、部署1、准备1、服务端和客户端：安装nfs-utils2、服务端：创建共享目录3、服
阅读更多...
JAVA系统中Spring Boot应用程序的配置文件application.yml使用详解

JAVA系统中Spring Boot应用程序的配置文件application.yml使用详解

《JAVA系统中SpringBoot应用程序的配置文件application.yml使用详解》：本文主要介绍JAVA系统中SpringBoot应用程序的配置文件application.yml的... 目录文件路径文件内容解释1. Server 配置2. Spring 配置3. Logging 配置4. Ma
阅读更多...
C#使用yield关键字实现提升迭代性能与效率

C#使用yield关键字实现提升迭代性能与效率

《C#使用yield关键字实现提升迭代性能与效率》yield关键字在C#中简化了数据迭代的方式,实现了按需生成数据,自动维护迭代状态,本文主要来聊聊如何使用yield关键字实现提升迭代性能与效率,感兴... 目录前言传统迭代和yield迭代方式对比yield延迟加载按需获取数据yield break显式示迭
阅读更多...
Python实现高效地读写大型文件

Python实现高效地读写大型文件

《Python实现高效地读写大型文件》Python如何读写的是大型文件,有没有什么方法来提高效率呢,这篇文章就来和大家聊聊如何在Python中高效地读写大型文件,需要的可以了解下... 目录一、逐行读取大型文件二、分块读取大型文件三、使用 mmap 模块进行内存映射文件操作（适用于大文件）四、使用 pand
阅读更多...
python实现pdf转word和excel的示例代码

python实现pdf转word和excel的示例代码

《python实现pdf转word和excel的示例代码》本文主要介绍了python实现pdf转word和excel的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、引言二、python编程1，PDF转Word2，PDF转Excel三、前端页面效果展示总结一
阅读更多...
在MyBatis的XML映射文件中＜trim＞元素所有场景下的完整使用示例代码

在MyBatis的XML映射文件中＜trim＞元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中＜trim＞元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中，<trim>元素用于动态地添加SQL语句的一部分，例如SET或W
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2