青岛电子商务的网站建设,网站上线后想修改,河源市新闻最新消息,深圳网站开发哪家专业本系列文章为浙江大学陈越、何钦铭数据结构学习笔记#xff0c;系列文章链接如下#xff1a; 数据结构(陈越、何钦铭)学习笔记 文章目录 一、题目描述二、整体思路与实现代码 一、题目描述
题目描述#xff1a; 给定一棵树#xff0c;按照从上到下、从左到右的顺序列出所有…本系列文章为浙江大学陈越、何钦铭数据结构学习笔记系列文章链接如下 数据结构(陈越、何钦铭)学习笔记 文章目录 一、题目描述二、整体思路与实现代码 一、题目描述
题目描述 给定一棵树按照从上到下、从左到右的顺序列出所有叶结点。 输入格式 每个输入文件包含一个测试用例。对于每种情况第一行给出一个正整数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;
}运行输入测试样例结果正确
