数据结构之判断二叉树是否为搜索树(C/C++实现)
文章目录
- 判断二叉树是否为搜索树
- 方法一:递归法
- 方法二:中序遍历法
- 总结
二叉树是一种非常常见的数据结构,它在计算机科学中有着广泛的应用。二叉搜索树(Binary Search Tree,简称BST)是二叉树的一种特殊形式,它具有以下性质:对于树中的任意一个节点,其左子树中的所有节点的值都小于该节点的值,其右子树中的所有节点的值都大于该节点的值。本文将详细介绍如何判断一个二叉树是否为搜索树,并提供C和C++的实现示例。
判断二叉树是否为搜索树
思路
判断一个二叉树是否为搜索树,可以通过以下两种方法:
- 递归法
- 中序遍历法
下面分别对这两种方法进行详细讲解。
方法一:递归法
递归法的核心思想是:对于树中的每个节点,检查其左子树的最大值是否小于当前节点的值,以及其右子树的最小值是否大于当前节点的值。
- 如果树为空,则它是二叉搜索树。
- 对于当前节点,递归地检查其左子树的最大值是否小于当前节点的值,同时检查其右子树的最小值是否大于当前节点的值。
- 如果上述两个条件均满足,则递归地检查左子树和右子树是否都是二叉搜索树。
C语言实现
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>typedef struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
} TreeNode;// 判断二叉树是否为搜索树
int isBSTUtil(struct TreeNode* node, int min, int max) {if (node == NULL) return 1;if (node->val < min || node->val > max) return 0;return isBSTUtil(node->left, min, node->val - 1) && isBSTUtil(node->right, node->val + 1, max);
}int isBST(TreeNode* root) {return isBSTUtil(root, INT_MIN, INT_MAX);
}// 创建新节点
TreeNode* newNode(int val) {TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));node->val = val;node->left = node->right = NULL;return node;
}int main() {TreeNode *root = newNode(4);root->left = newNode(2);root->right = newNode(5);root->left->left = newNode(1);root->left->right = newNode(3);if (isBST(root))printf("是搜索树\n");elseprintf("不是搜索树\n");return 0;
}
C++实现
#include <iostream>
#include <climits>using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};// 判断二叉树是否为搜索树
bool isBSTUtil(TreeNode* node, int min, int max) {if (node == NULL) return true;if (node->val < min || node->val > max) return false;return isBSTUtil(node->left, min, node->val - 1) && isBSTUtil(node->right, node->val + 1, max);
}bool isBST(TreeNode* root) {return isBSTUtil(root, INT_MIN, INT_MAX);
}int main() {TreeNode *root = new TreeNode(4);root->left = new TreeNode(2);root->right = new TreeNode(5);root->left->left = new TreeNode(1);root->left->right = new TreeNode(3);if (isBST(root))cout << "是搜索树" << endl;elsecout << "不是搜索树" << endl;return 0;
}
方法二:中序遍历法
中序遍历法的基本思想是:对二叉树进行中序遍历,遍历过程中检查当前节点的值是否大于前一个节点的值。如果是,则为搜索树;否则,不是搜索树。
C语言实现
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
} TreeNode;// 全局变量,用于记录前一个节点的值
int prev = INT_MIN;bool isBSTInorder(TreeNode* root) {if (root != NULL) {// 遍历左子树if (!isBSTInorder(root->left))return false;// 检查当前节点的值是否大于前一个节点的值if (root->val <= prev)return false;prev = root->val;// 遍历右子树return isBSTInorder(root->right);}return true;
}// 创建新节点
TreeNode* newNode(int val) {TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));node->val = val;node->left = node->right = NULL;return node;
}int main() {TreeNode *root = newNode(4);root->left = newNode(2);root->right = newNode(5);root->left->left = newNode(1);root->left->right = newNode(3);if (isBSTInorder(root))printf("是搜索树\n");elseprintf("不是搜索树\n");return 0;
}
C++实现
#include <iostream>
#include <climits>using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};// 全局变量,用于记录前一个节点的值
int prev = INT_MIN;bool isBSTInorder(TreeNode* root) {if (root == nullptr) return true;if (!isBSTInorder(root->left))return false;if (root->val <= prev)return false;prev = root->val;return isBSTInorder(root->right);
}int main() {TreeNode *root = new TreeNode(4);root->left = new TreeNode(2);root->right = new TreeNode(5);root->left->left = new TreeNode(1);root->left->right = new TreeNode(3);if (isBSTInorder(root))cout << "是搜索树" << endl;elsecout << "不是搜索树" << endl;return 0;
}
总结
本文详细介绍了如何判断一个二叉树是否为搜索树,包括递归法和中序遍历法两种实现方式。递归法通过比较节点与其子树的关系来判断,而中序遍历法则通过比较中序遍历的节点值来判断。两种方法各有优劣,可以根据实际需求选择合适的方法
相关文章:
数据结构之判断二叉树是否为搜索树(C/C++实现)
文章目录 判断二叉树是否为搜索树方法一:递归法方法二:中序遍历法总结 二叉树是一种非常常见的数据结构,它在计算机科学中有着广泛的应用。二叉搜索树(Binary Search Tree,简称BST)是二叉树的一种特殊形式&…...
golang长连接的误用
误用一:忘记读取响应的body 由于忘记读取响应的body导致创建大量处于TIME_WAIT状态的连接(同时产生大量处于transport.go的readLoop和writeLoop的协程) 在linux下运行下面的代码: package mainimport ("fmt""html"&qu…...
Springboot @Validate @Valid 基于复杂嵌套对象的参数校验示例
Springboot Validate Valid 基于复杂嵌套对象的参数校验示例 复杂对象 Data public class Object1 {Length(max 50,message "长度不能超过50位字符")NotBlank(message "名称不能为空")private String name;NotNull(message "不能为空")pri…...
算力共享下的,分级路由转发报文协议与通告
目录 网络双 SLA 约束 一、双SLA约束的定义与背景 二、双SLA约束的应用场景 三、双SLA约束的管理与实施 四、双SLA约束的优势与挑战 算力共享下的,分级路由转发报文协议与通告 基础设施即服务(IaaS)类 型算力资源 函数即服务(FaaS)类型算力服务 软件即服务(SaaS…...
滚动数组详解
滚动数组详解 何为滚动数组?滚动数组是如何优化空间的?交替滚动例题:来自某某轮廓线DP的题目 自我滚动(~~不如交替~~ 完结!!! ( 宇宙免责任书:我用的是C) 何为滚动数组? 什么是滚动…...
C 语言动态链表
线性结构->顺序存储->动态链表 一、理论部分 从起源中理解事物,就是从本质上理解事物。 -杜勒鲁奇 动态链表是通过结点(Node)的集合来非连续地存储数据,结点之间通过指针相互连接。 动态链表本身就是一种动态分配内存的…...
【Leetcode】二十、记忆化搜索:零钱兑换
文章目录 1、记忆化搜索2、leetcode509:斐波那契数列3、leetcode322:零钱兑换 1、记忆化搜索 也叫备忘录,即把已经计算过的结果存下来,下次再遇到,就直接取,不用重新计算。目的是以减少重复计算。 以前面提…...
json数据格式 继续学习
1.定义 轻量级的数据交互格式,可以按照json数据格式去组织和封装数据。 本质是一个带有特定格式的字符串。 2.功能 负责不同编程语言中的数据传递和交互。 3.json数据格式转化 """ 演示json数据和python字典之间的转换 """ impor…...
gradle 构建项目添加版本信息
gradle 构建项目添加版本信息,打包使用 spring boot 的打包插件 build.gradle 配置文件 bootJar {manifest {attributes(Project-Name: project.name,Project-Version: project.version,"project-Vendor": "XXX Corp","Built-By": &…...
vue3 学习笔记17 -- 基于el-menu封装菜单
vue3 学习笔记17 – 基于el-menu封装菜单 前提条件:组件创建完成 配置路由 // src/router/index.ts import { createRouter, createWebHashHistory } from vue-router import type { RouteRecordRaw } from vue-router export const Layout () > import(/lay…...
使用 Redis 实现验证码、token 的存储,用自定义拦截器完成用户认证、并使用双重拦截器解决 token 刷新的问题
可以看一下我以前做过的笔记:黑马点评 短信登录部分 基于session实现登录流程 1.发送验证码 用户在提交手机号后,会校验手机号是否合法,如果不合法,则要求用户重新输入手机号 如果手机号合法,后台此时生成对应的验…...
反转链表 - 力扣(LeetCode)C语言
206. 反转链表 - 力扣(LeetCode)( 点击前面链接即可查看题目) /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/ struct ListNode* reverseList(struct ListNode* head) {if(head NULL)…...
【Linux】进程间通信(1):进程通信概念与匿名管道
人与人之间是如何通信的?举个简单的例子,假如我是月老,我要为素不相识的但又渴望爱情的男女两方牵红线。我需要收集男方的信息告诉女方,收集女方的信息告诉男方,然后由男女双方来决定是否继续。对于他们而言࿰…...
Spring从入门到精通 01
文章目录 1. 依赖注入 (Dependency Injection, DI)2. 面向切面编程 (Aspect-Oriented Programming, AOP)3. 事务管理4. 简化 JDBC 开发5. 集成各种框架和技术6. 模块化和扩展性:主要的 Spring 模块:Core Container:AOP 模块:Data …...
C语言经典习题25
冒泡排序 对一维数组进行升序排序,然后在数组中输入20个数,将排序后的结果打印输出。 #include<stdio.h> #define N 20 int main() {int a[N];int i;for(i0;i<N;i) //初始化数组的数 {scanf("%d",&a);}for(i0;…...
2-47 基于matlab的时域有限差分法(FDTD法)拉夫等效原理进行时谐场外推
基于matlab的时域有限差分法(FDTD法)拉夫等效原理进行时谐场外推。外推边界距离吸收边界的距离、电磁场循环、傅立叶变换提起幅值和相位、各远区剖分点电场、方向系数计算等操作,得出可视化结果。程序已调通,可直接运行。 2-47 时域有限差分法(FDTD法) 拉…...
JupyterNotebook快捷键 自用
COMMAND MODE —————————————————————————————— Up Down cells的上下选择 A B 在上/下方插入cell C V X 复制/粘贴/剪切cell 双击D 删除所选cell Z 恢复被删除的cell 双击I Interrupt中断内核 Shift Enter 运行cell并选择下方 EDIT MODE ———…...
【我的OpenGL学习进阶之旅】讲一讲GL_TEXTURE_2D和GL_TEXTURE_EXTERNAL_OES的区别
在使用OpenGL ES进行图形图像开发时,我们常使用GL_TEXTURE_2D纹理类型,它提供了对标准2D图像的处理能力。这种纹理类型适用于大多数场景,可以用于展示静态贴图、渲染2D图形和进行图像处理等操作。 另外,有时我们需要从Camera或外部视频源读取数据帧并进行处理。这时,我们…...
Makefile 如何将生成的 .o 文件放到指定文件夹
研究了不少文章,我行通了一个,但是也不全,目前只能适用当前文件夹,如果源文件有子文件夹处理不了,还得继续研究。很多人说编译完把O文件移动走或者直接删掉。我想说的是不符合我的要求,移走或者删除O文件&a…...
聊一聊知识图谱结合RAG
因为最近在做一些关于提高公司内部使用的聊天机器人的回答准确率,并且最近微软官方也是开源了一下graphrag的源码,所以想聊一聊这个知识图谱结合rag。 rag在利用私有数据增强大模型回答的领域是一种比较典型的技术,也就是我们提出问题的时候&…...
Java面试锦集 之 一、Java基础(1)
一、Java基础(1) 1.final 关键字的作用? 修饰变量: 一旦被赋值,就不能再被修改,保证了变量值的稳定性。 例: final int NUMBER 10; //之后就不能再改变 NUMBER 的值了。修饰方法:…...
【leetcode】排列序列
给出集合 [1,2,3,...,n],其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况,并一一标记,当 n 3 时, 所有排列如下: "123""132""213""231""312""321" 给定…...
【Cesium开发实战】视频融合功能的实现,可自定义位置和视频路径
Cesium有很多很强大的功能,可以在地球上实现很多炫酷的3D效果。今天给大家分享一个视频融合功能。 1.话不多说,先展示 视频融合 2.设计思路 点击绘制开始在地图上绘制视频融合的点位,形成视频播放的区域,双击弹框输入名称和要播放视频的路径,即可对应区域播放对应视频,…...
【秋招笔试题】小明的美食
解析:思维题。由于需要互不相同,每次操作取重复的值与最大值相加即可,这样即可保证相加后不会新增重复的值。因此统计重复值即可。 #include <iostream> #include <algorithm>using namespace std; const int maxn 1e5 5; int…...
基于OpenLCA、GREET、R语言的生命周期评价方法、模型构建及典型案例应用
生命周期分析 (Life Cycle Analysis, LCA) 是评价一个产品系统生命周期整个阶段——从原材料的提取和加工,到产品生产、包装、市场营销、使用、再使用和产品维护,直至再循环和最终废物处置——的环境影响的工具。这种方法被认为是一种“从摇篮到坟墓”的…...
Linux操作系统 -socket网络通信
同一台主机之间的进程 1.古老的通信方式 无名管道 有名管道 信号 2、IPC对象通信 system v 消息队列 共享内存 信号量集 由于不同主机间进程通信 3.socket网络通信 国际网络体系结构: 七层OSI模型(理论…...
【苍穹】完美解决由于nginx更换端口号导致无法使用Websocket
一、报错信息 进行到websocket开发的过程中,遇到了前端报错,无法连接的提示: 经过F12排查很明显是服务端和客户端并没有连接成功。这里就涉及到之前的坑,现在需要填上了。 二、报错原因和推导 应该还记得刚开苍穹的第一天配置前…...
Qt中在pro中实现一些宏定义
在pro文件中利用 DEFINES 定义一些宏定义供工程整体使用。(和在cpp/h文件文件中定义使用有点类似)可以利用pro的中的宏定义实现一些全局的判断 pro中实现 #自定义一个变量 DEFINES "PI\"3.1415926\"" #自定义宏 DEFINES "T…...
bash XXX.sh文件和直接运行XXX.sh的区别
区别: bash XXX.sh 明确说明使用bash作为脚本的解释器不需要文件有执行权限 XXX.sh 需要指定相关解释器。如果第一行是#!/bin/bash则使用bash,如果是#!/bin/sh,则使用sh作为解释器需要有执行权限:通过chmod x 文件名指定 注意: #!是特殊标…...
【Python机器学习】k-近邻算法简单实践——改进约会网站的配对效果
需求背景: XX一直使用约会网站寻找适合自己的约会对象,ta会把人分为3种类型: 不喜欢、魅力一般、非常有魅力 对人分类轴,发现了对象样本的以下3种特征: 1、每年获得的飞行里程数 2、玩视频游戏所耗时间百分比 3、…...
vue3前端开发-小兔鲜项目-登录组件的开发表单验证
vue3前端开发-小兔鲜项目-登录组件的开发表单验证!现在开始写登录页面的内容。首先这一次完成基础的首页按钮点击跳转,以及初始化一些简单的表单的输入验证。后期还会继续完善内容。 1:首先还是准备好login页面的组件代码内容。 <script …...
Winform上位机TCP客户端/服务端、串口通信
Winform上位机TCP客户端/服务端、串口通信 背景 日常练习,着急换工作,心态都快乱了。 工具 串口调试助手 网络调试助手 代码 客户端 using Microsoft.VisualBasic.Logging; using System.Net.Sockets; using System.Text;namespace TcpClientDem…...
Linux基础复习(二)
前言 本文介绍了一下Linux命令行基本操作及网络配置 一、 命令行提示含义 [当前用户主机名 工作目录]$ 若当前用户是root,则最后一个字符为# 否则,最后一个字符为$ 二、常用Linux命令及其解释 修改主机名 一般在创建一台主机后会使用hostname相关命…...
nginx漏洞修复 ngx_http_mp4_module漏洞(CVE-2022-41742)【低可信】 nginx版本升级
风险描述: Nginx 是一款轻量级的Web服务器、反向代理服务器。 Nginx 的受影响版本中的ngx _http_mp4_module模块存在内存越界写入漏洞,当在配置中使用 mp4 directive时,攻击者可利用此漏洞使用使用ngx_http_mp4_module模块处理特制的音频或视…...
网格布局 HTML CSS grid layout demo
文章目录 页面效果代码 (HTML CSS)参考 页面效果 代码 (HTML CSS) <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"…...
Java算法之递归算法-如何计算阶乘的值
上一篇学了递归之后,练习一下递归算法。 题目:使用递归算法计算阶乘的值,也就是5!5*4*3*2*1,直接使用循环是非常简单的,这边练习一下递归算法。 先写一下两个条件 基线条件:等于1的时候返回1…...
python爬虫入门小案例
python爬虫 以下内容仅供学习交流,请勿用作其他用途,若涉及隐私和版权问题,请及时联系我删除 闲来无事,学了学爬虫小知识,适合入门,文笔拙劣,还望见谅 爬虫是什么: 爬取网页上的文字,图片,视频,音频 自动化操作浏览器,比如填写表单,打卡,提高工作效率爬虫的注意事项: 爬虫…...
【昇腾AI创新大赛集训营南京站学习笔记】-Ascend算子开发课程
昇腾AI创新大赛训练营 14:00-14:30 基础知识-理论课 一、CANN 、达芬奇架构和算子 1.AI Core逻辑架构 达芬奇架构包含三部分: 1)计算类:矩阵计算单元(两个矩阵扔进去相乘)、向量计算单元、标量计算单元 2)控…...
系统架构设计师教程 第4章 信息安全技术基础知识-4.5 密钥管理技术4.6 访问控制及数字签名技术-解读
系统架构设计师教程 第4章 信息安全技术基础知识-4.5 密钥管理技术&4.6 访问控制及数字签名技术 4.5 密钥管理技术4.5.1 对称密钥的分配与管理4.5.1.1 密钥的使用控制4.5.1.1.1 密钥标签4.5.1.1.2 控制矢量4.5.1.2 密钥的分配4.5.1.2.1物理方式14.5.1.2.2 物理方式24.5.1…...
C语言日常练习Day13
目录 一、设半径r1.5,圆柱高h3,求圆周长、圆面积、圆球表面积、圆球体积、圆柱体积 二、编写程序,用getchar函数读入两个字符给c1,c2,然后分别用putchar函数和printf函数输出这两个字符 三、输入4个整数,要求按由小…...
map、foreach、filter这些方法你还不知道什么时候该用哪个吗?那就看过来
forEach:主要用于遍历数组并对每个元素执行某种操作,通常用于改变当前数组里的值。它不会返回新数组,而是直接在原数组上进行操作。forEach方法不支持return、break、continue等语句,因为这些语句在forEach中不会…...
6.3 面向对象技术-设计模式
设计模式 创建型模式 结构型模式...
Mac 中安装内网穿透工具ngrok
ngrok 是什么? Ngrok 是一个网络工具,主要用于在网络中创建从公共互联网到私有或本地网络中运行的web服务的安全隧道。它充当了一个反向代理,允许外部用户通过公共可访问的URL访问位于防火墙或私有网络中的web应用程序或服务。Ngrok 特别适用…...
python count返回什么
描述 count() 方法用于统计字符串中某个子字符串出现的次数,可选参数为开始搜索与结束搜索的位置索引。 语法 count() 方法语法: S.count(sub[,start0[,endlen(S)]]) 参数 sub -- 搜索的子字符串。 S -- 父字符串。 start -- 可选参数,…...
mac清理软件哪个好用免费 MacBook电脑清理软件推荐 怎么清理mac
随着使用时间的增长,mac电脑会积累一些不必要的垃圾文件,这些文件会占用宝贵的存储空间,影响电脑的运行速度和稳定性。因此,定期清理mac电脑的垃圾文件是非常有必要的。市场上有许多优秀的Mac清理软件,包括一些出色的国…...
学生党百元蓝牙耳机哪个性价比高?精选四款超强性价比耳机型号
现阶段,蓝牙耳机技术逐渐成熟,蓝牙耳机在我们的学习和娱乐中承担着很重要的角色,那么在面对众多品牌和型号中,学生党们在选择蓝牙耳机上纠结不已,到底学生党百元蓝牙耳机哪个性价比高?作为一个蓝牙耳机重度…...
中文之美,美在辞藻富丽,也美在情感含蓄内敛。
文章目录 引言句句不提幸福,句句都是幸福句句不提释怀,句句都是释怀句句不提爱意,句句都是爱意句句不提安慰,句句都是安慰句句不提遗憾,句句都是遗憾句句不提思念,句句都是思念引言 许多句子没有将主题直抒胸臆,却通过字词间的呼应、碰撞,让人感受到“言未表而意无穷”…...
FPGA与ASIC:深入解析芯片设计的双子星
前言 在半导体世界里,FPGA(Field-Programmable Gate Array,现场可编程门阵列)与ASIC(Application-Specific Integrated Circuit,专用集成电路)是两种截然不同的芯片设计策略,各自在…...
深入 Symfony 服务容器:依赖注入的艺术
“深入 Symfony 服务容器:依赖注入的艺术” 是一个涵盖了 Symfony 服务容器核心概念和依赖注入机制的复杂话题。为了全面理解 Symfony 服务容器的运作,我们将详细探讨以下几个方面: 服务容器的概念和作用依赖注入的基本原理Symfony 服务容器…...
基于Java+SpringMvc+Vue技术的慈善捐赠平台设计与实现(源码+LW+部署讲解)
项目含有源码、文档、PPT、配套开发软件、软件安装教程、项目发布教程、包运行成功以及课程答疑! 软件开发环境及开发工具: 操作系统:Windows 10、Windows 7、Windows 8 开发语言:java 前端技术:JavaScript、VUE.j…...