데이터 구조 - 단서 이 진 트 리 의 기본 동작

#include
#include

typedef struct Node{        //           
	char data;
	struct Node *Lchild;
	struct Node *Rchild;
	int Ltag;
	int Rtag;
}BiTNode,*BiTree;

void CreateBiTree(BiTree *root){      //        ，           
	char ch;
	ch=getchar();
	
	if(ch=='#')    *root=NULL;
	else{
		*root=(BiTree)malloc(sizeof(BiTree));
	    (*root)->data=ch; 
	    CreateBiTree(&((*root)->Lchild));
	    CreateBiTree(&((*root)->Rchild));
	}
} 

void Visit(char data){
	printf("%c",data);
}

void InOrder(BiTree T){      //       
	if(T){
		InOrder(T->Lchild);
		Visit(T->data);
		InOrder(T->Rchild);
	}
}

BiTree pre = NULL;     //    ，pre           
void Inthread(BiTree T){     //     (  )
     if(T!=NULL){
     	Inthread(T->Lchild);   //      
		 
		if(T->Lchild==NULL){    //      ，      
			T->Lchild=pre;
		 	T->Ltag=1;
		} 
     	if(pre!=NULL&&pre->Rchild==NULL){  //        ，       
     		pre->Rchild=T;
     		pre->Rtag=1;
		 }
		pre=T;
		Inthread(T->Rchild);  //      
	 }
} 

BiTree InPre(BiTree T){      //           
    BiTree Pre;
	if(T->Ltag==1) Pre=T->Lchild; //      
	else{
		for(BiTree q=T->Lchild;q->Rtag==0;q=q->Rchild)   // T               
			Pre=q;
	} 
	return (Pre); 
} 

BiTree InNext(BiTree T){     //          
    BiTree Next; 
	if(T->Rtag==1) Next=T->Rchild; //      
	else{
		for(BiTree q=T->Rchild;q->Ltag==0;q=q->Lchild)   // T               
			Next=q;
	} 
	return (Next); 
} 

BiTree InFirst(BiTree T){    //                
	BiTree p=T;
	if(p==NULL) return (NULL);
	
	while(p->Ltag==0) p=p->Lchild;
	return p;
}

void TiOrder(BiTree T){      //         
	BiTree p;
	p=InFirst(T);
	while(p!=NULL){
		Visit(p->data);
		p=InNext(p);
	} 
}

int main(){
	BiTree T;
	CreateBiTree(&T);
	InOrder(T);
	
	return 0;
}