단서 이 진 트 리 - 데이터 구조

교재 에 따라 중 서 이 진 트 리 의 단서 화 를 진행 하 다.
단서 화 는 이 진 트 리 가 많이 나 오 는 n + 1 개의 체인 도 메 인 을 가리 키 는 전구 와 후계 용 으로 사용 하 는 것 입 니 다. 전구 후계 란 이 진 트 리 가 발생 하 는 전구 와 후계 를 중간 순서에 따라 옮 겨 다 니 는 것 을 말 합 니 다.
왼쪽 아이 왼쪽 아이 없 이 앞잡이
rtag = 0 오른쪽 아이 rtag = 1 오른쪽 아이 없 이 후계
예 코드: 구조 이 진 트 리  ABC \ # \ # DE \ # \ # \ # FG \ # \ # \ #

#include
#include
#include

typedef char Elemtype; 

typedef enum PonintTag{Link,Tread};//Link==0,  ，Tread==1,      
//enum     http://blog.sina.com.cn/s/blog_817a5eb6010146ad.html   enum                
typedef struct TNode
{
	struct TNode *lchild,*rchild;
	Elemtype data;
	PonintTag ltag,rtag;
}TNode,*BinTree;

BinTree pre;  //     


////////////////////////////              ABC##DE###FG###
void CreatTree(BinTree &T)
{
	Elemtype ch;
	scanf("%c",&ch);
	if(ch=='#') T=NULL;
	else
	{
		T=(TNode*)malloc(sizeof(TNode));
		T->data=ch;
		CreatTree(T->lchild);
		CreatTree(T->rchild);
	}
}

void PreOrdTree(BinTree T)
{
	BinTree p;
	p=T;
	if(p)
	{
		printf("%c",p->data);
		PreOrdTree(p->lchild);
		PreOrdTree(p->rchild);
	}	
}

void InTreading(BinTree P)  //    
{
	if(P)
	{
		InTreading(P->lchild);//      
		if(!P->lchild)    //       ，         
		{
			P->ltag=Tread;   //           
			P->lchild=pre;  //       
		} 
		if(!pre->rchild)        //     
		{
			pre->rtag=Tread;
			pre->rchild=P;
		}
		pre=P; //  pre       
		InTreading(P->rchild); //       
	}
}

void InOrdTreading(BinTree &Thrt,BinTree T)
{
	Thrt=(TNode*)malloc(sizeof(TNode));
	Thrt->ltag=Link,Thrt->rtag=Tread;  //    Thrt 
	Thrt->rchild=Thrt;                 //      
	if(!T) Thrt->lchild=Thrt;          //    ，      
	else
	{
		Thrt->lchild=T;  //      
		pre=Thrt;           
 		InTreading(T); //    
		pre->rchild=Thrt;//         
		pre->rtag=Tread;
		Thrt->rchild=pre;
	}
}

void InOrdTrevalThrd(BinTree T)
{
	BinTree p;
	p=T->lchild;
	while(p!=T)
	{
		while(p->ltag==Link) p=p->lchild;
		printf("%d %c %d
",p->ltag,p->data,p->rtag);
		while(p->rtag==Tread && p->rchild!=T)
		{
			p=p->rchild;
			printf("%d %c %d
",p->ltag,p->data,p->rtag);
		}
		p=p->rchild;
	}
	//printf("
");
}

int main()
{
	BinTree Tree,Th;
	CreatTree(Tree);
	PreOrdTree(Tree); //      ，           
	printf("
");
	InOrdTreading(Th,Tree);
	InOrdTrevalThrd(Th);
	
	return 0;
}