数据结构--二叉树相关习题5(判断二叉树是否是完全二叉树 )

1.判断二叉树是否是完全二叉树 

辨别:

不能使用递归或者算节点个数和高度来判断。

满二叉树可以用高度和节点来判断,因为是完整的。

但是完全二叉树前面是满的,但是最后一层是从左到右连续这种

如果仍然用这种方法的话,如下图两个识别方法是一样的,但是无法准确识别

完全二叉树:前h-1层是满的,最后一层是从左到右连续。

如果走层序那么一定是连续的,也就是说要通过层序遍历来走。

思路:1.层序遍历走,空也进序列。

2.遇到第一个空时开始判断,如果后面都为空则是完全二叉树,若空后面还出席那非空的情况则说明不是完全二叉树。

代码实现:

//判断二叉树是否是完全二叉树
bool TreeComplete(BTNode* root)
{ Queue q;//仍然使用队列去实现QueueInit(&q);if (root)QueuePush(&q,root)while (!QueueEmpty){BTNode* front = QueueFront(&q);QueuePop(&q);//遇到第一个空就可以开始判断,如果队列中还有非空,就不是完全二叉树。if (front == NULL){break;}QueuePush(&q, front->left);QueuePush(&q, front->right);}while (!QueueEmpty){BTNode* front = QueueFront(&q);QueuePop(&q);//如果仍有非空元素,直接
//		return false;if (front){QueueDestroy(&q);//如果存在非空。return false;}QueueDestroy(&q);return true;
//最终QueueDestroy,再返回}
}

补充队列的一系列实现

void QueueInit(Queue* pq)
{assert(pq);pq->phead =  NULL;pq->ptail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}// 队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->val = x;if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}// 队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size != 0);/*QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;if (pq->phead == NULL)pq->ptail = NULL;*/// 一个节点if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else // 多个节点{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3224043.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

Chromium编译指南2024 Linux篇-同步Chromium第三方库(四)

1.引言 在成功拉取Chromium源码并创建新分支后,我们需要进一步配置开发环境。这包括拉取必要的第三方库以及设置hooks,以确保我们能够顺利进行编译和开发工作。以下步骤将详细介绍如何进行这些配置。 2.拉取第三方库以及hooks Chromium 使用了大量的第…

WSL2编译使用6.6版本内核

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、有什么变化二、下载6.6内核三、开始编译1.安装环境2.开始编译 四、使用1.杀死虚拟机2.防止内核文件3.修改配置文件 总结 前言 最近出了一件不大不小的事&a…

【前端速通系列|第二篇】Vue3前置知识

文章目录 1.前言2.包管理工具npm2.1下载node.js2.2配置 npm 镜像源2.3 npm 常用命令 3.Vite构建工具4.Vue3组件化5.Vue3运行原理 1.前言 本系列文章旨在帮助大家快速上手前端开发。 2.包管理工具npm npm 是 node.js中进行 包管理 的工具. 类似于Java中的Maven。 2.1下载nod…

C++之goto陈述

关键字 goto用于控制程式执行的顺序&#xff0c;使程式直接跳到指定标签(lable) 的地方继续执行。 形式如下 标签可以是任意的识别字&#xff0c;后面接一个冒号。 举例如下 #include <iostream>int main() {goto label_one;label_one: {std::cout << "Lab…

第241题| 确定极限中参数问题 | 武忠祥老师每日一题

解题思路&#xff1a;确定极限中的参数的方法是求这个极限&#xff1b;求极限根据类型选方法。 形可以用到三种方法&#xff1a;洛必达&#xff0c;等价&#xff0c;泰勒。 先观察题目&#xff0c;将看成一个整体&#xff0c;同时,并令,整理之后如下&#xff1a; 这里也要想办…

如何使用uer做多分类任务

如何使用uer做多分类任务 语料集下载 找到这里点击即可 里面是这有json文件的 因此我们对此要做一些处理&#xff0c;将其转为tsv格式 # -*- coding: utf-8 -*- import json import csv import chardet# 检测文件编码 def detect_encoding(file_path):with open(file_path,…

16:9横屏短视频素材库有哪些?横屏短视频素材网站分享

在这个视觉内容至关重要的时代&#xff0c;16:9横屏视频因其宽广的画面和优越的观赏体验&#xff0c;已经成为无数创作者和营销专家的首选格式。但要创造出吸引人的横屏视频&#xff0c;高质量的视频素材库是不可或缺的。不管你是资深视频制作人还是刚入行的新手&#xff0c;下…

13 - matlab m_map地学绘图工具基础函数 - 介绍创建管理颜色映射的函数m_colmap和轮廓图绘制颜色条的函数m_contfbar

13 - matlab m_map地学绘图工具基础函数 - 介绍创建管理颜色映射的函数m_colmap和轮廓图绘制颜色条的函数m_contfbar 0. 引言1. 关于m_colmap2. 关于m_contfbar3. 结语 0. 引言 本篇介绍下m_map中用于创建和管理颜色映射函数&#xff08;m_colmap&#xff09;和 为轮廓图绘制颜…

