用按层次顺序遍历二叉树的方法,设计算法统计树中度为1的结点数目

用按层次顺序遍历二叉树的方法,设计算法统计树中度为1的结点数目

代码思路:
层序遍历的实现需要借助一个辅助队列
首先将根结点入队,然后根出队,把根的两个子树入队
然后下面循环执行:队头元素出队,队头元素的左右子树入队

举例如下:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

题目和普通层序遍历唯一不同的就是要统计树中度为1的结点,那么我们每次出队头元素,入队尾元素时,判断一下这个出队的元素它的左右孩子是不是只有一个,如果只有一个则count++即可

//层次遍历

int LevelOrder(BiTNode T) {
	SqQueue Q;
	InitQueue(&Q);//初始化一个辅助队列
	BiTree p;
	EnQueue(&Q,T)//根结点入队
	while(!isEmpty(Q)){
		DeQueue(Q,p);//队头元素出队,用p记录出队列的结点
		if(p->lchild!=NULL){
			EnQueue(Q,p->lchild);//左子树不空,左子树入队
			if(p->rchild==NULL){//p结点度为1(左孩子不空,右孩子空)
				count++;
			}
		}
		if(p->rchild!=NULL){
			EnQueue(Q,p->rchild);//右子树不空,右子树入队
			if(p->lchild==NULL){//p结点度为1(左孩子空,右孩子不空)
				count++;
			}
		}
	}
	return count;
}


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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

手机文件怎么传到电脑?简单方法分享!

将手机文件传输到电脑可以将其备份,以防数据丢失或意外情况发生。并且电脑具有更强大的处理能力,可以将文件进行编辑、修改、转换等操作,大大提高了工作效率。那么,手机文件怎么传到电脑?本文将为大家提供简单易懂的解…

[SpringCloud] SpringCloud配置中心的核心原理

SpringCloud是什么时候去拉取配置中心的配置中心客户端的配置信息为什么要写在bootstrap文件中对象中注入的属性是如何动态刷新的一些开源的配置中心是如何整合SpringCloud的 文章目录 1.从SpringBoot的启动过程说起1.1 大致过程 2.准备Environment的核心操作2.1 前置操作 3.pr…

Redis 两种持久化方式 AOF 和 RDB

目录 一、Redis 的持久化 二、Redis 的持久化方式 RDB RDB 介绍 RDB 的触发方式:. 三、RDB的文件生成策略 四、Save 和 Bgsave 命令的区别 六、RDB 最佳配置 七、触发机制-不容忽略方式 AOF 一、AOF介绍 二、RDB所存在的问题 三、AOF 三种策略 四、AOF…

6.15合并二叉树(LC617-E)

算法: 前序、中序、后序都可以,这道题正常逻辑一般都是用前序 正确代码: 这里就是在root1这颗树上改的,也可以新建一个树。 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode …

Long-Context下LLM模型架构全面介绍

深度学习自然语言处理 原创作者:cola 随着ChatGPT的快速发展,基于Transformer的大型语言模型(LLM)为人工通用智能(AGI)铺平了一条革命性的道路,并已应用于知识库、人机界面和动态代理等不同领域。然而,存在一个普遍的限制:当前许多…

「Verilog学习笔记」非整数倍数据位宽转换8to12

专栏前言 本专栏的内容主要是记录本人学习Verilog过程中的一些知识点,刷题网站用的是牛客网 要实现8bit数据至12bit数据的位宽转换,必须要用寄存器将先到达的数据进行缓存。8bit数据至12bit数据,相当于1.5个输入数据拼接成一个输出数据&#…

【1】AR Tag 在ros中的使用

1.定义 AR Tag 是一种用于增强现实(AR)应用中的视觉标记,用于跟踪和定位虚拟物体在现实世界中的位置。 AR Tag由黑白正方形图像表示,图像内部有黑色边框中的某些图案。它与我们经常用到的二维码长得类似,原理其实也一…

动态规划专项---状态机模型

