03-树2 List Leaves(浙大数据结构PTA习题)

03-树2 List Leaves

分数 25        全屏浏览        切换布局        作者 陈越        单位 浙江大学

Given a tree, you are supposed to list all the leaves in the order of top down, and left to right.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤10) which is the total number of nodes in the tree -- and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a "-" will be put at the position. Any pair of children are separated by a space.

Output Specification:

For each test case, print in one line all the leaves' indices in the order of top down, and left to right. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.

Sample Input:

8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

Sample Output:

4 1 5

代码长度限制:16 KB        时间限制:400 ms        内存限制:64 MB

题目解析:

题目大意:给定一系列树的结点,按照从上到下,从左到右的顺序输出这棵树的叶子结点

关键点1:找到树的根结点

        

关键点2:根据树的根结点以及其它一系列结点构建树

         采用递归的思路,如果根结点的左子树不为空,则递归构建左子树,否则为NULL;如果根结点的右子树不为空,则递归构建右子树,否则为NULL;

关键点3:按照从上到下,从左到右的顺序输出这棵树的叶子结点

        本质是树的层序遍历问题,借助队列实现;

参考代码:

# include<stdio.h>
# include<stdbool.h>
# include<stdlib.h>
# define MAXNODE 10 

typedef char ElementType;

typedef struct TreeNode* Tree;
struct TreeNode{
	ElementType info,left,right;
	Tree Left;
	Tree Right;
};

Tree Create(); 
Tree InitialTree(Tree Array[],int N);
Tree CreateTree(Tree Array[],Tree Root);
void InOrderPrint(Tree tree);

int main(){
	// 根据输入创建树 
	Tree tree = Create();
	// 对这棵树进行层序遍历,并输出叶子结点
	InOrderPrint(tree); 
	return 0;
}

// 对一棵树进行层序遍历,并输出叶子结点
void InOrderPrint(Tree tree){
	// 创建一个结点指针队列	
	Tree Queue[MAXNODE];
	int Rear=-1, Head = -1;
	// 压入根结点
	Queue[++Rear] = tree;
	// 用于格式化输出的统计
	int count = 0; 
	while(Rear!=Head){
		// 从队列出队一个结点,并判读是否是叶节点 
		Tree tmp = Queue[++Head];
		if(tmp->Left == NULL && tmp->Right==NULL){
			if(count==0){
				printf("%d",tmp->info-'0');
				count++;
			}
			else printf(" %d",tmp->info-'0');
		}
		// 分别压入其左右结点(若不为空)
		if(tmp->Left)Queue[++Rear] = tmp->Left;
		if(tmp->Right)Queue[++Rear] = tmp->Right; 
	} 
	return;
	 
} 
 

// 根据输入创建一棵树
Tree Create(){
	int N;
	scanf("%d",&N);
	getchar();
    if(N==0)return NULL;
	Tree Array[N];
	// 将信息存入指针数组中并获得树的根结点
	Tree Root = InitialTree(Array,N);
	// 通过树的根结点来建立树 
	Tree tree = CreateTree(Array,Root);
	return tree; 
} 

// 将结点信息存入指针数组中,并返回树的根结点 
Tree InitialTree(Tree Array[],int N){
	// Check数组用来标记结点是否作为了子节点 
	int i,Check[N];
	for(i=0;i<N;i++)Check[i] = 1;
	// 读入结点信息,并判读每个结点是否作为了子节点 
	for(i=0;i<N;i++){
		Tree node = (Tree)malloc(sizeof(struct TreeNode));
		node->info = '0'+i;
		node->left = getchar();
		if(node->left!='-')Check[node->left-'0'] = 0;
		getchar();
		node->right = getchar();
		if(node->right!='-')Check[node->right-'0'] = 0;
		getchar();
		node->Left = node->Right = NULL;
		Array[i] = node;
	}
	for(i=0;i<N;i++){
		if(Check[i]==1)break;
	}
	return Array[i];
}

