【考研408真题】2022年408数据结构41题---判断当前顺序存储结构树是否是二叉搜索树
文章目录
- 思路
- 408考研各数据结构C/C++代码(Continually updating)
思路
很明显,这是一个顺序存储结构的树的构成方法。其中树的根节点位置从索引0开始,对于该结构,存在有:如果当前根节点的下标为n,那么其左子树下标为2n+1,右子树下标为2n+2。
而对于BST,我们知道,其一个非常显著的特点就是:对于根节点root,其左子树小于其根节点的值,其右子树大于其根节点的值。同时,如果当前节点为null,不影响其是否为BST。
基于这个理论,我们大概的实现思路是:递归的判断当前根节点的左子树和右子树,并且限定其左右子树的值的大小区间范围。
那么这里应该如何去限制这个范围呢?
从上面的理论中我们可以得到如下的伪代码:
//如下代码基于链式存储结构 不过不影响理论实践
bool isBST(SqBiTree* root,int low,int high)
{if(root==null){return true;}//这里逻辑严谨应该增加一个左右指针的非空判断 我就不写了if(root.left.val>=root.val || root.right.val <= root.val){return false;}return isBST(root.left,low,root.val) && isBST(root.right,root.val,maxValue);
}
为什么要这么写呢?
首先我们基于上面的定义,如果当前节点为空,不影响当前树是否是BST,因此直接返回tree。
之后,我们开始条件判断,当前节点的左右子节点,是否小于和大于当前节点。
如果不是,也就是违法了BST的特性,那么我们直接返回false。
并且,我们一开始也说了,这应该是一个递归的判断过程,因此我们还需要对当前root节点的左子树和右子树继续去执行当前的递归过程。
那么递归的条件是什么?
对于当前节点的左子树,其最小值应该是不限定的,但是其最大值必须小于当前节点的值,
而对于其右子树,其最小值应该大于当前节点的值,其最大值不限。
所以就可以得到最后两行代码的条件了。
那么换到我们题目中,我们只需要将指针操作,修改为对数组下标的数据判断即可。
最终就可以得到如下代码:
// 递归函数,判断以n为根的二叉树是否是BST
bool isBSTUtil(BinaryTree *T, int n, TreeNodeType minVal, TreeNodeType maxVal)
{if (T->data[n] == '\0')return true;TreeNodeType nodeValue = T->data[n];// 检查当前节点的值是否在[minVal, maxVal]的范围内if ((nodeValue <= minVal) || ( maxVal <= nodeValue))return false;// 递归检查左子树和右子树,更新范围return isBSTUtil(T, 2 * n, minVal, nodeValue) && isBSTUtil(T, 2 * n + 1, nodeValue, maxVal);
}
ok,经过上面的解释,我们就已经得到了完整的当前题目的实现思路了。
完整代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>#define MaxSize 100typedef int TreeNodeType;// 二叉树结构
typedef struct
{TreeNodeType data[MaxSize];int BiTreeNum;
} BinaryTree;// 声明队列数据结构
typedef struct
{int front, rear;int size;int capacity;int *array;
} Queue;void initTree(BinaryTree *T);
void createTree(BinaryTree *T, int n);
TreeNodeType rootTree(BinaryTree *T);
int countTree(BinaryTree *T);
int maxDepthOfTree(BinaryTree *T, int n);
void preOrderTraverse(BinaryTree *T, int n);
void inOrderTraverse(BinaryTree *T, int n);
void postOrderTraverse(BinaryTree *T, int n);
void levelOrderTraverse(BinaryTree *T); // 层序遍历
bool destoryTree(BinaryTree *T);
void traverseArray(BinaryTree *T); // 遍历数组
bool isBSTUtil(BinaryTree *T, int n, TreeNodeType minVal, TreeNodeType maxVal);// 队列相关函数
Queue *createQueue(int capacity);
bool isQueueEmpty(Queue *queue);
bool isQueueFull(Queue *queue);
void enqueue(Queue *queue, int item);
int dequeue(Queue *queue);int main()
{BinaryTree T;// 开始构造二叉树 其中使用1作为根节点下标// 而不是使用0,使用0的问题在于不好表示数据在数组中的位置// 我们知道二叉树满足 当前节点n的左子树和右子树的序列号应该为 2n和2n+1initTree(&T);printf("请输入根结点(输入#表示该结点为空):");createTree(&T, 1);traverseArray(&T);printf("当前二叉树的最大深度为:%d\n", maxDepthOfTree(&T, 1));printf("先序遍历:");preOrderTraverse(&T, 1);printf("\n");printf("中序遍历:");inOrderTraverse(&T, 1);printf("\n");printf("后序遍历:");postOrderTraverse(&T, 1);printf("\n");printf("层序遍历:");levelOrderTraverse(&T);printf("\n");if (isBSTUtil(&T, 1, -10000, 10000)){printf("this is a BST");}else{printf("this is not a BST");}return 0;
}void initTree(BinaryTree *T)
{int i;for (i = 0; i < MaxSize; ++i){T->data[i] = '\0';}T->BiTreeNum = 0;return;
}void createTree(BinaryTree *T, int n)
{char ch;// 刷新(清空)标准输入流(stdin)// 主打一个求稳fflush(stdin);// 输入当前节点信息 # 代表当前节点为空// 先构造过字数scanf(" %c", &ch);if (ch == '#'){ // 空直接返回return;}else{T->data[n] = ch;T->BiTreeNum++;printf("输入 %c 的左子树数据(输入#表示当前左子树为空: ", ch);// 这里有一个技巧createTree(T, 2 * n);printf("输入 %c 的右子树数据(输入#表示当前右边子树为空): ", ch);createTree(T, (2 * n + 1));}
}// 计算二叉树的最大深度
// 从根节点到叶子节点的最长路径的长度
// 由于是顺序结构 因此这里从第一层也就是n=1开始向下遍历
// 然后不断的判断左子树和右子树的高度
// 最后取最大值
int maxDepthOfTree(BinaryTree *T, int n)
{if (n <= T->BiTreeNum && T->data[n] != '\0'){int leftDepth = maxDepthOfTree(T, 2 * n);int rightDepth = maxDepthOfTree(T, 2 * n + 1);return 1 + fmax(leftDepth, rightDepth);}else{return 0;}
}// 先序遍历 根左右
void preOrderTraverse(BinaryTree *T, int n)
{if (T->data[n] == '\0')return;else{printf("%c ", T->data[n]);preOrderTraverse(T, 2 * n);preOrderTraverse(T, (2 * n + 1));}
}
// 中序遍历 左根由7
void inOrderTraverse(BinaryTree *T, int n)
{if (T->data[n] == '\0')return;else{inOrderTraverse(T, 2 * n);printf("%c ", T->data[n]);inOrderTraverse(T, (2 * n + 1));}
}
// 后序遍历 左右根
void postOrderTraverse(BinaryTree *T, int n)
{if (T->data[n] == '\0')return;else{postOrderTraverse(T, 2 * n);postOrderTraverse(T, (2 * n + 1));printf("%c ", T->data[n]);}
}
void traverseArray(BinaryTree *T)
{for (int i = 1; i <= T->BiTreeNum; i++){printf("%c ", T->data[i]);}printf("\n");
}// 层序遍历二叉树
void levelOrderTraverse(BinaryTree *T)
{if (T->BiTreeNum == 0){printf("二叉树为空\n");return;}Queue *queue = createQueue(T->BiTreeNum);int current = 1; // 从根节点开始while (current <= T->BiTreeNum){printf("%c ", T->data[current]);if (2 * current <= T->BiTreeNum && T->data[2 * current] != '\0'){enqueue(queue, 2 * current);}if (2 * current + 1 <= T->BiTreeNum && T->data[2 * current + 1] != '\0'){enqueue(queue, 2 * current + 1);}if (!isQueueEmpty(queue)){current = dequeue(queue);}else{break;}}free(queue->array);free(queue);
}// 创建队列
Queue *createQueue(int capacity)
{Queue *queue = (Queue *)malloc(sizeof(Queue));if (!queue){perror("内存分配失败");exit(EXIT_FAILURE);}queue->front = 0;queue->rear = -1;queue->size = 0;queue->capacity = capacity;queue->array = (int *)malloc(capacity * sizeof(int));if (!queue->array){perror("内存分配失败");exit(EXIT_FAILURE);}return queue;
}// 检查队列是否为空
bool isQueueEmpty(Queue *queue)
{return (queue->size == 0);
}// 检查队列是否已满
bool isQueueFull(Queue *queue)
{return (queue->size == queue->capacity);
}// 入队列
void enqueue(Queue *queue, int item)
{if (isQueueFull(queue)){printf("队列已满\n");return;}queue->rear = (queue->rear + 1) % queue->capacity;queue->array[queue->rear] = item;queue->size++;
}// 出队列
int dequeue(Queue *queue)
{if (isQueueEmpty(queue)){printf("队列为空\n");return -1;}int item = queue->array[queue->front];queue->front = (queue->front + 1) % queue->capacity;queue->size--;return item;
}// 递归函数,判断以n为根的二叉树是否是BST
bool isBSTUtil(BinaryTree *T, int n, TreeNodeType minVal, TreeNodeType maxVal)
{if (T->data[n] == '\0')return true;TreeNodeType nodeValue = T->data[n];// 检查当前节点的值是否在[minVal, maxVal]的范围内if ((nodeValue <= minVal) || ( maxVal <= nodeValue))return false;// 递归检查左子树和右子树,更新范围return isBSTUtil(T, 2 * n, minVal, nodeValue) && isBSTUtil(T, 2 * n + 1, nodeValue, maxVal);
}
408考研各数据结构C/C++代码(Continually updating)
408考研各数据结构C/C++代码(Continually updating)
这个模块是我应一些朋友的需求,希望我能开一个专栏,专门提供考研408中各种常用的数据结构的代码,并且希望我附上比较完整的注释以及提供用户输入功能,ok,fine,这个专栏会一直更新,直到我认为没有新的数据结构可以讲解了。
目前我比较熟悉的数据结构如下:
数组、链表、队列、栈、树、B/B+树、红黑树、Hash、图。
所以我会先有空更新出如下几个数据结构的代码,欢迎关注。 当然,在我前两年的博客中,对于链表、哈夫曼树等常用数据结构,我都提供了比较完整的详细的实现以及思路讲解,有兴趣可以去考古。
相关文章:

