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

二叉树基于队列实现的操作详解

一、队列知识补充

有关队列的知识请详见博主的另一篇博客:http://t.csdnimg.cn/3PwO4

本文仅仅附上需要的队列操作供读者参考

//结构体定义
typedef struct BinaryTreeNode* QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//入队
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = InitNewnode(x);if (pq->phead == 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);if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QNode* temp = pq->phead->next;free(pq->phead);pq->phead = temp;}pq->size--;
}
//取出队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}
//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* pcur = pq->phead;while (pcur){QNode* temp = pcur->next;free(pcur);pcur = temp;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

二、层序遍历

2.1 递归思路

采用队列先进先出的特点,按照层序入队即可按照层序出队,从而达到层序遍历的目的。

考虑一般情况:

将根节点入队,下一次根节点出队的同时将孩子结点入队。

考虑特殊情况:

孩子结点可看作子树的根节点,重复递归即可。

只要队列不为空就一直递归

2.2 图解

2.3 C语言实现

注意:出队入队要额外新建变量来复制结点,避免销毁队列引发的原二叉树丢失的问题。

void TreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (QueueEmpty(&q)==false){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}QueueDestroy(&q);
}

三、判断一棵树是不是完全二叉树

3.0 回顾

        什么是完全二叉树?完全二叉树是一种特殊的二叉树,其中除了最后一层外,每一层的节点都被填满,而且最后一层的节点都尽可能地靠左排列。换句话说,如果一个层次深度为k的树,除了第 k 层外,其他各层都是满的,并且第 k 层的节点都依次靠左排列,则这棵树就是完全二叉树。

        所以仅仅通过判断结点的范围处于k-1层满二叉树和k层满二叉树之间的解法是错误的!!       

3.1 思路

通过层序遍历,将第一次出现空结点的地方找到,只需判断后续遍历的过程中是否存在非空结点即可,若存在就不是完全二叉树,反之则是。

分两个循环解决该问题。

  1. 第一层循环本质即为层序遍历,找到第一个空节点就退出。
  2. 第二层循环依然为层序遍历,看是否可以找到非空结点。当队列里面没有元素即层序遍历结束时判断完成。

3.2 C语言实现

bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root != NULL){QueuePush(&q, root);}//入队遇到空停止入队while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL){break;}QueuePush(&q, front->left);QueuePush(&q, front->right);}//判断后面是否还有非空while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){return false;}}QueueDestroy(&q);return true;
}

相关文章:

二叉树基于队列实现的操作详解

一、队列知识补充 有关队列的知识请详见博主的另一篇博客:http://t.csdnimg.cn/3PwO4 本文仅仅附上需要的队列操作供读者参考 //结构体定义 typedef struct BinaryTreeNode* QDataType;typedef struct QueueNode {struct QueueNode* next;QDataType val; }QNode;…...

LabVIEW常用开发架构有哪些

LabVIEW常用开发架构有多种,每种架构都有其独特的特点和适用场合。以下是几种常用的开发架构及其特点和适用场合: 1. 单循环架构 特点: 简单易用适用于小型应用将所有代码放在一个循环中 适用场合: 简单的数据采集和处理任务…...

告别 Dart 中的 Future.wait([])

作为 Dart 开发人员&#xff0c;我们对异步编程和 Futures 的强大功能并不陌生。过去&#xff0c;当我们需要同时等待多个 future 时&#xff0c;我们依赖 Future.wait([]) 方法&#xff0c;该方法返回一个 List<T>。然而&#xff0c;这种方法有一个显着的缺点&#xff1…...

Cisco ASA防火墙抓包命令Capture

在日常运维中&#xff0c;遇到故障时经常需要在ASA上抓包进行诊断。 从抓包中可以看到流量是否经过ASA流量是否被ASA放行&#xff0c;或block&#xff0c;匹配的哪一条ACL capture在Firepower平台上同样适用&#xff0c;无论跑的是ASA还是FTD 1 抓包命令 capture 2 配置方…...

Linux网络编程:HTTP协议

前言&#xff1a; 我们知道OSI模型上层分为应用层、会话层和表示层&#xff0c;我们接下来要讲的是主流的应用层协议HTTP&#xff0c;为什么需要这个协议呢&#xff0c;因为在应用层由于操作系统的不同、开发人员使用的语言类型不同&#xff0c;当我们在传输结构化数据时&…...

HTTP 协议中 GET 和 POST 有什么区别?分别适用于什么场景?

HTTP 协议中 GET 和 POST 是两种常用的请求方法&#xff0c;它们的区别如下: 1. 参数传递方式不同 GET 请求参数是在 URL 中以键值对的形式传递的&#xff0c;例如:http://www.example.com/&#xff1f;key1value1&k ey2value2。 而 POST 请求参数是在请求体中以键值对的…...

talib 安装

这里写自定义目录标题 talib 安装出错 talib 安装出错 https://github.com/cgohlke/talib-build/releases 这里找到轮子 直接装。...

echarts-树图、关系图、桑基图、日历图

