PTA-数据结构 编程题03-树2 List Leaves (25 分)

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

Input Specification:

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.

Output Specification:

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.

Sample Input:

8
1 -
- -
0 -
2 7
- -
- -

5 -

4 6

Sample Output:

4 1 5

#include <stdio.h>
#define MaxSize 10
#define Tree int
#define Null -1

typedef char ElementType;

/********二叉树结构体************/ 
struct TreeNode{
    Tree Left;
    Tree Right;
}T[MaxSize];

Tree check[MaxSize];
int N;

/********创建二叉树************/ 
Tree BulidTree( struct TreeNode T[])
{
	//freopen("test.txt", "r",stdin);
	int i;
	Tree Root = Null;   //若为空树，直接返回NULL； 
	char cl, cr;

	scanf("%d", &N);
	
	if(N)
	{
		for( i = 0; i < N; i++ )	check[i] = 0;  //用于判断  根节点 
		for( i = 0; i < N; i++) 
		{
			scanf("\n%c %c", &cl, &cr);  //  \n  是为了把上一个输入的回车替换掉 

			if( cl != '-' )
			{
				T[i].Left = cl - '0';
				check[ T[i].Left ] = 1;   //  T[i].Left 有指向   令该节点所在的 check设为 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;  //不被任何数指向的（check[i] == 0 的地方）  所在的位置 就为根节点所在的位置 
		Root = i;
	}
	return Root;
}

/********输出叶子节点************/ 
void OrderTraversal( Tree R )
{
	int leaves[MaxSize];    //记录输出叶节点个数，使输出时第一个节点输出前没有空格
	int i, K = 0;
	
	//建一个队列来存放节点下标
	int Q[MaxSize];
	int front = 0, rear = 0; 
	Q[ rear++ ] = R;   //根节点入队 
	
	while( rear - front )
	{ 
		int node = Q[ front++ ]; // 队头节点出队
		 
		if( ( T[ node ].Left == Null ) && ( T[ node ].Right == Null ) )
		{
			leaves[ K++ ] = node;
		} 
		if( T[ node ].Left != Null)		Q[ rear++ ] = T[ node ].Left;    //如果左节点不空，左儿子入队	
		if( T[ node ].Right != Null)	Q[ rear++ ] = T[ node ].Right;    //如果左节点不空，左儿子入队		
	}
	
	for( i = 0; i < K-1; i++)	printf( "%d ", leaves[i] );
	printf( "%d\n", leaves[K-1] );
	
 } 

int main()
{
    Tree R;
    
	R = BulidTree( T );
    OrderTraversal( R ); 
    
    return 0;
}