List Leaves【データ構造試験3.2】

タイトル:
Gven 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 ars res.ore.The Nberrows.front.Theand gives the indices of the left and right children of the node.If the child does not exist,a'-'will be put the position.Any pair of childrene e e e separated bya space.Output Specification:Foress the the the ineseand left to right.The e must be exactly one space between any adjacent numbers,and no extra spacact the end of the line.Sample Input:8--0-2 7--5-4 Sample Oput:
4 1 5
テーマ説明:(参考:http://blog.csdn.net/conjimmy/article/details/42118037)
この問題は完全に二叉の木の順番コードではなく、リンクテーブルのように入力ノードにサブノード情報が付いていますが、ツリーの構造とルートの結点は自分で確定する必要があります.
コードの注釈が多いです.

// ListLeaves.cpp :              。
//

#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <fstream>
using namespace std;

#define MAXSIZE 10
typedef struct TNode *BinTree;
typedef struct TNode
{
	BinTree left;
	BinTree right;
	int isRoot;
	int data;
}TNode;

typedef struct Queue
{
	TNode* node[MAXSIZE];
	int rear;	
	int front;
}Queue;

bool isEmpty(Queue *queue)
{
	if(queue->front == queue->rear)
		return true;
	return false;
}

Queue* initQueue(Queue* queue)//    -     
{
	queue->front = queue->rear = 0;
	return queue;
}

void push(Queue* queue,TNode* node)
{
	queue->node[queue->rear] = node;
	queue->rear++;//        
}

TNode* pop(Queue *queue)
{
	TNode* temp = queue->node[queue->front];
	queue->front++;//        
	return temp;//         
}
TNode* list[MAXSIZE];
TNode* inProc()//    ，  ，     
{
	int n;//    
	cin>>n;
	if(n == -1)	return NULL;

	char ileft[2],iright[2];//     
	TNode* bt = NULL;//     
	for(int i = 0; i < n; i++)//  n   ，  '-' null     ，   int    
	{
		cin>>ileft>>iright;
		bt = (TNode*)malloc(sizeof(TNode));
		
		//   
		if(ileft[0] == '-'){
			bt->left = NULL;
		}
		else{
			bt->left = (TNode*)malloc(sizeof(TNode));//        ，      
			bt->left->data = atoi(ileft);//    int
		}

		//   
		if(iright[0] == '-'){
			bt->right = NULL;
		}
		else{
			bt->right =  (TNode*)malloc(sizeof(TNode));
			bt->right->data = atoi(iright);
		}
		list[i] = bt;//          
	}

	for(int i = 0; i < n; i++)//      
	{
		TNode* p = NULL;//    p   list        
		p = list[i];
		if(p->left != NULL)
		{
			int tmp = p->left->data;
			p->left = list[tmp];//  list                (list[3]    2 7，   list[3]->left list[2]、eftlist[7]    )
			p->left->data = tmp;
			p->left->isRoot = 1;
			//cout<<"bt is:"<<p->left->data<<endl;
			//list[list[i]->left->data]->isRoot = 1;//1    root
		}
		if(p->right != NULL)
		{
			int tmp = p->right->data;
			p->right = list[tmp];//  list                (list[3]    2 7，   list[3]->left list[2]、eftlist[7]    )
			p->right->data = tmp;
			p->right->isRoot = 1;
			//cout<<"bt is:"<<p->right->data<<endl;
			//list[list[i]->right->data]->isRoot = 1;
		}
	}
	//     
	TNode* root = NULL;
	for(int i = 0; i < n; i++)
	{
		root = list[i];
		if(root->isRoot != 1)
			break;
	}
	return root;//     
}


int main()
{
	Queue queue;
	Queue *q = &queue;
	q = initQueue(q);
	TNode * root = inProc();
	push(q,root);
	int isFirst = 1;//        ，           
	while (!isEmpty(q))
	{//       ：     ，  (       ，  (   )   ，  (   )   )
		TNode * tmp=pop(q);//  
		if((tmp->right==NULL)&&(tmp->left==NULL))//  
		{
			if(isFirst)
			{
				cout<<tmp->data;
				isFirst = 0;
			}
			else
			{
				cout<<" "<<tmp->data;
			}
		}

		if(tmp->left)//      
			push(q,tmp->left);
		if(tmp->right)//      
			push(q,tmp->right);
	}


	return 0;
}