List Leaves

本题是建立树的基本操作，同时通过使用队列的方法从上到下，从左到右的顺序输出叶节点，思路是广度优先算法。

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

C语言代码如下：

#include<stdio.h>
#include<stdlib.h>

#define maxsize 10
#define tree int
#define NULL -1

struct treenode
{
	tree left;
	tree right;
}T[maxsize];

//构建队列
int K;
tree queue[maxsize];//层序遍历
int first = 0, last = -1;
void push(tree t)
{
	queue[++last] = t;
	return;
}
void pop()
{
	++first;
	return;
}
tree top()
{
	return queue[first];
}
//
tree bulidtree(struct treenode T[]);
void printleaves(tree R);

int main()
{
	tree a = bulidtree(T);
	printleaves(a);
	return 0;
}

tree bulidtree(struct treenode T[])//建立树，返回树根节点
{
	int k;
	scanf("%d", &k); K = k;
	getchar();
	if (k == 0)return NULL;
	//C语言的写法
	int *check;
	check = (int*)malloc(sizeof(int)*k);
	//C++的写法
	//int *check = new int[k];
	int i;
	for (i = 0; i < k; i++)//先设置为0
		check[i] = 0;
	for (i = 0; i < k; i++)
	{
		char tep1, tep2;
		scanf("%c %c", &tep1, &tep2);
		getchar();
		if (tep1 == '-')T[i].left = NULL;
		else
		{
			T[i].left = tep1 - '0';
			check[T[i].left] = 1;
		}
		if (tep2 == '-')T[i].right = NULL;
		else
		{
			T[i].right = tep2 - '0';
			check[T[i].right] = 1;
		}
	}
	for (i = 0; i < k; i++)
		if (!check[i])break;
	return i;
}

void printleaves(tree R)
{
	tree up = R;
	push(R);
	int flag = 0;
	for (int i = 0; i < K;)//退出条件为pop了K次
	{
		if (T[up].left != NULL)
		{
			push(T[up].left);
		}
		if (T[up].right != NULL)
		{
			push(T[up].right);
		}
		if (T[up].left != NULL || T[up].right != NULL)//不是叶子节点
		{
			pop(); up = top(); i++;
		}
		else
		{
			if (flag)
			{
				printf(" %d", up);
				pop(); up = top(); i++;
			}
			else
			{
				printf("%d", up);
				pop(); up = top(); i++;
				flag = 1;
			}

		}
	}
	//以下代码可以实现树的叶节点从左往右遍历
	//if (T[R].left == NULL&&T[R].right == NULL)
	//{
	//	printf("%d ", R);
	//	return;
	//}
	//else if (T[R].left != NULL&&T[R].right == NULL)
	//	printleaves(T[R].left);
	//else if (T[R].right != NULL&&T[R].left == NULL)
	//	printleaves(T[R].right);
	//else
	//{
	//	printleaves(T[R].left);
	//	printleaves(T[R].right);
	//}
	//return;
}