【考研408真题】2022年408数据结构41题---判断当前顺序存储结构树是否是二叉搜索树
文章目录 思路408考研各数据结构C/C代码(Continually updating) 思路 很明显,这是一个顺序存储结构的树的构成方法。其中树的根节点位置从索引0开始,对于该结构,存在有:如果当前根节点的下标为n,…...

深度学习DAY3:激活函数
激活函数映射——引入非线性性质 h (Σ(W * X)b) yσ(h) 将h的值通过激活函数σ映射到一个特定的输出范围内的一个值,通常是[0, 1]或[-1, 1] 1 Sigmoid激活函数 逻辑回归LR模型的激活函数 Sigmoid函数࿰…...

puppeteer
目录 介绍启动方法功能一、爬虫优势如何实现爬虫小demo 功能二、执行脚本百度搜索脚本demo 功能三、获取cookie(这个只能是模拟浏览器当前进入网页的cookie不是平时用的下载的的浏览器的cookie)功能四、监控网页,进行性能分析 介绍 puppetee…...
javascript二维数组(21)执行异步HTTP(Ajax)请求的方法($.get、$.post、$getJSON、$ajax)
执行异步HTTP(Ajax)请求的方法 . g e t 、 .get、 .get、.post、 g e t J S O N 、 getJSON、 getJSON、ajax都是jQuery提供的用于执行异步HTTP(Ajax)请求的方法。每个方法都有其特定的用途和区别。 . g e t :这个方法…...
TypeScript React(下)
目录 TypeScript & React TS开发环境的搭建 tsconfig.json webpack.config.js babel.config.js .eslintrc.js TypeScript & React TS开发环境的搭建 软件版本:TypeScript:3.9.5;React:16.13.1 Node:8.17.0环境搭建:正确搭建一…...

