数据结构基础：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;
}

运行，输入测试样例，结果正确