树2 List Leaves（C语言）

树2 List Leaves（C语言） 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.
第一行给一个正整数表示树的总共结点数量，树的结点以0到N-1编号。然后N行，每一行相当于一个结点，给出结点的左儿子和右儿子，如果儿子不存在，则在对应位置上写“-”。每对儿子用空格分隔

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

代码如下

编程环境：VisualStudio2017

#include
#include
#include

#define ElementType int
#define MaxSize 10
#define Tree int
#define Null -1
#define ERROR -1
struct QNode
{
	ElementType *Data;
	int Rear;
	int Front;
	int maxsize;
};

typedef struct QNode *Queue;

Queue CreateQueue(int MaxSizee) {
	Queue Q = (Queue)malloc(sizeof(struct QNode));
	Q->Data = (ElementType*)malloc(MaxSizee * sizeof(ElementType));
	Q->Front = Q->Rear = 0;
	Q->maxsize = MaxSizee;
	return Q;
}

bool IsFull(Queue Q)
{
	return ((Q->Rear + 1) % Q->maxsize == Q->Front);
}

bool AddQ(Queue Q, ElementType X)
{
	if (IsFull(Q)) {
		//printf("队列满");
		return false;
	}
	else {
		Q->Rear = (Q->Rear + 1) % Q->maxsize;
		Q->Data[Q->Rear] = X;
		return true;
	}
}

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

ElementType DeleteQ(Queue Q)
{
	if (IsEmpty(Q)) {
		//printf("队列空");
		return ERROR;
	}
	else {
		Q->Front = (Q->Front + 1) % Q->maxsize;
		return  Q->Data[Q->Front];
	}
}

struct TreeNode
{
	ElementType Data;
	Tree Left;
	Tree Right;
}T1[MaxSize];

Tree BuildTree(struct TreeNode T[]) {
	int N, check[MaxSize], j, Root = Null;
	char cl, cr;
	scanf("%dn", &N);
	if (N) {
		for (int i = 0; i < N; i++)	check[i] = 0;
		for (int i = 0; i < N; i++)
		{
			scanf("%c %cn", &cl, &cr);
			T[i].Data = i;
			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 (j = 0;j < N;j++) {
			if (!check[j]) break;
		}
		Root = j;
	}
	return Root;
}

void LevelOrderTraversal(int Root)
{
	Queue Q;
	int tmp;
	if (Root == Null) return;
	Q = CreateQueue(MaxSize);
	AddQ(Q, Root);
	while (!IsEmpty(Q))
	{
		tmp = DeleteQ(Q);
		if ((T1[tmp].Left == Null) && (T1[tmp].Right == Null))
		{
			printf("%d", T1[tmp].Data);
			if (!IsEmpty(Q)) printf(" ");
		}
		if (T1[tmp].Left!=Null) AddQ(Q, T1[tmp].Left);
		if (T1[tmp].Right!=Null) AddQ(Q, T1[tmp].Right);
	}

}


int main() {
	Tree R1;
	R1 = BuildTree(T1);
	LevelOrderTraversal(R1);
	//system("pause");
	return 0;
}