文章目录 大盗阿福股票买卖IV股票买卖V设计密码修复DNA 一、大盗阿福OJ链接 本题思路:状态表示当前第i家店铺选择偷或者不偷的最大利益。状态计算:f[i][0]std::max(f[i-1][0],f[i-1][1]);//如果第i家店铺被偷,则第i-1家店铺不能被偷,f[i][1]f[i-1][0]w[i]…

Django整合回顾

web应用 什么是web:通过web访问web应用程序,很方便,用户只需要一个浏览器即可。是典型的浏览器/服务器端架构的产物 cs架构与bs架构 应用程序有C/S B/S两种模式:b/s 本质上还是c/s mysql属于c/s架构,只是我们的服务…

Harmony OS4开发入门

项目目录介绍 ArkTS介绍 简单案例: State times: number 0State msg: string "hello"State a: any "hello"build() {Row() {Column() {Button(点我${this.times}次).backgroundColor("#360").onClick(() > {this.times}).wid…

歌手荆涛演唱的《春节回家》,一种情感的表达和文化的传承

歌手荆涛演唱的《春节回家》,一种情感的表达和文化的传承 春节回家,是中国传统文化中最为重要的传统节日之一,也是亿万华夏儿女最为期待的日子。每当春节临近,无论身在何处,人们都会收拾行囊,踏上归途&…

VScode集成python开发环境和基本插件下载配置

VSCode开发工具 下载VSCode VSCode官方首页:Visual Studio Code - Code Editing. Redefined 点击Download for Windows下载 安装过程一路下一步即可,其中建议勾选 将"通过Code打开"操作添加到Windows资源管理器目录上下文菜单方便我们直接通过…

AI4S Cup学习赛-中枢神经系统药物研发:药物筛选与优化

赛题介绍 链接:Bohrium 案例广场 (dp.tech) 中枢神经系统类疾病长期以来存在着重要的临床未满足需求。据统计,在当前人口老龄化趋势下,阿兹海默(AD)、帕金森病(PD)等神经退行性疾病和脑癌、中…

String类讲解(1)

🐵本篇文章将讲解String类及其包含的方法 一、介绍String类 String属于引用类型,String类是Java的一个内置类,用于表示字符串,String类中具有许多方法,可以用来操作和处理字符串 二、字符串的构造 下面介绍三种构造字…

【序列推荐】MAN:跨领域顺序推荐的混合注意网络

#论文题目:MAN:Mixed Attention Network for Cross-domain Sequential Recommendation(跨领域顺序推荐的混合注意网络) #论文地址:https://dl.acm.org/doi/10.1145/3543507.3583278 #论文源码开源地址:http…

第二十章多线程

课程重点: 线程相关概念的理解线程的生命周期线程的常用方法 20.1. 线程的简介 20.1.1. 串行与并发 如果在程序中,有多个任务需要被处理,此时的处理方式可以有串行和并发: 串行(同步):所有的任务&…

【密码学引论】分组密码

第三章 分组密码 DES、IDEA、AES、SM4 1、分组密码定义(按照五个组成部分答) 密钥空间:属于对称加密算法kekd明密文空间:将明文划分为m比特的组,每一块依次进行加密加解密算法:由key决定一个明文到密文的…

AIGC系列之:升级版的Stable Diffusion之SDXL介绍

目录 AIGC工具对比 DALL-E MidJourney Stable Diffusion 相关资料 SDXL介绍 SDXL生图效果 SDXL训练LoRA流程 AIGC工具对比 在目前的三大新兴文本转图像模型中,Stable Diffusion诞生得最晚,但由于拥有发展良好的开源社区,它的用户关注…

影响机器视觉测量精度的因素有哪些?

精度测量取决于分辨率 在机器视觉测量中提供高精度和低不确定度的决定性因素是获取的图像的分辨率。在这种情况下,术语分辨率 (或图像分辨率)意味着以实际单位的单个像素的大小。简而言之,如果一个摄像机传感器在水平方向上包含…

Vue实现可拖拽边界布局

Vue实现可拖拽边界布局 在前端开发中,有时需要实现一种可拖拽边界的布局,通过拖动分隔线来调整不同区域大小。例如,下图是一个典型的可拖拽边界布局,它由左右两个区域组成,左边是一个树形菜单,右边是一个上…