基础实验4-2.2 列出叶结点

对于给定的二叉树，本题要求你按从上到下、从左到右的顺序输出其所有叶结点。

输入格式：

首先第一行给出一个正整数 n（≤10），为树中结点总数。树中的结点从 0 到 n−1 编号。随后 n 行，每行给出一个对应结点左右孩子的编号。如果某个孩子不存在，则在对应位置给出 "-"。编号间以 1 个空格分隔。

输出格式：

在一行中按规定顺序输出叶结点的编号。编号间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

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

输出样例：

4 1 5

代码实现

#include<stdio.h> 
#include<stdlib.h> 
#define MAXN 10
#define Tree int
#define Null -1//表示左右儿子为空的情况 
struct TreeNode{
	Tree left;
	Tree right;
};
struct TreeNode T1[MAXN];

typedef enum { false, true } bool;
typedef Tree ElementType;//树的节点编号放入队列 

/*-----队列的定义-----*/
typedef int Position;
typedef struct QNode *PtrToQNode;
struct QNode {
	ElementType *Data;
	Position Front, Rear;
	int MaxSize;
};
typedef PtrToQNode Queue;

Queue CreateQueue( int MaxSize );
bool IsEmptyQ( Queue Q );
void AddQ( Queue Q, ElementType X );
ElementType DeleteQ( Queue Q );
/*-----队列的定义结束-----*/


//===============队列操作------------------------ 
Queue CreateQueue( int MaxSize )
{
	Queue Q = (Queue)malloc(sizeof(struct QNode));
	Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
	Q->Front = Q->Rear = 0;
	Q->MaxSize = MaxSize;
	return Q;
}

bool IsEmptyQ( Queue Q )
{
	return (Q->Front == Q->Rear);
}

void AddQ( Queue Q, ElementType X )
{ /* 简版入列，不检查队列满的问题 */
	Q->Rear = (Q->Rear+1)%Q->MaxSize;
	Q->Data[Q->Rear] = X;
}

ElementType DeleteQ( Queue Q )
{ /* 简版出列。不检查队列空的问题 */
	Q->Front =(Q->Front+1)%Q->MaxSize;
	return  Q->Data[Q->Front];
}

//------------树的构造----------------- 
Tree buildTree(struct TreeNode T[]) {
	char cl,cr;
	int root;//数根 
	int n,i,check[MAXN];//用于寻找树的根节点 
	scanf("%d\n",&n);
	
	if(n){
		for(i=0;i<n;i++)
			check[i]=0; 
		for(i=0;i<n;i++){
			scanf("%c %c\n",&cl,&cr);
			if(cl!='-'){
				T[i].left=cl-'0';
				check[T[i].left]=1;
			}else
				T[i].left=Null;
			if(cr!='-'){
				T[i].right=cr-'0';
				check[T[i].right]=1;
			}else
				T[i].right=Null;
		}
		
		for(i=0;i<n;i++)
			if(!check[i])
				break;
		root=i;
		return root;	 
	}
	return Null;//n为0情况，根节点就返回-1 
	
}
//--------------------树层序遍历-------------
void levelOrderTraversal(Tree t){
	
	Queue q;
	Tree tmp;
	int flag=0;//用于区别收尾输出的空格 
	if(t==-1)
		return;
	q=CreateQueue(MAXN);
	AddQ(q,t);
	while(!IsEmptyQ(q)){
		tmp=DeleteQ(q);
		if(T1[tmp].left==Null&&T1[tmp].right==Null)//只输出叶节点
			if(!flag){//首次输出 
				printf("%d",tmp);
				flag=1;
			}else
				printf(" %d",tmp);
		
		if(T1[tmp].left!=Null)//有左孩子，就加入队列，等待下一层遍历
			AddQ(q,T1[tmp].left);
		if(T1[tmp].right!=Null)//有左孩子，就加入队列，等待下一层遍历
			AddQ(q,T1[tmp].right);
	}
	
}

int main(){
	Tree root = buildTree(T1);
	
	levelOrderTraversal(root);
	
	
	return 0;
}