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

数据结构之判断二叉树是否为搜索树(C/C++实现)

文章目录

    • 判断二叉树是否为搜索树
    • 方法一:递归法
    • 方法二:中序遍历法
    • 总结

在这里插入图片描述


二叉树是一种非常常见的数据结构,它在计算机科学中有着广泛的应用。二叉搜索树(Binary Search Tree,简称BST)是二叉树的一种特殊形式,它具有以下性质:对于树中的任意一个节点,其左子树中的所有节点的值都小于该节点的值,其右子树中的所有节点的值都大于该节点的值。本文将详细介绍如何判断一个二叉树是否为搜索树,并提供C和C++的实现示例。

判断二叉树是否为搜索树

思路
判断一个二叉树是否为搜索树,可以通过以下两种方法:

  1. 递归法
  2. 中序遍历法

下面分别对这两种方法进行详细讲解。

方法一:递归法

递归法的核心思想是:对于树中的每个节点,检查其左子树的最大值是否小于当前节点的值,以及其右子树的最小值是否大于当前节点的值。

  1. 如果树为空,则它是二叉搜索树。
  2. 对于当前节点,递归地检查其左子树的最大值是否小于当前节点的值,同时检查其右子树的最小值是否大于当前节点的值。
  3. 如果上述两个条件均满足,则递归地检查左子树和右子树是否都是二叉搜索树。

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++实现)

文章目录 判断二叉树是否为搜索树方法一&#xff1a;递归法方法二&#xff1a;中序遍历法总结 二叉树是一种非常常见的数据结构&#xff0c;它在计算机科学中有着广泛的应用。二叉搜索树&#xff08;Binary Search Tree&#xff0c;简称BST&#xff09;是二叉树的一种特殊形式&…...

golang长连接的误用

误用一&#xff1a;忘记读取响应的body 由于忘记读取响应的body导致创建大量处于TIME_WAIT状态的连接&#xff08;同时产生大量处于transport.go的readLoop和writeLoop的协程&#xff09; 在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…...

滚动数组详解

滚动数组详解 何为滚动数组&#xff1f;滚动数组是如何优化空间的&#xff1f;交替滚动例题&#xff1a;来自某某轮廓线DP的题目 自我滚动(~~不如交替~~ 完结&#xff01;&#xff01;&#xff01; ( 宇宙免责任书&#xff1a;我用的是C) 何为滚动数组&#xff1f; 什么是滚动…...

C 语言动态链表

线性结构->顺序存储->动态链表 一、理论部分 从起源中理解事物&#xff0c;就是从本质上理解事物。 -杜勒鲁奇 动态链表是通过结点&#xff08;Node&#xff09;的集合来非连续地存储数据&#xff0c;结点之间通过指针相互连接。 动态链表本身就是一种动态分配内存的…...

【Leetcode】二十、记忆化搜索:零钱兑换

文章目录 1、记忆化搜索2、leetcode509&#xff1a;斐波那契数列3、leetcode322&#xff1a;零钱兑换 1、记忆化搜索 也叫备忘录&#xff0c;即把已经计算过的结果存下来&#xff0c;下次再遇到&#xff0c;就直接取&#xff0c;不用重新计算。目的是以减少重复计算。 以前面提…...

json数据格式 继续学习

1.定义 轻量级的数据交互格式&#xff0c;可以按照json数据格式去组织和封装数据。 本质是一个带有特定格式的字符串。 2.功能 负责不同编程语言中的数据传递和交互。 3.json数据格式转化 """ 演示json数据和python字典之间的转换 """ impor…...

gradle 构建项目添加版本信息

gradle 构建项目添加版本信息&#xff0c;打包使用 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封装菜单 前提条件&#xff1a;组件创建完成 配置路由 // src/router/index.ts import { createRouter, createWebHashHistory } from vue-router import type { RouteRecordRaw } from vue-router export const Layout () > import(/lay…...

使用 Redis 实现验证码、token 的存储,用自定义拦截器完成用户认证、并使用双重拦截器解决 token 刷新的问题

可以看一下我以前做过的笔记&#xff1a;黑马点评 短信登录部分 基于session实现登录流程 1.发送验证码 用户在提交手机号后&#xff0c;会校验手机号是否合法&#xff0c;如果不合法&#xff0c;则要求用户重新输入手机号 如果手机号合法&#xff0c;后台此时生成对应的验…...

反转链表 - 力扣(LeetCode)C语言

206. 反转链表 - 力扣&#xff08;LeetCode&#xff09;( 点击前面链接即可查看题目) /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/ struct ListNode* reverseList(struct ListNode* head) {if(head NULL)…...

【Linux】进程间通信(1):进程通信概念与匿名管道

人与人之间是如何通信的&#xff1f;举个简单的例子&#xff0c;假如我是月老&#xff0c;我要为素不相识的但又渴望爱情的男女两方牵红线。我需要收集男方的信息告诉女方&#xff0c;收集女方的信息告诉男方&#xff0c;然后由男女双方来决定是否继续。对于他们而言&#xff0…...

Spring从入门到精通 01

文章目录 1. 依赖注入 (Dependency Injection, DI)2. 面向切面编程 (Aspect-Oriented Programming, AOP)3. 事务管理4. 简化 JDBC 开发5. 集成各种框架和技术6. 模块化和扩展性&#xff1a;主要的 Spring 模块&#xff1a;Core Container&#xff1a;AOP 模块&#xff1a;Data …...

C语言经典习题25

冒泡排序 对一维数组进行升序排序&#xff0c;然后在数组中输入20个数&#xff0c;将排序后的结果打印输出。 #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法)拉夫等效原理进行时谐场外推。外推边界距离吸收边界的距离、电磁场循环、傅立叶变换提起幅值和相位、各远区剖分点电场、方向系数计算等操作&#xff0c;得出可视化结果。程序已调通&#xff0c;可直接运行。 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 文件放到指定文件夹

研究了不少文章&#xff0c;我行通了一个&#xff0c;但是也不全&#xff0c;目前只能适用当前文件夹&#xff0c;如果源文件有子文件夹处理不了&#xff0c;还得继续研究。很多人说编译完把O文件移动走或者直接删掉。我想说的是不符合我的要求&#xff0c;移走或者删除O文件&a…...

聊一聊知识图谱结合RAG

因为最近在做一些关于提高公司内部使用的聊天机器人的回答准确率&#xff0c;并且最近微软官方也是开源了一下graphrag的源码&#xff0c;所以想聊一聊这个知识图谱结合rag。 rag在利用私有数据增强大模型回答的领域是一种比较典型的技术&#xff0c;也就是我们提出问题的时候&…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...