// 根据指针数组及根结点递归构建一棵树
Tree CreateTree(Tree Array[],Tree Root){
	int i,count;
	// 递归构建左子树 
	if(Root->left == '-'){
		Root->Left = NULL;
	}else{
		Root->Left = CreateTree(Array,Array[Root->left-'0']);
	}
	// 递归构建右子树
	if(Root->right == '-'){
		Root->Right = NULL;
	}else{
		Root->Right = CreateTree(Array,Array[Root->right-'0']);
	}
	return Root;
} 

运行结果:

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

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

相关文章

mac 安装java jdk8 jdk11 jdk17 等

oracle官网 https://www.oracle.com/java/technologies/downloads/ 查看当前电脑是英特尔的x86 还是arm uname -m 选择指定版本&#xff0c;指定平台的安装包&#xff1a; JDK8 JDK11的&#xff0c;需要当前页面往下拉&#xff1a; 下载到的安装包&#xff0c;双击安装&#x…

Linux系统编程(六)线程同步机制

本文目录 前述&#xff1a;同步机制的引入及概念一、线程的互斥锁1. 定义2. 互斥锁常用方法3. 相关函数&#xff08;1&#xff09;头文件&#xff08;2&#xff09;创建互斥锁&#xff08;3&#xff09;销毁互斥锁&#xff08;4&#xff09;加锁&#xff08;5&#xff09;解锁 …

Java Sort 方法的使用(包含Arrays.sort(),Collections.sort()以及Comparable,Comparator的使用 )

目录 Comparable && Comparator的使用&#xff1a; Comparable: Comparator: Arrays.sort()的使用: 升序排序&#xff1a; 降序排序&#xff1a; 自定义排序方法&#xff1a; 在日常的刷题或开发中&#xff0c;很多时候我们需要对数据进行排序&#xff0c;以达到我…

【C++修行之道】类和对象(二)类的6个默认成员函数、构造函数、析构函数

目录 一、类的6个默认成员函数 二、构造函数 2.1 概念 2.2 特性 2.2.5 自动生成默认构造函数 不进行显示定义的隐患&#xff1a; 2.2.6 自动生成的构造函数意义何在&#xff1f; 两个栈实现一个队列 2.2.7 无参的构造函数和全缺省的构造函数都称为默认构造函数&#x…

ELK 使用 metricbeat监控数据

IP功能版本192.168.140.153elk-18.13.4192.168.140.153metricbeat8.13.4192.168.140.156elk-28.13.4192.168.140.156metricbeat8.13.4192.168.140.159logstash8.13.4192.168.140.159kibana8.13.4 一、安装ELK 参考文档&#xff1a; https://download.csdn.net/download/weix…

【免费Web系列】JavaWeb实战项目案例四

这是Web第一天的课程大家可以传送过去学习 http://t.csdnimg.cn/K547r 多表操作&员工列表查询 1. 多表关系 关于单表的操作(单表的设计、单表的增删改查)我们就已经学习完了。接下来我们就要来学习多表的操作&#xff0c;首先来学习多表的设计。 项目开发中&#xff0…

2023年全球DDoS攻击现状与趋势分析

天翼安全科技有限公司副总工程师、运营保障部总经理陈林表示&#xff0c;2023年扫段攻击频次快速增长&#xff0c;成为网络基础设施面临的最大威胁。为躲避防御&#xff0c;低速扫段攻击成为主流达到攻击总数的73.19%&#xff1b;43.26%的C段攻击持续时间小于5分钟&#xff0c;…

面试题vue+uniapp(个人理解-面试口头答述)未编辑完整....

1.vue2和vue3的区别&#xff08;vue3与vue2的区别&#xff08;你不知道细节全在这&#xff09;_vue2和vue3区别-CSDN博客&#xff09;参考 Vue3 在组合式&#xff08;Composition &#xff09;API&#xff0c;中使用生命周期钩子时需要先引入&#xff0c;而 Vue2 在选项API&am…

车载以太网的未来:OPEN Alliance下17个技术委员会的最新进展与行业影响(下)

从上篇介绍来看&#xff0c;TC1-TC8大多数处于暂停或完成状态。而TC9-TC17在2023年都有不同程度的进展&#xff0c;让我们继续探索藏在其中的车载以太网的发展和挑战。 TC9 Automotive Ethernet Channel & Components&#xff08;in progress&#xff09; TC9的目标是为通…

基础9 探索图形化编程的奥秘:从物联网到工业自动化

