【树】List Leaves

【树】List Leaves

题目要求：

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

输入格式：

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.

输出格式：

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.

输入样例：

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

输出样例：

4 1 5

解题思路：

1. 用静态链表实现，即结构体数组。
2. 需要进行层次遍历，层次遍历使用队列，先让根结点入队，然后弹出队列头结点，将弹出结点的左右孩子入队,再继续弹出队头元素，以此类推，直到队列为空。
3. 找根结点：所有结点都没有指向的结点就是根结点。
4. 判断结点是否为叶子结点：没有左右孩子的结点就是叶子结点。
5. 输入字字符是因为输入有可能为-，将表示整型的字符转换为整型即可。

注意：

1. 输入并不是有序的，输入只是表明了结点的左右孩子的情况，所以需要找根结点。
2. 注意尽量避免使用fflush函数来清空缓存区，因为编译器可能不支持，可以用getchar()来读取输入结束的回车符。

完整程序：

/*
【解题思路】 
1.用静态链表实现，即结构体数组
2.需要进行层次遍历，层次遍历使用队列，先让根结点入队，然后弹出队列头结点，将弹出结点的左右孩子入队,再继续弹出队头元素，以此类推
直到队列为空 
3.找根结点所有结点都没有指向的结点就是根结点
4.判断结点是否为叶子结点：没有左右孩子的结点就是叶子结点 
5.输入字字符是因为输入有可能为-，将表示整型的字符转换为整型即可 
*/
/*
【程序结构】
1.二叉树的表示，队列的表示
2.建树
3.层序遍历的同时判断是否为叶子结点，如果是叶子结点，则输出该结点 
*/ 
/*
【注意】输入并不是有序的，输入只是表明了结点的左右孩子的情况 
*/ 
#include <stdio.h>
#define Null -1 // 用-1表示空，因为编号为0的下标存储了结点
#define Tree int
#define MaxSize 10

typedef struct TNode {
	int Data;
	Tree Left;
	Tree Right;
} TreeNode;

TreeNode T[MaxSize];
TreeNode Queue[MaxSize];

int qFirst = 0,qLast = 0; // 定义队列的头尾指针，队空：头指针 = 尾指针，头指针指向第一个元素，尾指针指向最后一个元素的下一个位置 

Tree BuildTree(TreeNode T[]); // 建树
void LevelTraversal(Tree R); // 层次遍历 
TreeNode Pop(); //出队
void Push(TreeNode treeNode); // 入队 

int main()
{
	Tree R;
	R = BuildTree(T);
	LevelTraversal(R);
	return 0;
}

Tree BuildTree(TreeNode T[]) 
{
	Tree Root = Null; // 根结点默认置空
	char cl,cr; // 临时存储左右孩子，定义为字符类型
	int i,N,check[MaxSize]; // check用来表示结点是否被其他结点所指向 
	scanf("%d",&N);
	getchar(); // 读取缓存区的回车符 
	if(N) {
		for(i = 0;i < N;i ++)
			check[i] = 0;
		for(i = 0;i < N;i ++) {
			scanf("%c %c",&cl,&cr); 
			getchar(); // 读取缓存区的回车符 
			T[i].Data = i;
			if(cl == '-')
				T[i].Left = Null;
			else {
				T[i].Left = cl -'0';
				check[T[i].Left] = 1;  
			}
			if(cr == '-')
				T[i].Right = Null;
			else {
				T[i].Right = cr -'0';
				check[T[i].Right] = 1;  
			}
		}
		for(i = 0;i < N;i ++)
			if(check[i] == 0) Root = i;
	} 
	return Root;
}

void Push(TreeNode treeNode)
{
	Queue[qLast ++] = treeNode;
} 
 
TreeNode Pop()
{
	return Queue[qFirst ++]; // 没有真正的出队，只是让队头指针向后移一位 
} 

void LevelTraversal(Tree R)
{
	int leaves[MaxSize]; // 存放叶子结点 
	int i,nL = 0; // 叶子结点数（从0） 
	if(R == Null) return; // 若是空树直接返回 
	Push(T[R]); // 根结点入队 
	TreeNode TN;
	while(qFirst != qLast) { // 层序遍历结束的条件是队空 
		TN = Pop();
		if(TN.Left != Null)
			Push(T[TN.Left]);
		if(TN.Right != Null)
			Push(T[TN.Right]);
		if(TN.Left == Null && TN.Right == Null) // 判断是否为叶子结点 
			leaves[nL ++] = TN.Data;
	}
	nL --; // 多加了1 
	for(i = 0;i < nL;i ++)
		printf("%d ",leaves[i]);
	printf("%d",leaves[i]);	
}