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

数据结构基础:P3-树(上)----编程作业02:List Leaves

本系列文章为浙江大学陈越、何钦铭数据结构学习笔记,系列文章链接如下

数据结构(陈越、何钦铭)学习笔记

文章目录

  • 一、题目描述
  • 二、整体思路与实现代码


一、题目描述

题目描述: 给定一棵树,按照从上到下、从左到右的顺序列出所有叶结点。
输入格式: 每个输入文件包含一个测试用例。对于每种情况,第一行给出一个正整数N(≤10),为树中的结点总数,结点编号从0到N-1。接着是N行,每一行对应一个结点,并给出该结点的左、右子结点的索引。如果子结点不存在,则在相应位置上给出“-”。任何一对子结点都用一个空格隔开。
输出格式: 对于每个测试用例,在一行中按从上到下、从左到右的顺序打印所有的叶结点索引。相邻数字之间必须有一个空格,行尾不能有多余的空格。
输入样例:
8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6
输出样例:
4 1 5

二、整体思路与实现代码

思路分析

①建树:读取各个节点,存放在一个数组中,建立一棵树。
②找到这棵树的根节点:把数组从头到尾扫描一遍,然后看看有没有哪个结点不存在其他结点指向他。如果没人指向他,他就是根结点了,非根结点肯定有人指向他了。
③层序输出叶节点:层序输出在前面文章已经将讲解过,首先将根结点入队,然后开始执行循环:结点出队、访问该结点、其左右儿子入队。在此基础上,我们加上对节点属性的判定,如果是叶子节点则将节点编号保存在一个数组中。最后通过便利保存节点编号的数组,将叶子节点编号输出。

整体代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MaxTree 10
#define Null -1    //子树为空时定义为Null
#define Tree int//定义树节点
struct TreeNode {Tree left;   //左子树的下标 Tree right;  //右子树的下标 
}T[MaxTree];//定义一个队列,用于中序遍历时进行入队出队操作
struct Queue {Tree data[MaxTree];  //保存Tree节点int front;  //队首int rear;   //队尾
}Q;//建立一棵树,并返回根节点
Tree BuildTree(struct TreeNode T[])
{int n;    //输入n个节点int i;    Tree Root; //最后找到的根节点int check[MaxTree]; //记录当前各个节点是否已访问char cl, cr;        //保存输入的左、右节点scanf("%d", &n); //输入的ngetchar();//读取回车if (n) {for (i = 0; i < n; i++) check[i] = 0; //初始化各个节点均未被访问for (i = 0; i < n; i++) {		scanf("%c %c", &cl, &cr); //输入的左、右节点getchar();//读取回车	/*对cl的对应处理 */if (cl != '-') {T[i].left = cl - '0';check[T[i].left] = 1;}else T[i].left = Null;/*对cr的对应处理 */if (cr != '-') {T[i].right = cr - '0';check[T[i].right] = 1;}else T[i].right = Null;}//n个节点中没有被check的就是根节点for (i = 0; i < n; i++)if (!check[i]) break;Root = i;}return Root;
}void LevelOrderTraversal(Tree root)
{if (!root) return;     //若是空树则直接返回Tree leaves[MaxTree];  //保存叶子节点/*初始化队列 根结点放到队列里面去*/Q.front = -1;Q.rear = -1;Q.data[++Q.rear] = root;int t = 0; //用于记录叶节点数量/*然后接下来是一个循环循环做三件事情:第一件事情 从队列里面抛出一个元素第二件事情 把队列刚抛出元素的Data print出来第三件事情 是把它的左右儿子放到队列里去*/while (Q.front != Q.rear) {	 //队列不为空时int i = Q.data[++Q.front];	 //出队if (T[i].left == Null && T[i].right == Null) { //叶节点leaves[t++] = i;}else { //非叶节点,左右子树若存在就入队if(T[i].left != Null)Q.data[++Q.rear] = T[i].left;if (T[i].right != Null)Q.data[++Q.rear] = T[i].right;}		}//实现最后一个节点后面没有空格,其它节点后面有空格for (int i = 0; i < t; i++) {if(i < t - 1)printf("%d ", leaves[i]);elseprintf("%d", leaves[i]);}
}int main()
{Tree A = BuildTree(T);LevelOrderTraversal(A);return 0;
}