办公室内&#xff0c;明媚的阳光透过窗户洒落&#xff0c;为每张办公桌披上了一层金色的光辉。同事们各自忙碌着&#xff0c;键盘敲击声、文件翻页声和低声讨论交织在一起&#xff0c;营造出一种忙碌而有序的氛围。空气中氤氲着淡淡的咖啡香气和纸张的清新味道&#xff0c;令人…

【PHP项目实战训练】——laravel框架的实战项目中可以做模板的增删查改功能(2)

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;开发者-曼亿点 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 曼亿点 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a…

linux centos nfs挂载两台服务器挂载统一磁盘目录权限问题

查看用户id id 用户名另一台为 修改uid和gid为相同id&#xff0c;添加附加组 usermod -u500 -Gwheel epms groupmod -g500 epms

SQL Server定期收缩日志文件详细步骤——基于SQL Server 2012

SQL Server定期收缩日志文件详细步骤 一、环境配置1、查看数据库的属性2、文件设置3、备份模式4、查看收缩配置5、查看收缩选项 二、编写作业计划1、选择新建作业2、常规配置3、步骤4、输入内容5、脚本详解6、新建计划7、输入名称、选择执行时间8、查看测试9、查看测试结果 一、…

Mistral发布首个代码生成人工智能模型Codestral 但不可用于商业活动

由微软支持、估值高达 60 亿美元的法国人工智能初创公司 Mistral发布了首个用于编码的生成式人工智能模型&#xff0c;名为 Codestral。Codestral 与其他代码生成模型一样&#xff0c;旨在帮助开发人员编写代码并与之交互。 Mistral 在一篇博文中解释说&#xff0c;它接受过 80…

想学习中医的看过来

近年来&#xff0c;随着短视频的兴起&#xff0c;中国传统文化&#xff0c;在各大平台成为热搜&#xff0c;且有愈演愈烈之势。证明&#xff0c;国人开始重视起自己的文化&#xff0c;这是一个好的现象。中医学&#xff0c;作为传统文化中不可或缺的一员&#xff0c;也受到了广…

分布式架构设计之Base理论深度剖析:从理论到实践的完美融合

文章目录 引言一、Base理论概述1.1. 基本可用&#xff08;Basically Available&#xff09;1.2. 软状态&#xff08;Soft State&#xff09;1.3. 最终一致性&#xff08;Eventually Consistent&#xff09; 二、Base理论在分布式架构设计中的应用2.1. 分布式数据库设计2.2. 分布…

C语言分支和循环(2)

我的相关博客&#xff1a; C语言的分支与循环&#xff08;1&#xff09; 1.switch语句 除了 if 语句外&#xff0c;C语⾔还提供了 switch 语句来实现分⽀结构。 switch 语句是⼀种特殊形式的 的 if...else 结构&#xff0c;⽤于判断条件有多个结果的情况。它把多重 else if…

用Unityhub安装unity2018.3.0和vuforia

打开下载网址 https://unity.cn/releases/full/2018 选择2018.3.x 找到2018.3.0后&#xff0c;点击从UnityHub下载 然后unityhub会弹出安装界面 只勾选这两个&#xff0c;其余的全部取消勾选&#xff0c;默认勾选上的也取消掉&#xff0c;然后点击安装

【观察】研华科技:奏响数智化转型“交响乐”,将新质生产力融入千行百业...

加快发展新质生产力&#xff0c;已成为当前的主旋律。特别是近年来&#xff0c;以人工智能、大模型、大数据、云计算为代表的数字技术的一系列革命性突破&#xff0c;引发了传统生产要素以及以数据为代表的新生产要素的融合与创新配置&#xff0c;不仅成为推动新质生产力发展的…

开发语言Java+前端框架Vue+后端框架SpringBoot开发的ADR药物不良反应监测系统源码 系统有哪些优势?

开发语言Java前端框架Vue后端框架SpringBoot开发的ADR药物不良反应监测系统源码 系统有哪些优势&#xff1f; ADR药物不良反应监测系统具有多个显著的优势&#xff0c;这些优势主要体现在以下几个方面&#xff1a; 一、提高监测效率与准确性&#xff1a; 通过自动化的数据收集…