『Linux小程序』进度条
文章目录 缓冲区问题回车与换行的区别进度条小程序 缓冲区问题 假设有一段代码为: #include<iostream> #include<unistd.h> int main() …...

【手写数字识别】GPU训练版本
SVM Adaboost Bagging 完整代码 I import torch import torch.nn.functional as F from torch.utils.data import DataLoader, TensorDataset from torchvision import transforms, datasets import matplotlib.pyplot as plt# 超参数 batch_size 64 num_epochs 10# 数据…...

c#-特殊的集合
位数组 可观察的集合 private ObservableCollection<string> strList new ObservableCollection<string>();// Start is called before the first frame updatevoid Start(){strList.CollectionChanged Change;strList.Add("ssss");strList.Add("…...
Android 使用 eChart 设置标线
echart使用标线 Android部分: import android.webkit.WebView; import com.jianqu.plasmasterilizer.R; import com.jianqu.plasmasterilizer.utils.DisplayUtils; import com.jianqu.plasmasterilizer.utils.TimerUtil; import java.util.ArrayList; import java.…...

红队专题-Cobalt strike 4.x - Beacon重构
红队专题 招募六边形战士队员重构后 Beacon 适配的功能windows平台linux和mac平台C2profile 重构思路跨平台功能免杀代码部分sysinfo包packet包config.go命令的执行shell、run、executepowershell powerpick命令powershell-importexecute-assembly 堆内存加密字符集 招募六边形…...
一文掌握 Go 文件的写入操作
前言 通过案例展示如何读取文件里的内容。本文接着上篇文章的内容,介绍文件的写入操作。 File.Write、File.WriteString、File.WriteAt File.Write(b []byte) (n int, err error) 直接操作磁盘往文件里写入数据,写入单位为字节。 b 参数:…...

