//实现中序线索化二叉树

#include
#include
#include
#define	MaxSize 100

//实现中序线索化二叉树

typedef struct node{
	char data;		//数据域
	int ltag,rtag;	//线索标记
	struct node *lchild;	//左孩子指针
	struct node *rchild;	//右孩子 
}TBTNode;

//ltag、rtag为1：表示线索化 

//由str串建立含空线索域的二叉链b
void CreateTBTree(TBTNode *&b,char *str){
	TBTNode *St[MaxSize],*p;
	int top=-1,k,j=0;
	char ch=str[j];		//ch赋值为字符串的第一个字符
	b=NULL;		//初始化二叉树b 	
	while(ch!=''){		//扫描到结束符退出循环 
		switch(ch){
			case'(':
				top++;
				St[top] = p;	//St存储双亲结点 ,也就是上一个结点 
				k=1;		//k用于标记下个元素是不是左右孩子
				break;		//开始处理左子树
			case')':
				top--;		//删除一个St中的双亲元素 
				break;		//子树处理完毕
			case',':
				k=2;		//k=2,下个元素为右孩子 
				break;		//开始处理右子树	
			default:
				p=(TBTNode *)malloc(sizeof(TBTNode));
				p->data = ch;		//存储结点值 
				p->lchild = p->rchild = NULL;	//左右指针全指向NULL
				if (b==NULL)	
					b=p;	//若b为空，p置为二叉树根结点
							//这里修改了头指针，所以函数定义时，需要用&
							 
				else{		//若已经创建好根结点
					switch(k){		//这里用的k标记是上一轮循环标记好的 
						case 1:St[top]->lchild = p;		//St[top]存储了上一个结点p1
							//等价于 p1->lchild = p; 
								break;
						case 2: St[top]->rchild = p;
								break;
					} 
					
				} 
				 
		}
		j++;
		ch = str[j];
	}
	
} 

//输出含空线索域的二叉树 
void DispTBTree(TBTNode *b){
	if(b!=NULL){
		printf("%c",b->data);
		if(b->lchild != NULL || b->rchild != NULL){
			printf("(");	//有孩子结点时才输出(
			DispTBTree(b->lchild);	//递归处理左子树
			if(b->rchild != NULL)
				printf(",");		//有右孩子结点时才输出,
			DispTBTree(b->rchild);	// 递归处理右子树
			printf(")");	//有孩子结点时才输出)
		}
	}
}

TBTNode *pre;	//==========全局变量===================
 
//中序线索化二叉树，被CreateThread调用
void Thread(TBTNode *&p){
	if(p!=NULL){
		Thread(p->lchild);	//-------递归遍历左子树，并将其线索化 
		if(p->lchild == NULL){		//若左指针为空，将该指针作为线索保存前驱结点
			p->lchild = pre;	//p的前驱是pre，所以p的左孩子保存pre结点 
			p->ltag=1;		//标记该结点已经线索化 
		} else	//否则标记左指针不能被线索化
			p->ltag=0;
		if(pre->rchild == NULL)	{	//pre的后继是p，所以pre的右孩子保存p结点
		//注意此处判断的pre的右孩子是否为空  
			pre->rchild=p;
			pre->rtag=1; 
		}else
			pre->rtag=0;
		pre = p;	//修改前驱结点
		Thread(p->rchild);	//--------递归遍历右子树，并将其线索化 
	}
} 

//问题一：已经构建好了二叉树，并且在Thread中已经线索化了，那么CreateThread()函数有什么作用？
 

//创建中序线索化二叉树
TBTNode *CreateThread(TBTNode *b){
	TBTNode *root;
	root = (TBTNode *)malloc(sizeof(TBTNode));	//创建头结点
	root->ltag=0;	//左指针指向根结点 
	root->rtag=1;	//右指针用来线索化 
	root->rchild=b;//如果数b只有一个结点，那么头结点root的右指针指向最后一个结点 
	if(b==NULL)			//空二叉树 
		root->lchild = root; 
	else{
		root->lchild = b;
		pre = root;
		Thread(b);	
		pre->rchild = root;	//此时的pre为中序遍历的最后结点	
		pre->rtag = 1;
		root->rchild = pre; //将的右指针线索指向最后结点pre 
	}
	return root;
} 

// 被ThInOrder算法调用
void InOrder(TBTNode *tb){
	if(tb->lchild != NULL && tb->ltag == 0)		//有左孩子且没有被线索化
		InOrder(tb->lchild);
	printf("%c",tb->data);
	if(tb->rchild!=NULL && tb->rtag == 0)
		InOrder(tb->rchild); 
} 

//中序线索二叉树的中序遍历递归算法
void ThInorder(TBTNode *tb){
	InOrder(tb->lchild);
} 

//中序线索二叉树的中序遍历非递归算法
void ThInOrder1(TBTNode *tb){
	TBTNode *p = tb->lchild;	//指向根结点
	while(p!=tb){
		while(p->ltag == 0)		//找中序开始结点 
			p=p->lchild;
		printf("%c",p->data);
		while(p->rtag == 1 && p->rchild != tb){
			p=p->rchild;
			printf("%c",p->data);
		}
		p=p->rchild;
		
	} 
}

//被DestroyTBTree算法调用

void DestroyTBTree1(TBTNode *tb){
	if(tb!=NULL){
		if(tb->lchild != NULL && tb->ltag == 0)	//如果有左孩子，且没被线索化
			DestroyTBTree1(tb->lchild);
		if(tb->rchild != NULL && tb->rtag == 0)
			DestroyTBTree1(tb->rchild);
		free(tb); 
	}
} 

//释放中序线索二叉树的所有结点
void  DestroyTBTree(TBTNode * tb){
	DestroyTBTree1(tb->lchild);
	free(tb);
	printf("释放完成");
}

int main(){
	TBTNode *b,*tb;
	CreateTBTree(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))");
	printf("二叉树：");DispTBTree(b);printf("n");
	tb=CreateThread(b);
	tb=b;
	printf("线索中序序列：n");
	printf("  递归算法：");ThInorder(tb); printf("n");
	printf(" 非递归算法：");ThInOrder1(tb);printf("n");
	DestroyTBTree(tb);
	return 1;
}