树图 树图主要用来表达关系结构。 树图的端点也收symbol的调节 树图的特有属性&#xff1a; 树图的方向&#xff1a; layout、orient子节点收起展开&#xff1a;initialTreeDepth、expandAndCollapse叶子节点设置&#xff1a; leaves操作设置&#xff1a;roam线条&#xff1a…...

04Django项目基本运行逻辑及模板资源套用

对应视频链接点击直达 Django项目用户管理及模板资源 对应视频链接点击直达1.基本运行逻辑Django的基本运行路线&#xff1a;视图views.py中的 纯操作、数据返回、页面渲染 2.模版套用1.寻找一个好的模版2.模板部署--修改适配联动 OVER&#xff0c;不会有人不会吧不会的加Q1394…...

安徽大学数学科学学院教授陈昌昊

男&#xff0c;本&#xff08;2005-2009&#xff09;、硕&#xff08;2009-2012&#xff09;学位都在湖北大学获得&#xff0c;博士学位在芬兰获得&#xff08;2012-2016&#xff09;&#xff0c;博士后分别在澳大利亚&#xff08;2016-2019&#xff09;、香港&#xff08;2020…...

com.alibaba.fastjson.JSONObject循环给同一对象赋值会出现“$ref“:“$[0]“现象问题

1、问题描述 有些场景下&#xff0c;我们会选择用JSONObject代替Map来处理业务逻辑&#xff0c;但是使用JSONObject时有一个需要注意的地方&#xff1a;在处理JSONObject对象时&#xff0c;引用的com.alibaba.fastjson.JSONObject&#xff0c;在一个集合中&#xff0c;循环给这…...

【C++】详解AVL树——平衡二叉搜索树

个人主页&#xff1a;东洛的克莱斯韦克-CSDN博客 祝福语&#xff1a;愿你拥抱自由的风 目录 二叉搜索树 AVL树概述 平衡因子 旋转情况分类 左单旋 右单旋 左右双旋 右左双旋 AVL树节点设计 AVL树设计 详解单旋 左单旋 右单旋 详解双旋 左右双旋 平衡因子情况如…...

《计算机网络微课堂》2-2 物理层下面的传输媒体

请大家注意&#xff0c;传输媒体不属于计算机网络体系结构的任何一层&#xff0c;如果非要将它添加到体系结构中&#xff0c;‍‍那只能将其放在物理层之下。 传输媒体可分为两类&#xff1a;一类是导引型传输媒体&#xff0c;‍‍另一类是非导引型传输媒体。 在导引型传输媒体…...

【算法设计与分析】基于Go语言实现动态规划法解决TSP问题

本文针对于最近正在学习的Go语言&#xff0c;以及算法课实验所需内容进行Coding&#xff0c;一举两得&#xff01; 一、前言 由于这个实验不要求向之前的实验一样做到那种连线的可视化&#xff0c;故可以用图形界面不那么好实现的语言进行编写&#xff0c;考虑到Go语言的…...

Golang单元测试

文章目录 传统测试方法基本介绍主要缺点 单元测试基本介绍测试函数基准测试示例函数 传统测试方法 基本介绍 基本介绍 代码测试是软件开发中的一项重要实践&#xff0c;用于验证代码的正确性、可靠性和预期行为。通过代码测试&#xff0c;开发者可以发现和修复潜在的错误、确保…...

mac下安装airflow

背景&#xff1a;因为用的是Mac的M芯片的电脑&#xff0c;安装很多东西都经常报错&#xff0c;最近在研究怎么把大数据集群上的crontab下的任务都配置到一个可视化工具中&#xff0c;发现airflow好像是个不错的选择&#xff0c;然后就研究怎么先安装使用起来&#xff0c;后面再…...

二进制中1的个数c++

题目描述 计算鸭给定一个十进制非负整数 NN&#xff0c;求其对应 22 进制数中 11 的个数。 输入 输入包含一行&#xff0c;包含一个非负整数 NN。(N < 10^9) 输出 输出一行&#xff0c;包含一个整数&#xff0c;表示 NN 的 22 进制表示中 11 的个数。 样例输入 100 …...

【面试干货】数据库乐观锁,悲观锁的区别,怎么实现

【面试干货】数据库乐观锁&#xff0c;悲观锁的区别&#xff0c;怎么实现 1、乐观锁&#xff0c;悲观锁的区别2、总结 &#x1f496;The Begin&#x1f496;点点关注&#xff0c;收藏不迷路&#x1f496; 1、乐观锁&#xff0c;悲观锁的区别 悲观锁&#xff08;Pessimistic Lo…...

移动端仪表盘,支持更多组件

05/22 主要更新模块概览 定位函数 快捷筛选 轨迹图表 时间组件 01 表单管理 1.1 【表单组件】- 表单关联新增支持自定义按钮样式 说明&#xff1a; 表单关联-关联数据按钮&#xff0c;原仅支持默认按钮样式&#xff0c;现增加关联数据按钮自定义功能&#xff0c;满…...

科技产业园3D探秘:未来科技之城的奇幻之旅

