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

《二叉树》——3(层序遍历)

目录

前言:

层序遍历:

解析:


前言:

本文主讲链式二叉树的层序遍历,在前面的张篇blog我们初步实现了链式二叉树递归部分的内容,对于递归算法的学习和思维方式我们仍然需要不断加强,所以将对链式二叉树进行收尾,下一章我们将开启递归算法的题目强化训练。

层序遍历:

typedef struct BTTreeNode* QDataType;
//将链队列中的节点类型改为struct BTTreeNode(二叉树节点的数据类型)void TreeLevelOrder(TreeNode* root)
{Queue q;QueueInit(&q);if (root == NULL){printf("空树\n");exit(-1);}int levelsize = 1;QueuePush(&q, root);while (!QueueEmpty(&q)){while (levelsize--){TreeNode* front = QueueFront(&q);printf("%d ", front->data);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}QueuePop(&q);}printf("\n");levelsize = QueueSize(&q);}printf("\n");QueueDestroy(&q);
}

层序遍历不需要用到递归的思想,用我们之前学习过的队列的知识就可以实现层序遍历。

这里是用到队列的先进先出的特性。

以上是一颗二叉树,现在要实现该数的层序遍历,最终结果为:

1

2 4

3 5 6

解析:

    Queue q;QueueInit(&q);if (root == NULL){printf("空树\n");exit(-1);}int levelsize = 1;QueuePush(&q, root);

 对于这一串代码,就是定义队列并且初始化,并将根节点入队列,再定义一个队列长度,用来接受队列里的节点数,当levelsize为空时,就代表当前层数的节点已经打印完毕。因为是将根节点入队列,而且第一层有且只有一个节点,即根节点,所以levelsize = 1;

while (!QueueEmpty(&q)){while (levelsize--){TreeNode* front = QueueFront(&q);printf("%d ", front->data);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}QueuePop(&q);}printf("\n");levelsize = QueueSize(&q);}

 

目前的队列如上图所示。

首先我们需要将定义front指针指向队列的第一个元素。

此时我们需要将root的左右子树入队列,首先我们需要判断左右子树是否为空树。

如果不是空树就入队列。

则有:

 

而这个时候front指向的节点会被先打印出来,再出队列,这时候front就会指向下一个节点,并且levelsize也为0,因为这时候队列的首数据已经出队列,所以队列中只有两个数据,那么levelsize就会被赋值为2。

如图:

 

 同样,接下来就是判断front指向的节点的左右子树是否为空,不为空则入队列。

即:

由于levelsize为2,所以程序会打印队列的前两个数据,即24

2打印完后,front就会指向4这个节点,同样也会判断该节点的左右子树是否为空,不为空则入队列。

如图:

 

然后打印完4的节点后,levelsize又会被赋值为3,用来答应下一层的节点。

 

如此不断重复,层序遍历则完美实现。 

相关文章:

《二叉树》——3(层序遍历)

目录 前言: 层序遍历: 解析: 前言: 本文主讲链式二叉树的层序遍历,在前面的张篇blog我们初步实现了链式二叉树递归部分的内容,对于递归算法的学习和思维方式我们仍然需要不断加强,所以将对链式二叉树进行…...

HarmonyOS应用开发者基础认证考试答案

HarmonyOS应用开发者基础认证考试答案 一、判断题 1.Ability是系统调度应用的最小单元,是能够完成一个独立功能的组件。一个应用可以包含一个或多个Ability。 正确(True) 2.所有使用Component修饰的自定义组件都支持onPageShow,onBackPress和onPageHide…...

【前端素材】bootstrap3 实现地产置业公司source网页设计

一、需求分析 地产置业公司的网页通常是该公司的官方网站,旨在向访问者提供相关信息和服务。这些网页通常具有以下功能: 公司介绍:网页通常包含有关公司背景、历史、核心价值观和使命等方面的信息。此部分帮助访问者了解公司的身份和目标。 …...

C++ 数论相关题目 博弈论 Nim游戏

给定 n 堆石子,两位玩家轮流操作,每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完,但不能不拿),最后无法进行操作的人视为失败。 问如果两人都采用最优策略,先手是否必胜。 输入格式…...

机器学习---无偏估计

1. 如何理解无偏估计 无偏估计:就是我认为所有样本出现的概率⼀样。 假如有N种样本我们认为所有样本出现概率都是 1/N。然后根据这个来计算数学期望。此时的数学期望就是我们平常讲 的平均值。数学期望本质就 是平均值。 2. 无偏估计为何叫做“无偏”&#xff1…...

C语言基础13

今天是学习嵌入式相关内容的第十四天,以下是今日所学内容 1.结构体: 1.结构体类型定义 2.结构体变量的定义 3.结构体元素的访问 4.结构体的存储 内存对齐 结构体整体的大小必须为最大基本类型长度的整数倍 5.结构体作为函数参数 值传递 练习:定…...

【Java】Maven配置加载到全局

Maven配置加载到全局 <build><plugins><plugin><artifactId>maven-resources-plugin</artifactId><configuration><encoding>utf-8</encoding><useDefaultDelimiters>true</useDefaultDelimiters></configura…...