小程序入门及案例展示
目录 一、小程序简介 1.1 为什么要使用小程序 1.2 小程序可以干什么 二、前期准备 2.1 申请账号 2.2 开发工具下载与安装 三、电商案例演示 四、入门案例 4.1 项目结构解析 4.2 基础操作及语法 4.3 模拟器 4.4 案例演示 4.4.1 新建页面 4.4.2 头部样式设置 4.4.…...

linux 安装python django pip 遇到的问题
Python解决SSL不可用问题 解决方案: 首先要明白python版本需要和openssl的版本需要相对匹配的,在Python3.7之后的版本,依赖的openssl,必须要是1.1或者1.0.2之后的版本,或者安装了2.6.4之后的libressl,linux…...

【问题解决】【爬虫】抓包工具charles与pycharm发送https请求冲突问题
问题: 开启charles抓包,运行pycharm发送https请求报以下错误 解决: 修改python代码,发送请求时添加verify false,此时charles也能抓取到pycharm发送的请求 2. 关闭charles抓包,取消勾选window proxy...
Hadoop3教程(二):HDFS的定义及概述
文章目录 (40)HDFS产生的背景和定义(41)HDFS的优缺点(42)HDFS组成架构(43)HDFS文件块大小(面试重点)参考文献 (40)HDFS产生的背景和定…...

【物联网+JAVA 】智慧工地源码
一、什么是智慧工地? 工地本身不拥有智慧,工地的运作是依赖于人的智慧。工地信息化技术,能够减少对人的依赖,使工地拥有智慧。 智慧工地,就是立足于“智慧城市”和“互联网”,采用云计算、大数据和物联网…...

001数据安全传输-多端协议传输平台:Openssl安装和配置 - EVP代码测试
001数据安全传输-多端协议传输平台:Openssl安装和配置 - EVP代码测试 文章目录 001数据安全传输-多端协议传输平台:Openssl安装和配置 - EVP代码测试1. 安装1.1 windows下安装openssl1.2 Linux下安装OpenSSL 2. VS中使用openssl3. 测试 1. 安装 1.1 win…...
关于小编入坑第512天
机缘 最初成为创作者的初心:总结记录整个学习前端的历程 日常学习过程中的记录: 先思考,整个程序逻辑流程是否出现问题 再文档,根据相关文档了解源头,学会看懂文档,是一个锻炼自学前端能力的关键一步 …...

VS2015编译Qt工程发生MSB4018错误完整解决过程
一、错误产生环境 操作系统:Windows10 开发工具:VS2015企业版 Qt版本:Qt5.7.1 64位 二、错误内容 MSB4018 “VCMessage”任务意外失败。 System.FormatException: 索引(从零开始)必须大于或等于零,且小于参数列表的大小。 …...

如何使用JMeter测试导入接口/导出接口
今天一上班,被开发问了一个问题:JMeter调试接口,文件导入接口怎么老是不通?还有导出文件接口,不知道文件导到哪里去了? 我一听,这不是JMeter做接口测试经常遇到的嘛,但是一时半会又…...

.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...

ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...

HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...

【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...