03-树2 List Leaves（25 分）

题意：按层次输出叶子节点

思路：由于数据都是小于10的整数，所以可以用数组存储二叉树，层次遍历二叉树则需要一个队列存储每一层的节点。遇到叶子节点就输出。

#include<stdio.h>
struct node{   //数组用来存储二叉树 
	int data;
	int left;
	int right;
}tr[10];

int main()
{
	int N,i,M=0;
	int check[10]={0};
	scanf("%d",&N);
	getchar();                         //读入换行符 
	for(i=0;i<N;i++){
		char l,r;
	    scanf("%c %c",&l,&r);        //读入左右孩子 
	    getchar();
	    if(l=='-'&&r=='-')M++;        //叶子节点个数 
	    tr[i].data=i;                  //节点数据 
	    tr[i].left=l=='-'?-1:l-'0';    
	    tr[i].right=r=='-'?-1:r-'0'; 
	    if(l!='-')check[l-'0']=1;     //查找根节点 
	    if(r!='-')check[r-'0']=1;
	}
	int queue[10]={0},rear=-1,front=-1;   //设置队列，按层次输出 
	struct node p;
	for(i=0;i<N;i++)         //根节点 
	{
	    if(check[i]==0)queue[++rear]=i;    //队尾插入根节点 
	}
	while(front!=rear){                       //队列不为空 
		p=tr[queue[++front]];                 //队头取出节点 
		if(p.left!=-1)queue[++rear]=p.left;   //队尾插入左孩子
		if(p.right!=-1)queue[++rear]=p.right; //队尾插入右孩子 
		if(p.left==-1&&p.right==-1){          //输出叶子节点 
		    printf("%d",p.data);
		    M--;
		    if(M)printf(" ");
		}
	}
	return 0;
}