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

那我们可以采用层序遍历的方法,借助一个辅助队列
当辅助队列不空的时候,出队头元素,入队头元素的左右孩子
这里不同于层序遍历的是,我们这里入左右孩子,如果左右孩子是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…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
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,可…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关
在水泥厂的生产流程中,工业自动化网关起着至关重要的作用,尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关,为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多,其中不少设备采用Devicenet协议。Devicen…...
小木的算法日记-多叉树的递归/层序遍历
🌲 从二叉树到森林:一文彻底搞懂多叉树遍历的艺术 🚀 引言 你好,未来的算法大神! 在数据结构的世界里,“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的,它…...
对象回调初步研究
_OBJECT_TYPE结构分析 在介绍什么是对象回调前,首先要熟悉下结构 以我们上篇线程回调介绍过的导出的PsProcessType 结构为例,用_OBJECT_TYPE这个结构来解析它,0x80处就是今天要介绍的回调链表,但是先不着急,先把目光…...
Linux-进程间的通信
1、IPC: Inter Process Communication(进程间通信): 由于每个进程在操作系统中有独立的地址空间,它们不能像线程那样直接访问彼此的内存,所以必须通过某种方式进行通信。 常见的 IPC 方式包括&#…...
Selenium 查找页面元素的方式
Selenium 查找页面元素的方式 Selenium 提供了多种方法来查找网页中的元素,以下是主要的定位方式: 基本定位方式 通过ID定位 driver.find_element(By.ID, "element_id")通过Name定位 driver.find_element(By.NAME, "element_name"…...