右手螺旋线定则

通电螺线管中的安培定则&#xff08;安培定则二&#xff09;&#xff1a;用右手握住通电螺线管&#xff0c;让四指指向电流的方向&#xff0c;那么大拇指所指的那一端是通电螺线管的N极。...

2024 高级前端面试题之 React 「精选篇」

该内容主要整理关于 React 模块的相关面试题&#xff0c;其他内容面试题请移步至 「最新最全的前端面试题集锦」 查看。 React模块精选篇 1. 如何理解React State不可变性的原则2. JSX本质3. React合成事件机制4. setState和batchUpdate机制5. 组件渲染和更新过程6. Diff算法相…...

OSPF协议解析及相关技术探索(C/C++代码实现)

OSPF&#xff08;开放最短路径优先&#xff09;是一种用于自治系统&#xff08;AS&#xff09;内部的路由协议&#xff0c;它是基于链路状态算法的。OSPF的设计目的是为了提供一种可扩展、快速收敛和高效的路由解决方案。 OSPF概念和特点 概念 自治系统&#xff08;AS&#…...

如何恢复已删除的照片?

在这篇综合文章中发现恢复丢失照片的有效且免费的方法。无论您使用的是智能手机、iPhone、Windows 计算机、Mac、SD 卡还是数码相机&#xff0c;我们都提供有关如何恢复已删除照片的分步说明。此外&#xff0c;学习一些有价值的技巧&#xff0c;以防止将来意外删除照片。 意外…...

VMware虚拟机安装macOS

VMware虚拟机安装macOS 文章目录 VMware虚拟机安装macOS先看效果一、准备工作①&#xff1a;镜像资源下载②&#xff1a;虚拟机③&#xff1a;安装macOS所必要的插件 二、开始安装①&#xff1a;创建新的虚拟机②&#xff1a;自定义硬件③&#xff1a;开启虚拟机 先看效果 一、…...

API管理协作工具:Apipost

相信无论是前端&#xff0c;还是后端的测试和开发人员&#xff0c;都遇到过这样的困难。不同工具之间数据一致性非常困难、低效。多个系统之间数据不一致&#xff0c;导致协作低效、频繁出问题&#xff0c;开发测试人员痛苦不堪。 API管理的难点在哪&#xff1f; 开发人员在 …...

GPT-SoVITS 本地搭建踩坑

GPT-SoVITS 本地搭建踩坑 前言搭建下载解压VSCode打开安装依赖包修改内容1.重新安装版本2.修改文件内容 运行总结 前言 传言GPT-SoVITS作为当前与BertVits2.3并列的TTS大模型&#xff0c;于是本地搭了一个&#xff0c;简单说一下坑。 搭建 下载 到GitHub点击此处下载 http…...

【教学类-34-02】20240130纸尺2.0 (A4横版5条,刻度25*5=125CM,有图案)

作品展示&#xff1a; 背景需求&#xff1a; 设计了纸尺的基本模板 【教学类-34-01】20240130纸尺1.0 &#xff08;A4横版5条&#xff0c;刻度25*5125CM&#xff09;-CSDN博客文章浏览阅读194次&#xff0c;点赞5次&#xff0c;收藏5次。【教学类-34-01】20240130纸尺1.0 &am…...

iText操作pdf

最近有个任务是动态的创建pdf根据获取到的内容&#xff0c;百度到的知识点都比较零散&#xff0c;官方文档想必大家也不容易看懂。下文是我做出的汇总 public class CreatePdfUtils {public static void create(){//准备File file new File("C:\\code\\base-project-back…...

关于SQLite 的下载与使用。配合python

win系统下&#xff1a; SQLite Download Page Precompiled Binaries for Windows sqlite-tools-win-x64-3450000.zip (4.77 MiB) 解压后&#xff0c;找个位置。然后设置环境变量指定位置。 可以手动建立.db文件。 也可以通过代码建立&#xff1a; 如下代码就是建立一个db文件。…...

java面向对象基础(面试)

一、面向对象基础 1. 面向对象和面向过程的区别 面向过程把解决问题的过程拆成一个个方法&#xff0c;通过一个个方法的执行解决问题。面向对象会先抽象出对象&#xff0c;然后用对象执行方法的方式解决问题。 2.创建一个对象用什么运算符?对象实体与对象引用有何不同? n…...

【C++修行之道】STL(初识list、stack)

目录 一、list 1.1list的定义和结构 以下是一个示例&#xff0c;展示如何使用list容器: 1.2list的常用函数 1.3list代码示例 二、stack 2.1stack的定义和结构 stack的常用定义 2.2常用函数 2.3stack代码示例 一、list 1.1list的定义和结构 list的使用频率不高&#…...

【环境配置】安装了pytorch但是报错torch.cuda.is_availabel()=Flase

解决思路&#xff1a;import torch正常&#xff0c;说明torch包安装正常&#xff0c;但是不能和gpu正常互动&#xff0c;猜测还是pytroch和cuda的配合问题 1.查看torch包所需的cuda版本 我的torch是2.0.1&#xff0c;在现在是比较新的包&#xff0c;需要12以上的cuda支持&…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...