运行,输入测试样例,结果正确
在这里插入图片描述

相关文章:

数据结构基础:P3-树(上)----编程作业02:List Leaves

本系列文章为浙江大学陈越、何钦铭数据结构学习笔记&#xff0c;系列文章链接如下&#xff1a; 数据结构(陈越、何钦铭)学习笔记 文章目录 一、题目描述二、整体思路与实现代码 一、题目描述 题目描述&#xff1a; 给定一棵树&#xff0c;按照从上到下、从左到右的顺序列出所有…...

山西电力市场日前价格预测【2023-08-25】

日前价格预测 预测明日&#xff08;2023-08-25&#xff09;山西电力市场全天平均日前电价为314.22元/MWh。其中&#xff0c;最高日前电价为336.17元/MWh&#xff0c;预计出现在18: 30。最低日前电价为283.05元/MWh&#xff0c;预计出现在24: 00。 价差方向预测 1&#xff1a; 实…...

手机无人直播软件,有哪些优势?

近年来&#xff0c;随着手机直播的流行和直播带货的市场越来越大&#xff0c;手机无人直播软件成为许多商家开播带货的首选。在这个领域里&#xff0c;声音人无人直播系统以其独特的优势&#xff0c;成为市场上备受瞩目的产品。接下来&#xff0c;我们将探讨手机无人直播软件给…...

SpringBoot概述SpringBoot基础配置yml的使用多环境启动

&#x1f40c;个人主页&#xff1a; &#x1f40c; 叶落闲庭 &#x1f4a8;我的专栏&#xff1a;&#x1f4a8; c语言 数据结构 javaEE 操作系统 石可破也&#xff0c;而不可夺坚&#xff1b;丹可磨也&#xff0c;而不可夺赤。 SpringBoot简介 一、 SpringBoot概述1.1 起步依赖…...

Python Pandas 处理Excel数据 制图

目录 1、饼状图 2、条形统计图 1、饼状图 import pandas as pd import matplotlib.pyplot as plt import numpy as np #from matplotlib.ticker import MaxNLocator # 解决中文乱码 plt.rcParams[font.sans-serif][SimHei] plt.rcParams[font.sans-serif]Microsoft YaHei …...

如何自己实现一个丝滑的流程图绘制工具(五)bpmn的xml和json互转

背景 因为服务端给的数据并不是xml&#xff0c;而且服务端要拿的数据是json&#xff0c;所以我们只能xml和json互转&#xff0c;来完成和服务端的对接 xml转json import XML from ./config/jsonxml.js/*** xml转为json* param {*} xml*/xmlToJson(xml) {const xotree new X…...

mysql--数据库的操作

数据库&#xff0c;是数据存储的最大单元。 1 创建数据库 create database mydatabase; 每次创建数据库的时候&#xff0c;都会多一个文件夹&#xff0c;关系型数据库是存储在磁盘当中的&#xff0c;所以这时候可以查看新建的数据库 2 指定字符集 MySQL中的字符集转换过程 制…...

kafka--技术文档--架构体系

架构体系 Kafka的架构体系包括以下几个部分&#xff1a; Producer. 消息生产者&#xff0c;就是向Kafka broker发送消息的客户端。Broker. 一台Kafka服务器就是一个Broker。一个集群由多个Broker组成。一个Broker可以容纳多个Topic。Topic. 可以理解为一个队列&#xff0c;一…...

ctfshow web入门 web103-web107

1.web103 和102一样 payload: v2115044383959474e6864434171594473&v3php://filter/writeconvert.base64-decode/resource1.php post v1hex2bin2.web104 值只要一样就可以了 payload: v21 post v113.web105 考查的是$$变量覆盖,die可以带出数据,输出一条消息&#xf…...

前端工程化之模块化

模块化的背景 前端模块化是一种标准&#xff0c;不是实现理解模块化是理解前端工程化的前提前端模块化是前端项目规模化的必然结果 什么是前端模块化? 前端模块化就是将复杂程序根据规范拆分成若干模块&#xff0c;一个模块包括输入和输出。而且模块的内部实现是私有的&…...

文件服务器实现方式汇总