在数字时代的浪潮中&#xff0c;科技产业园区成为了推动城市经济发展、科技创新的重要引擎。 当我们打开科技产业园的3D可视化模型&#xff0c;仿佛穿越时空&#xff0c;来到了一个充满奇幻色彩的科技世界。在这里&#xff0c;高楼大厦鳞次栉比&#xff0c;绿色植被点缀其间&am…...

[资源] 【百度网盘 】最终幻想战略版 伊瓦利斯编年史 豪华中文 Build.20688883+全DLC-支持手柄

受太阳与圣印保佑&#xff0c;由双头狮统治的国家――――Ivalice。Ivalice与邻国Ordallia展开“The Fifty Years’ War”却战败。一年后先王病逝&#xff0c;而将要继承王位的王子年仅两岁。此后为争夺监护人的头衔与实权&#xff0c;在“The Fifty Years’ War”立下战功的两…...

使用Alpine配置WSL ssh门户忌

1. 哑铃图是什么&#xff1f; 哑铃图&#xff08;Dumbbell Plot&#xff09;&#xff0c;有时也称为DNA图或杠铃图&#xff0c;是一种用于比较两个相关数据点的可视化图表。 它源于人们对更有效数据比较方式的持续探索。 在传统的时间序列比较中&#xff0c;我们通常使用两条折…...

灯具展板、展会展板哪里能找到?答案在这!

在灯具行业&#xff0c;无论是灯具门店的日常展示&#xff0c;还是参加各类展会&#xff0c;合适的展板都起着至关重要的作用。它们不仅能有效展示灯具的特点和魅力&#xff0c;还能提升整体的展示效果。那么&#xff0c;灯具展板、展会展板究竟哪里能找到呢&#xff1f;今天就…...

QEMU v8.2.4 源码深度剖析:从编译到核心模块的实战指南

1. 从零开始&#xff1a;编译属于你自己的QEMU v8.2.4 如果你和我一样&#xff0c;对虚拟化技术充满好奇&#xff0c;总想扒开QEMU这头“巨兽”的肚子看看里面到底是怎么运转的&#xff0c;那么从源码编译开始&#xff0c;绝对是最扎实的第一步。这不仅仅是得到一个可执行文件&…...

C++的std--function与lambda表达式:可调用对象包装器

C的std::function与lambda表达式&#xff1a;可调用对象包装器 在现代C编程中&#xff0c;可调用对象的灵活处理是提升代码复用性和可读性的关键。std::function与lambda表达式的结合&#xff0c;为开发者提供了一种强大的工具&#xff0c;能够统一管理函数指针、成员函数、仿…...

SmolVLA实战教程:USAGE.md文档结构解析与核心功能速查表

SmolVLA实战教程&#xff1a;USAGE.md文档结构解析与核心功能速查表 1. 引言&#xff1a;为什么你需要关注SmolVLA&#xff1f; 如果你正在寻找一个既强大又轻量的机器人控制模型&#xff0c;那么SmolVLA绝对值得你花时间了解。想象一下&#xff0c;一个只有5亿参数的模型&am…...

PHP 8.9 JIT在高并发API网关中的真实表现(对比PHP 8.2/8.3:QPS+312%,内存下降38%)

第一章&#xff1a;PHP 8.9 JIT正式落地&#xff1a;高并发API网关性能跃迁的里程碑PHP 8.9 并非官方版本号——这是虚构设定&#xff0c;但本章基于真实技术演进逻辑构建&#xff1a;以 PHP 8.0 引入的 Tracing JIT 为基石&#xff0c;结合社区对极致 API 网关性能的持续优化诉…...

Snap.Hutao:Windows平台开源原神工具箱完整使用指南

Snap.Hutao&#xff1a;Windows平台开源原神工具箱完整使用指南 【免费下载链接】Snap.Hutao 实用的开源多功能原神工具箱 &#x1f9f0; / Multifunctional Open-Source Genshin Impact Toolkit &#x1f9f0; 项目地址: https://gitcode.com/GitHub_Trending/sn/Snap.Hutao…...

Simulink仿真避坑指南:如何设置步长、powergui和模块采样时间才能让控制周期更稳定

Simulink控制系统仿真参数配置实战&#xff1a;从步长到采样时间的精准调优 在电机控制、电力电子系统等工业仿真场景中&#xff0c;Simulink参数的合理配置直接决定了仿真结果的可靠性与工程指导价值。许多工程师第一次搭建控制系统模型时&#xff0c;往往被各种时间参数搞得晕…...

Java 25虚拟线程压测全对比:Spring WebFlux vs Virtual Threads vs Project Loom原生方案,谁才是百万QPS终极解?

第一章&#xff1a;Java 25虚拟线程压测全对比&#xff1a;Spring WebFlux vs Virtual Threads vs Project Loom原生方案&#xff0c;谁才是百万QPS终极解&#xff1f;Java 25正式将虚拟线程&#xff08;Virtual Threads&#xff09;从预览特性转为标准特性&#xff0c;标志着J…...