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

//bitree struct
typedef struct BitNode{
	char	data;
	struct BitNode	*lchild, *rchild;
}BitNode, *BiTree;

/*
    the node pointer point at one of the elements of the tree
    there is a TreeNum array,start from  TreeNum[1],
    and from the top down,from left to right,
    set each node of the tree a number
    like TreeNum[1]=root
*/
typedef struct{
    struct BitNode *node;
}TreeNum;


int count;//count the number of element of tree
int lackChild;//the flag whether the node has child node
int isperfect;//the flag whether the tree is perfect rightnow!

//creat binary tree
void creatBiTree(BiTree &p, FILE *fp){
	//First traversal
	char ch;

	fscanf(fp, "%c",&ch);
	count++;
	if(ch == '\n') {p = NULL;return;}
    printf("%c",ch);
    
	if(ch =='#') p = NULL; //'#' represent null
	else{
		if( !(p = (BitNode *)malloc(sizeof(BitNode) ) ) ) exit(1);
		
		p->data = ch;
		creatBiTree(p->lchild,fp);
		creatBiTree(p->rchild,fp);
	}//else
}//CreatBiTree

void setTreeNumber(BiTree &T, int i,TreeNum num[100]){
	
	//set squence Traverse number
    num[i].node=T;
    if(T==NULL) return;

    printf("%d:%c ",i,num[i].node->data);
	//it's left child's number is 2i
	if(count>=2*i)
	   setTreeNumber(num[i].node->lchild,2*i,num);
	//it's right child's number is 2i+1
    if(count>=2*i+1)
	   setTreeNumber(num[i].node->rchild,2*i+1,num);
	
}

void sequenceTra(BiTree &T){
	//if the tree now has been judged as a imperfect tree,return
    if(T==NULL) return;
	//if the forward node lack child
    if(lackChild==1){
        if(T->lchild != NULL || T->rchild != NULL){
            isperfect=0;
			return;
        }//if
    }//if
    //if the forward node don't lack child
    else{
        if(T->lchild == NULL || T->rchild == NULL){
            lackChild=1;
            if(T->lchild == NULL)
                if(T->rchild != NULL){
                    isperfect=0;
					return;
                }//if
             //if
        }//if
     }//else
}//sequenceTra

void main(){
	
	BiTree	T[3];
	TreeNum number[3][100];//assume the tree has 99 elements,number[0]=null
	int k=0,countOfTree=3;
    int i;
	FILE *fp;
	if( !(fp = fopen("experiment2-1.in","r")) )
		exit(1);
	
	//pointer point next row in the file
	printf("There are %d trees\n",countOfTree);
	
    while(k<countOfTree){
	   //flags recover initialization	
	   lackChild=0;
	   count=0;
	   isperfect=1;

	   printf("No.%d tree:\n",k+1);
	   //creat a binary tree
	   creatBiTree(T[k],fp);
	   printf("\n");
       //if this is the last tree,colse the file
	   if(k==countOfTree-1)	fclose(fp);
	   //we don't use number[][0],the set as null
       number[k][0].node=NULL;
	
	   //if this is a empty tree
       if(T[k]==NULL){
           printf("This is an empty tree then a perfect binary tree\n\n");
           k++;
           system("pause");
           continue;
       }
       
       //set the element
       printf("\nsequence number:\n");
       setTreeNumber(T[k],1,number[k]);
	
       //sequence traveral,judge T is a perfect binary tree or not
	   int deep=(int)( log( (double)(count-3) ) / log(2.0) )+1;

       for(i=1;i<=pow(2.0,(double)(deep-1))-0.5;i++){//stop at last element of deep-1 layer
	        if(!isperfect)	break;
            sequenceTra(number[k][i].node);
       }
	   if(isperfect)
		  printf("\nThis is a perfect binary tree\n");
	   else
		  printf("\nThis is not a perfect binary tree\n");
	   system("pause");

	   k++;
	}	
}