JFlash读取和烧录加密stm32程序

JFlash读取和烧录加密stm32程序 安装后JFlash所在的目录&#xff1a;C:\Program Files\SEGGER\JLink 一、烧写加密程序 1、打开C:\Program Files\SEGGER\JLink目录&#xff0c;找到JFlash.exe,双击它&#xff0c;就可以打开该执行程序。见下图&#xff1a; 2、选择“Create …

微信小程序毕业设计-书店系统项目开发实战(附源码+论文)

大家好&#xff01;我是程序猿老A&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;微信小程序毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计…

骏网一卡通之类的游戏卡有什么用?

感觉现在打端游的人越来越少了 而且游戏充值卡显得就很鸡肋&#xff0c;在家里整理东西&#xff0c;翻出来好多骏网一卡通&#xff0c;但是我又不打游戏 想着把这卡送给有需要的朋友&#xff0c;不然也是浪费&#xff0c;问了一圈送不出去 还好最后在收卡云上卖掉了&#xf…

【QT中实现摄像头播放、以及视频录制】

学习分享 1、效果图2、camerathread.h3、camerathread.cpp4、mainwindow.h5、mainwindow.cpp6、main.cpp 1、效果图 2、camerathread.h #ifndef CAMERATHREAD_H #define CAMERATHREAD_H#include <QObject> #include <QThread> #include <QDebug> #include &…

mysql 5.7.44 32位 zip安装

前言 因为研究别人代码&#xff0c;他使用了5.7的 32位 mysql &#xff0c;同时最新的 8.4 64位 mysql 不能用官方lib连接。所以安装这个版本使用&#xff0c;期间有些坑&#xff0c;在这里记录一下。 下载路径 mysql官方路径&#xff1a;https://downloads.mysql.com/archi…

c++ primer plus 第15章友,异常和其他:15.1.2 友元成员函数

#c primer plus 第15章友&#xff0c;异常和其他&#xff1a;15.1.2 友元成员函数 提示&#xff1a;这里可以添加系列文章的所有文章的目录&#xff0c;目录需要自己手动添加 例如&#xff1a;15.1.2 友元成员函数 提示&#xff1a;写完文章后&#xff0c;目录可以自动生成&am…

01:简易的电动车防盗报警器

简易的电动车防盗报警器 1、震动传感器模块的使用2、使用震动传感器模块控制继电器开关3、433M无线发射接收模块的使用 需要材料&#xff1a; 1、51单片机 2、震动传感器模块 3、继电器模块 4、高功率喇叭 5、433M无线发射接收模块 6、弱干杜邦线 1、震动传感器模块的使用 接好…

2024全网最全面及最新且最为详细的网络安全技巧五 之 SSRF 漏洞EXP技巧,典例分析以及 如何修复 (下册)———— 作者:LJS

五.SSRF 漏洞EXP技巧&#xff0c;典例分析以及 如何修复 (下册) 目录 五.SSRF 漏洞EXP技巧&#xff0c;典例分析以及 如何修复 (下册) 5.4gopher 协议初探 0x01 Gopher协议 0x02 协议访问学习 复现环境 centos7 kali 2018 发送http get请求 发送http post请求 5.5 SSRF…

2017年,我成为了技术博主

2017年9月&#xff0c;我已经大三了。 >>上一篇&#xff08;爪哇&#xff0c;我初窥门径&#xff09; 我大二学了很多java技术&#xff0c;看似我一会就把javaweb/ssh/ssm这些技术栈给学了。 这些技术确实不难&#xff0c;即便是我&#xff0c;我都能学会&#xff0c;…

Java字符串(String、字符串拼接、原理)

文章目录 一、String字符串1.1创建方式【直接赋值、new一个对象】1.1.1 使用字符串字面值直接赋值&#xff1a;&#xff08;1&#xff09;字符串字面量创建String对象的转换过程&#xff08;2&#xff09;一些方法&#xff08;3&#xff09;说明 1.1.2 使用new关键字创建字符串…

新手教学系列——crontab 使用不当引发的服务器性能问题

起因及症状 最近,我们的一台服务器随着运行时间的增加,逐渐出现了压力过大的问题。具体表现为数据库连接数飙升至 4000+,Redis 频繁超时,系统报错文件打开数过多等。针对这些问题,我们逐一检查了数据库连接池、Redis 连接池以及系统的 ulimit 配置,但都未能找到问题的根…

服务注册Eureka

目录 一、背景 1、概念 2、CAP 理论 3、常见的注册中心 二、Eureka 三、搭建 Eureka Server 1、搭建注册中心 四、服务注册 五、服务发现 六、Eureka 和 Zooper 的区别 一、背景 1、概念 远程调用就类似于一种通信 例如&#xff1a;当游客与景区之间进行通信&…