当前位置: 首页 > news >正文

数据结构-考研难点代码突破(C++实现树型查找-二叉搜索树(二叉排序树))

文章目录

  • 1.二叉搜索树基本操作
    • 二叉搜索树的效率分析
  • 2. C++实现

1.二叉搜索树基本操作

二叉排序树是具有下列特性的二叉树:

  1. 若左子树非空,则左子树上所有结点的值均小于根结点的值。
  2. 若右子树非空,则右子树上所有结点的值均大于根结点的值。
  3. 左、右子树也分别是一棵二叉排序树

根据二叉排序树的定义,左子树结点值< 根结点值< 右子树结点值。
所以对二叉排序树进行中序遍历,可以得到一个递增的有序序列。

二叉排序树的搜索

  1. 从根结点开始,沿某个分支逐层向下比较的过程。
  2. 若二叉排序树非空,先将给定值与根结点的关键字比较,若相等,则查找成功
  3. 若不等,如果小于根结点的关键字,则在根结点的左子树上查找,否则在根结点的右子树上查找。

这个过程可以通过递归或者非递归实现实现

二叉排序树的插入

  1. 若原二叉排序树为空,则直接插入结点
  2. 若关键字k小于根结点值,则插入到左子树,若关键字k大于根结点值,则插入到右子树。

插入的结点一定是一个新添加的叶结点,且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子.

二叉排序树的删除

在二叉排序树中删除一个结点时,不能把以该结点为根的子树上的结点都删除,必须先把被删除结点从存储二叉排序树的链表上摘下,将因删除结点而断开的二叉链表重新链接起来,同时确保二叉排序树的性质不会丢失。删除操作的实现过程按3种情况来处理

  1. 若被删除结点z是叶结点,则直接删除,不会破坏二叉排序树的性质

  2. 若结点z只有一棵左子树或右子树,则让z的子树成为z父结点的子树,替代z的位置

  3. 若结点z有左、右两棵子树,则令z的直接后继(或直接前驱)替代z,然后从二叉排序树中删去这个直接后继(或直接前驱),这样就转换成了第一或第二种情况。可以使用递归解决这个问题。

    直接后继:节点右子树中最左节点(右子树最小节点)

    删除流程图:具体看代码流程
    在这里插入图片描述

二叉搜索树的效率分析

二叉排序树的查找效率,主要取决于树的高度。

  1. 若二叉排序树的左、右子树的高度之差的绝对值不超过1(这样的二叉排序树称为平衡二叉树)它的平均查找长度为O(logN)

  2. 若二叉排序树是一个只有右(左)孩子的单支树(类似于有序的单链表),则其平均查找长度为O(N)

在这里插入图片描述
a图的平均搜索成功长度ASL:类似折半查找(1x1 + 2x2+……h×2h-1) )(每层的节点不一定放满,需要针对题目灵活处理)
(1×1+2×2+3×4+4×3)÷10=2.9

b图的平均搜索成功长度ASL:(1+10)/2=5.5
因为此时搜索二叉树由树型退化为线型,平均搜索长度为(n+1)/2

二叉排序树与二分查找相似。就平均时间性能而言,二叉排序树上的查找和二分查找差不多。

但二分查找的判定树唯一,而二叉排序树的查找不唯一,相同的关键字其插入顺序不同可能生成不同的二叉排序树。

二叉排序树与二分搜索:

  1. 二叉排序树无须移动结点,只需修改指针即可完成插入和删除操作, 平均执行时间为O(logN)
  2. 二分查找的对象是有序顺序表,若有插入和删除结点的操作,所花的代价是O(n)。
  3. 当有序表是静态查找表时,宜用顺序表作为其存储结构,采用二分查找实现其查找操作;若有序表是动态查找表,则应选择二叉排序树作为其逻辑结构.

2. C++实现