hello&#xff0c;伙伴们&#xff0c;大家好&#xff0c;今天这一期shigen来给大家推荐几款可以一键实现文件浏览器的工具&#xff0c;让你轻松的实现文件服务器和内网的文件传输、预览。 基于node 本次推荐的是http-server&#xff0c; 它的githuab地址是&#xff1a;http-s…...

ChatGPT计算机科学与技术专业的本科毕业论文,2000字。论文查重率低于30%。

目录 摘要 Abstract 绪论 1.1 研究背景 1.2 研究目的和意义 2.1 ChatGPT技术概述 2.2 ChatGPT技术的优缺点分析 2.2.1 优点 2.2.2 缺点 摘要 本论文围绕ChatGPT展开&#xff0c;介绍了该技术的发展历程、特点及应用&#xff0c;分析了该技术的优缺点&#xff0c;提出了…...

【Winform学习笔记(八)】通过委托实现跨窗体传值

通过委托实现跨窗体传值 前言正文1、委托及事件2、通过委托实现跨窗体传值的步骤1.在子窗体中定义委托2.在子窗体中声明一个委托类型的事件3.调用委托类型事件4.在实例化子窗体后&#xff0c;子窗体订阅事件接受方法5.实现具体的事件 3、具体示例4、完整代码5、实现效果 前言 …...

Windows用户如何安装Cpolar

目录 概述 什么是cpolar&#xff1f; cpolar可以用在哪些场景&#xff1f; 1. 注册cpolar帐号 1.1 访问官网站点 2. 下载Windows版本cpolar客户端 2.1 下载并安装 2.2 安装完验证 3. token认证 3.1 将token值保存到默认的配置文件中 3.2 创建一个随机url隧道&#x…...

C++最易读手撸神经网络两隐藏层(任意Nodes每层)梯度下降230820a

这是史上最简单、清晰&#xff0c;最易读的…… C语言编写的 带正向传播、反向传播(Forward ……和Back Propagation&#xff09;……任意Nodes数的人工神经元神经网络……。 大一学生、甚至中学生可以读懂。 适合于&#xff0c;没学过高数的程序员……照猫画虎编写人工智能、…...

机器学习理论笔记(二):数据集划分以及模型选择

文章目录 1 前言2 经验误差与过拟合3 训练集与测试集的划分方法3.1 留出法&#xff08;Hold-out&#xff09;3.2 交叉验证法&#xff08;Cross Validation&#xff09;3.3 自助法&#xff08;Bootstrap&#xff09; 4 调参与最终模型5 结语 1 前言 欢迎来到蓝色是天的机器学习…...

10*1000【2】

知识: -----------金融科技背后的技术---------------- -------------三个数字化趋势 1.数据爆炸&#xff1a;internet of everything&#xff08;iot&#xff09;&#xff1b;实时贡献数据&#xff1b;公有云服务->提供了灵活的计算和存储。 2.由计算能力驱动的&#x…...

“探秘JS加密算法:MD5、Base64、DES/AES、RSA你都知道吗?”

目录 1、什么是JS、JS反爬是什么&#xff1f;JS逆向是什么? 2、JS逆向的大致流程 3、逆向的环境搭建 3.1、安装node.js 3.2、安装js代码调试工具(vscode) 3.3、安装PyExecJs模块 4、JS常见加密算法 4.1、Base64算法 4.2、MD5算法 4.3、DES/AES算法 4.2.2 AES与DES的…...

Spark项目Java和Scala混合打包编译

文章目录 项目结构Pom完整文件编译查看 实际开发用有时候引用自己写的一些java工具类&#xff0c;但是整个项目是scala开发的spark程序&#xff0c;在项目打包时需要考虑到java和scala混合在一起编译。 今天看到之前很久之前写的一些打包编译文章&#xff0c;发现很多地方不太对…...

深度学习处理文本(NLP)

文章目录 引言1. 反向传播1.1 实例流程实现1.2 前向传播1.3 计算损失1.4 反向传播误差1.5 更新权重1.6 迭代1.7 BackPropagation & Adam 代码实例 2. 优化器 -- Adam2.1 Adam解析2.2 代码实例 3. NLP任务4. 神经网络处理文本4.1 step1 字符数值化4.2 step 2 矩阵转化为向量…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...