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

#define	STACK_INIT_SIZE	100
#define	STACKINCREAMENT	10

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

void creatBiTree(BiTree &T, FILE *fp){
	//First traversal
	char ch;

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

typedef struct MyStack{
	
	BiTree *base;
	BiTree *top;
	int	stacksize;

}MyStack;

void initStack(MyStack &s){

	s.base = (BiTree *)malloc(sizeof(BiTree)*STACK_INIT_SIZE);
	if(!s.base) exit(1);
	s.top = s.base;
	s.stacksize = STACK_INIT_SIZE;

}

void stackPush(MyStack &s,BiTree &T){

	if(s.top-s.base >= s.stacksize){//stack is full
		
		s.base = (BiTree *)realloc(s.base,sizeof(BiTree)*(STACK_INIT_SIZE+STACKINCREAMENT));
		if(!s.base)	exit(1);
		s.top = s.base + s.stacksize;
		s.stacksize += STACKINCREAMENT;
	
	}
	
	*s.top++ = T;
}

void stackPop(MyStack &s,BiTree &T){

	if(s.top == s.base)	exit(1);

	T = *--s.top;

}

void preorder(BiTree &T){
	
	MyStack s;
	initStack(s);
	
	while(T || !(s.top == s.base) ){
		if(T != NULL){
			printf("%c",T->data);
			stackPush(s,T);
			T=T->lchild;
		}
		else{
			stackPop(s,T);
			T = T->rchild;
		}
	}//while
}

void main(){	
	BiTree T;	
	FILE *fp;
	if( !(fp = fopen("experiment2-2.in","r")) )
		exit(1);
	printf("Element of the tree of sequence storing:\n");	
	//creat a binary tree
	creatBiTree(T,fp);
	printf("\n");	
	fclose(fp);
	printf("preorder the effective element of the tree:\n");
	preorder(T);
	printf("\n");
	system("pause");
}