// 二叉搜索树头文件实现
#include <iostream>
#include <vector>
#include <algorithm>struct TreeNode
{int _val;TreeNode *_left;TreeNode *_right;TreeNode(int val) : _val(val), _left(nullptr), _right(nullptr) {}
};class SearchTree
{
private:TreeNode *root = nullptr;/*** @brief 在二叉搜索树中查找节点值为val的节点** @param val 查找节点的值* @param node 如果找到了这个节点,node就是这个节点的地址,否则为null* @param part part这个节点的父亲,如果这个节点为null,这个参数输出null*/void _find(int val, TreeNode *&node, TreeNode *&part){TreeNode *ptr = root;TreeNode *prev = nullptr;while (ptr != nullptr){if (ptr->_val == val){node = ptr;break;}else if (ptr->_val > val){prev = ptr;ptr = ptr->_left;}else{prev = ptr;ptr = ptr->_right;}}node = ptr;part = prev;}bool _erase(int val, TreeNode *&node){if (node == nullptr){return false;}else{if (node->_val > val){_erase(val, node->_left);}else if (node->_val < val){_erase(val, node->_right);}else{if (node->_left == nullptr){TreeNode *del = node;node = node->_right;delete del;}else if (node->_right == nullptr){TreeNode *del = node;node = node->_left;delete del;}else{// 找要删除节点的后继TreeNode *right_min_node = node->_right;while (right_min_node->_left != nullptr){right_min_node = right_min_node->_left;}// 记录right_min_node这个节点的值,吧这个节点的值和node节点交换,在删除right_min_node这个节点即可// right_min_node这个节点的左子树一定为空,在上面顶点流程会处理int tmp = right_min_node->_val;_erase(tmp, node->_right);node->_val = tmp;}}return true;}}// 判断一棵树是否是二叉搜索树,检查每个节点是否满足节点值的取值范围bool _isSearchTree(TreeNode *node, int min, int max){if (node == nullptr)return true;if (node->_val < min || node->_val > max){return false;}return _isSearchTree(node->_left, min, node->_val - 1) && _isSearchTree(node->_right, node->_val + 1, max);}void _display_inorder(TreeNode *node){if (node == nullptr)return;_display_inorder(node->_left);std::cout << node->_val << " ";_display_inorder(node->_right);}int _max(){TreeNode *node = root;while (node->_right != nullptr){node = node->_right;}return node->_val;}int _min(){TreeNode *node = root;while (node->_left != nullptr){node = node->_left;}return node->_val;}public:SearchTree() = default;SearchTree(const std::vector<int> &buff){for (int i = 0; i < buff.size(); i++){insert(buff[i]);}}// 不允许重复插入相同的值bool insert(int val){if (root == nullptr){root = new TreeNode(val);return true;}else{TreeNode *pos = nullptr;TreeNode *prev = nullptr;_find(val, pos, prev);if (pos != nullptr){// 之前插入过,值重复return false;}else{// pos==nullptr;if (prev->_val > val){prev->_left = new TreeNode(val);}else{prev->_right = new TreeNode(val);}return true;}}}// 查找节点值为val的节点bool find(int val){TreeNode *node;TreeNode *part;_find(val, node, part);return node != nullptr;}// 删除搜索二叉树节点bool erase(int val){return _erase(val, root);}// 判断这颗树是否为二叉搜索树bool isSearchTree(){return _isSearchTree(root, _min(), _max());}// 中序遍历二叉搜索树void inorder(){_display_inorder(root);std::cout << "\n";}
};

测试代码:

#include "SearchTree.h"
#include <time.h>using namespace std;#define TIMES 10int main(int argc, char const *argv[])
{srand((unsigned int)time(0));// vector<int> ret = {1, 2, 3};vector<int> ret;for (int i = 0; i < TIMES; i++){ret.push_back(rand() % 100);}SearchTree tree(ret);tree.inorder();tree.insert(40);tree.inorder();cout << tree.isSearchTree() << endl;tree.insert(1);tree.erase(40);tree.inorder();cout << tree.isSearchTree() << endl;return 0;
}

在这里插入图片描述

相关文章:

数据结构-考研难点代码突破(C++实现树型查找-二叉搜索树(二叉排序树))

文章目录1.二叉搜索树基本操作二叉搜索树的效率分析2. C实现1.二叉搜索树基本操作 二叉排序树是具有下列特性的二叉树&#xff1a; 若左子树非空&#xff0c;则左子树上所有结点的值均小于根结点的值。若右子树非空&#xff0c;则右子树上所有结点的值均大于根结点的值。左、…...

emqx异常处理

启动异常 通过解压tar压缩包安装后通过 ./bin/emqx start 启动报错 WARNING: Default (insecure) Erlang cookie is in use. WARNING: Configure node.cookie in /opt/emqx/etc/emqx.conf or override from environment variable EMQX_NODE__COOKIE NOTE: Use the same config…...

Web前端:开始学习ReactJS需要知道什么?

毫无疑问&#xff0c;ReactJS是前端开发者中最著名的库之一&#xff0c;它的受欢迎程度与日俱增。用ReactJS构建的网站看起来非常棒&#xff0c;大多数开发新手都被它吸引住了。然而&#xff0c;许多新人和有经验的开发人员在没有首先了解先决条件的情况下&#xff0c;就直接用…...

卡诺图化简

1.相关概念 最小项&#xff1a;函数的某个乘积项包含了函数的全部变量&#xff08;原变量或反变量的形式&#xff09;&#xff0c;且每个变量仅出现一次&#xff0c;则这个乘积项为该函数的一个标准积项。 最小项中的原变量记为1&#xff0c;反变量记为0&#xff0c;当变量顺序…...

带你了解软件测试是做什么的

软件测试是互联网技术中一门重要的学科&#xff0c;它是软件生命周期中不可或缺的一个环节&#xff0c;担负着把控、监督软件的质量的重任。 人才稀缺&#xff0c;对于求职者来说就意味着机会。但是很多想学习软件测试的人对这个学科并不了解&#xff0c;也不知道该如何学习&a…...

企业电子招投标采购系统源码之功能模块功能描述

​ 功能模块&#xff1a; 待办消息&#xff0c;招标公告&#xff0c;中标公告&#xff0c;信息发布 描述&#xff1a; 全过程数字化采购管理&#xff0c;打造从供应商管理到采购招投标、采购合同、采购执行的全过程数字化管理。通供应商门户具备内外协同的能力&#xff0c;为外…...

职场中的高手,是如何高质量解决问题?

职场总会遇见很多新问题&#xff0c;高手会从容应对&#xff0c;因为他们学习了一套通 用理论&#xff0c;可以处理工作当中的大部分内容&#xff0c;剩下的一部分能够用快速 提问的方式找到思路。 记得几年前有个同事 A&#xff0c;下午四点多项目突然丢过来一个活&#xff0c…...

报表生成工具Stimulsoft中的电子签名和 PDF 数字签名

Stimulsoft Reports 是一款报告编写器&#xff0c;主要用于在桌面和Web上从头开始创建任何复杂的报告。可以在大多数平台上轻松实现部署&#xff0c;如ASP.NET, WinForms, .NET Core, JavaScript, WPF, Angular, Blazor, PHP, Java等&#xff0c;在你的应用程序中嵌入报告设计器…...

【Hello Linux】Linux环境下写的第一个程序 -- 进度条

作者&#xff1a;小萌新 专栏&#xff1a;Linux 作者简介&#xff1a;大二学生 希望能和大家一起进步&#xff01; 本篇博客简介&#xff1a;写出Linux中的第一个小程序 进度条 进度条小程序行缓冲区概念\r 和 \n进度条代码和演示行缓冲区概念 我们首先用两段代码来感受下行缓…...

【基础】性能测试,从0到实战(手把手教,非常实用)

一、性能基础 什么是性能测试--->本质? 基于协议来模拟用户发送的请求&#xff08;业务模拟&#xff09;&#xff0c;对服务器形成一定负载。关注点&#xff1a;时间性能、空间性能与界面无关 性能测试分类 性能测试&#xff08;狭义&#xff09; 性能测试方法是通过模…...

07-Java异常分类以及处理机制

1.异常概念 Java标准库内建了一些通用的异常&#xff0c;这些类以Throwable为顶层父类。Throwable又派生出Error类和Exception类。 1.错误&#xff1a;是程序无法处理的错误&#xff0c;表示运行应用程序中较严重问题。大多数错误与代码编写者执行的操作无关&#xff0c;而表示…...

用到的C++的相关知识-----未完待续

文章目录前言一、vector函数的使用1.1 构造向量二、常用函数2.1 矩阵输出函数2.2 向量输出函数2.3 矩阵的使用2.4三、new的用法3.1 内存的四种分区3.2 new的作用3.33.4四、4.14.24.34.4总结前言 只是为方便学习&#xff0c;不做其他用途 一、vector函数的使用 有关的文章 C v…...

JavaScript刷LeetCode拿offer-贪心算法

前言 学习算法的时候&#xff0c;总会有一些让人生畏的名词&#xff0c;比方动态规划&#xff0c;贪心算法 等&#xff0c;听着就很难&#xff1b;而这一 part 就是为了攻破之前一直没有系统学习的 贪心算法&#xff1b; 有一说一&#xff0c;做了这些贪心题&#xff0c;其实…...

selenium

下载并安装selenium 安装&#xff1a;cmd中执行 pip install -i https://pypi.douban.com/simple selenium执行完成后 pip show selenium 可查看安装是否成功安装浏览器驱动&#xff0c;查看当前浏览器的版本选择合适的驱动并下载 chrome的链接&#xff1a;https://chromedrive…...

SpringMVC的视图

转发视图ThymeleafView若使用的视图技术为Thymeleaf&#xff0c;在SpringMVC的配置文件中配置了Thymeleaf的视图解析器&#xff0c;由此视图解析器解析之后所得到的是ThymeleafView。解析&#xff1a;当控制器方法中所设置的视图名称没有任何前缀时&#xff0c;此时的视图名称会…...

idea使用本地代码远程调试线上运行代码---windows环境

场景&#xff1a; 今天在书上看了一个代码远程调试的方法&#xff0c;自己本地验证了一下感觉十分不错&#xff01;&#xff01; windows环境&#xff1a; 启动测试jar包&#xff1a;platform-multiappcenter-base-app-1.0.0-SNAPSHOT.jar 测试工具&#xff1a;postman,idea 应…...

简单记录简单记录

目录1.注册Gmail2.注册ChatGPT3.验证“真人”使用4.开始使用1.注册Gmail 第一步先注册一个谷歌邮箱&#xff0c;你也可以使用微软账号&#xff0c;大部分人选择使用gmail。 申请谷歌邮箱 选择个人用途创建账号即可。 &#x1f4cc;温馨提示&#xff1a; 你直接使用guo内的网…...

源码系列 之 ThreadLocal

简介 ThreadLocal的作用是做数据隔离&#xff0c;存储的变量只属于当前线程&#xff0c;相当于当前线程的局部变量&#xff0c;多线程环境下&#xff0c;不会被别的线程访问与修改。常用于存储线程私有成员变量、上下文&#xff0c;和用于同一线程&#xff0c;不同层级方法间传…...

C语言入门(1)——特点及关键字

1、C特点及与Java区别 1.1、C特点 面向过程 一般用于嵌入式开发、编写最底层的程序、操作系统 可以直接操作内存 可以封装动态库 不容易跨平台 有指针 可以直接操作串口 线程更加灵活 和硬件打交道速度是最快的 1.2、和Java区别 C是C的增强版&#xff0c;增加了一些新的特性&…...

react中useEffect和useLayoutEffect的区别

布局上 useEffect在浏览器渲染完成后执行useLayoutEffect在DOM更新后执行 特点 useLayoutEffect 总是比 useEffect 先执行&#xff1b;useLayoutEffect与componentDidMount、componentDidUpdate调用时机相同&#xff0c;都是在DOM更新后&#xff0c;页面渲染前调用&#xff1…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...