二叉树按二叉链表形式存储,试编写一个判别给定二叉树是否是完全二叉树的算法
完全二叉树:就是每层横着划过去是连起来的,中间不会断开
比如下面的左图就是完全二叉树
再比如下面的右图就是非完全二叉树

那我们可以采用层序遍历的方法,借助一个辅助队列
当辅助队列不空的时候,出队头元素,入队头元素的左右孩子
这里不同于层序遍历的是,我们这里入左右孩子,如果左右孩子是NULL,我们也入队
当我们在重复执行上面的操作时,我们会有一刻出队列的时候遇到NULL的情况
这时,再对队列的剩余元素进行判断,如果全是NULL则是完全二叉树,否则是非完全二叉树
举例如下

先把根节点A入队

然后队列不空,队头A出队,A的左右孩子BC入队

然后队列不空,队头B出队,B的左孩子D 和NULL入队

然后队列不空,队头C出队,C的左右孩子E 和NULL入队

然后队列不空,队头D出队,D的左右孩子NULL入队

接下来,队不空,出队的元素是NULL
对于这种情况,我们就需要把队列剩余元素看一下了,如果队列剩余元素中有非NULL元素,
那么该树就不是完全二叉树

代码如下:
//队列相关操作
void InitQueue(SqQueue* Q);//初始化队列
void EnQueue(SqQueue* Q,BiTree T);//入队
void DeQueue(SqQueue* Q,BiTree* T)//出队头元素,用T带回出队元素
int QueueEmpty(SqQueue Q);//判断队列是否为空//判断是否是完全二叉树
int IsComplete(BiTree T){if(T==NULL){//空树是一种特殊的完全二叉树return 1;}SqQueue Q;//初始化一个辅助队列InitQueue(&Q);EnQueue(&Q,T);//根节点入队while(!QueueEmpty(Q)){//层序遍历BiTree p;DeQueue(&Q,&p);if(p!=NULL){//出的队头元素非空//左右孩子入队EnQueue(&Q,p->lchild);EnQueue(&Q,p->rchild);}else{//出的队头元素是NULL//判断队列中剩余元素是否全是NULL//全是NULL——完全二叉树//不全是NULL——非完全二叉树while(!QueueEmpty(Q)){DeQueue(&Q,&p);if(p!=NULL){return 0;}}}}return 1;
}
相关文章:
二叉树按二叉链表形式存储,试编写一个判别给定二叉树是否是完全二叉树的算法
完全二叉树:就是每层横着划过去是连起来的,中间不会断开 比如下面的左图就是完全二叉树 再比如下面的右图就是非完全二叉树 那我们可以采用层序遍历的方法,借助一个辅助队列 当辅助队列不空的时候,出队头元素,入队头…...
Android自定义控件
目录 Android自定义控件一、对现有控件进行扩展二、创建复合控件1 定义属性2 组合控件3 引用UI模板 三、重写View来实现全新控件1 弧线展示图1.1 具体步骤: 2 音频条形图2.1 具体步骤 四、补充:自定义ViewGroup Android自定义控件 ref: Android自定义控件…...
Java 中的 Cloneable 接口和深拷贝
引言: 在 Java 中,深拷贝是一种常见的需求,它可以创建一个对象的完全独立副本。Cloneable 接口提供了一种标记机制,用于指示一个类实例可以被复制。本文将详细介绍 Java 中的 Cloneable 接口和深拷贝的相关知识࿰…...
项目实战:通过axios加载水果库存系统的首页数据
1、创建静态页面 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title><link rel"stylesheet" href"style/index.css"><script src"script/axios.mi…...
RK3568平台 内存的基本概念
一.Linux的Page Cache page cache,又称pcache,其中文名称为页高速缓冲存储器,简称页高缓。page cache的大小为一页,通常为4K。在linux读写文件时,它用于缓存文件的逻辑内容,从而加快对磁盘上映像和数据的访…...
mysql联合索引和最左匹配问题。
1引言: 如果频繁地使⽤相同的⼏个字段查询,就可以考虑建⽴这⼏个字段的联合索引来提⾼查询效率。⽐如对 于联合索引 test_col1_col2_col3,实际建⽴了 (col1)、(col1, col2)、(col, col2, col3) 三个索引。联合 索引的主要优势是减少结果集数量…...
全球发布|首个AI视角下的生态系统架构解读—《生态系统架构--人工智能时代从业者的新思维》重磅亮相!
点击可免费注册下载 👇 人工智能时代的企业架构师必读系列 《生态系统架构--人工智能时代从业者的新思维》 Philip Tetlow、Neal Fishman、Paul Homan、Rahul著 The Open Group Press 2023年11月出版 这本书可以很好地帮助全球架构师使用人工智能来构建、开发和…...
解决torch.hub.load加载网络模型异常
1 torch.hub.load 加载网络模型错误 通过网络使用torch.hub.load加载模型代码如下: self.model torch.hub.load("facebookresearch/dinov2", dinov2_vits14, sourcegithub).to(self.device) 运行网上的项目,经常会卡住或者超时,…...
如何获取HuggingFace的Access Token;如何获取HuggingFace的API Key
Access Token通过编程方式向 HuggingFace 验证您的身份,允许应用程序执行由授予的权限范围(读取、写入或管理)指定的特定操作。您可以通过以下步骤获取: 1.首先,你需要注册一个 Hugging Face 账号。如果你已经有了账号…...
How to resolve jre-openjdk and jre-openjdk-headless conflicts?
2023-11-05 Archlinux 执行 pacman -Syu 显示 failed to prepare transaction;jre-openjdk and jre-openjdk-headless conflicts 解决 archlinux sudo pacman -Sy jdk-openjdk...
setTimeout和setImmediate以及process.nextTick的区别?
目录 前言 setTimeout 特性和用法 setImmediate 特性和用法 process.nextTick 特性和用法 区别和示例 总结 在Node.js中,setTimeout、setImmediate和process.nextTick是用于调度异步操作的三种不同机制。它们之间的区别在于事件循环中的执行顺序和优先级。…...
read 方法为什么返回 int 类型
在Java的输入流(InputStream)中,read方法返回int类型的值的原因是为了提供更多的信息和灵活性。虽然这可能看起来有些不直观,但有一些合理的考虑和用途,主要包括以下几点: EOF标志:read方法返回…...
在二维矩阵/数组中查找元素 Leetcode74, Leetcode240
这一类题型中二维数组的元素取值有序变化,因此可以用二分查找法。我们一起来看一下。 一、Leetcode 74 Leetcode 74. 搜索二维矩阵 这道题要在一个二维矩阵中查找元素。该二维矩阵有如下特点: 每行元素 从左到右 按非递减顺序排列。每行的第一个元素 …...
MS35657步进电机驱动器可兼容DRV8824
MS35657 是一款双通道 DMOS 全桥驱动器,可以驱动一个步进电机或者两个直流电机。可兼容DRV8824(功能基本一致,管脚不兼容)。每个全桥的驱动电流在 24V 电源下可以工作到 1.4A。MS35657 集成了固定关断时间的 PWM 电流校正器&#…...
SQL语句性能优化
1、查询 SQL 尽量不要使用 select *,而是 select 具体字段 反例子: select * from sys_user; 正例子: select id,name from sys_user; 理由如下: 只取需要的字段,节省资源、减少网络开销。select * 进行查询时,很可能就不会使用到覆盖索引了,就会造成回表查询。…...
线性代数之 伪逆矩阵
目录 一、伪逆矩阵 ◼ A的伪逆矩阵与SVD ◼ 用Python代码计算A的伪逆矩阵 ◼ 笔算A的伪逆矩阵 一、伪逆矩阵 ◼ A的伪逆矩阵与SVD 逆矩阵并不总是存在,即使是方阵。然而,对于非正方形矩阵,存在一个伪逆矩阵,也叫摩尔-彭罗斯…...
【3D图像分割】基于Pytorch的VNet 3D 图像分割5(改写数据流篇)
在这篇文章:【3D 图像分割】基于 Pytorch 的 VNet 3D 图像分割2(基础数据流篇) 的最后,我们提到了: 在采用vent模型进行3d数据的分割训练任务中,输入大小是16*96*96,这个的裁剪是放到Dataset类…...
【漏洞复现】Apache_Shiro_1.2.4_反序列化漏洞(CVE-2016-4437)
感谢互联网提供分享知识与智慧,在法治的社会里,请遵守有关法律法规 文章目录 1.1、漏洞描述1.2、漏洞等级1.3、影响版本1.4、漏洞复现1、基础环境2、漏洞分析3、漏洞验证 说明内容漏洞编号CVE-2016-4437漏洞名称Apache_Shiro_1.2.4_反序列化漏洞漏洞评级…...
Mac连接linux的办法(自带终端和iterm2)
1. 使用Mac自带终端Terminal 1.1 点击右上角的聚焦搜索,再输入终端 1.2 查找linux系统的ip地址 在虚拟机里输入如下命令,找到蓝色区域的就是ip地址 ip addr 如果没有显示ip地址,可以重新安装一下虚拟机,之后确保以太网的连接是打…...
js调整table表格上下相邻元素顺序
有时候我们会遇到要通过箭头控制table表格上下顺序的需求,如下: 点击向下就将该元素下移一位,下面的一位元素就移上来,点击向上就将该元素上移一位,上面的一位元素就移下来,也就是相邻元素互换位置顺序: <el-table :data="targetTable" border style=&quo…...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...
es6+和css3新增的特性有哪些
一:ECMAScript 新特性(ES6) ES6 (2015) - 革命性更新 1,记住的方法,从一个方法里面用到了哪些技术 1,let /const块级作用域声明2,**默认参数**:函数参数可以设置默认值。3&#x…...
