#include "stdio.h"#include "stdlib.h"#define OK 1#define ERROR 0typedef char TElemType;typedef char Elemtype;typedef int Status;typedef enum PointerTag {Link,Thread}; //link==0:pointer,Thread==1:threadtypedef struct BiThrNode{	TElemType data;	struct BiThrNode *lchild,*rchild;	PointerTag LTag,RTag;}BiThrNode,*BiThrTree;BiThrTree pre; // 全局变量,始终指向刚刚访问过的结点void InThreading(BiThrTree p){	if(p)	  {	   InThreading(p->lchild);//左子树线索化	   if(!p->lchild){p->LTag=Thread;p->lchild=pre;}//前驱线索	   if(!pre->rchild){pre->RTag=Thread;pre->rchild=p;}//后续线索	   pre=p; //保持pre指向p的前驱	   InThreading(p->rchild);//右子树线索化	  }//if}//InThreadingStatus InOrderThreading(BiThrTree &Thrt,BiThrTree T){//中序遍历二叉树，并将其中序线索化，Thrt指向头结点//BiThrTree Thrt;	if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(-1);	Thrt->LTag=Link; //建立头结点	Thrt->RTag=Thread; //右指针回指	Thrt->rchild=Thrt; 	if(!T) Thrt->rchild=Thrt; //若二叉树为空，则左指针回指	else {	     Thrt->lchild=T;	     pre=Thrt;	     InThreading(T);  //中序遍历进行中序线索化	     pre->rchild=Thrt;//最后一个结点线索化	     pre->RTag=Thread;	     Thrt->rchild=pre;	    }return OK;}//InOrderThreadingStatus InOrderTraverse_Thr(BiThrTree T){//T指向头结点，头结点的左链lchild指向根结点，非递归算法	BiThrTree p; 	p=T->lchild;	while(p!=T) //空树或遍历结束时，T＝＝p	 {		while(p->LTag==Link) p=p->lchild;		printf("%c",p->data); //访问其左子树为空的结点		while(p->RTag==Thread&&p->rchild!=T)          {	          p=p->rchild;              printf("%c",p->data); //访问后续结点          }//while	   p=p->rchild;	}//while	printf("\n");	return OK;}//InOrderT_ThrBiThrTree InOrderSearch_Thr(BiThrTree T,Elemtype ch){//T指向头结点，头结点的左链lchild指向根结点，非递归算法,查找指定字符ch，找到返回，未找到返回NULL	BiThrTree p; 	p=T->lchild;	while(p!=T) //空树或遍历结束时，T＝＝p	 {		while(p->LTag==Link) p=p->lchild;		if(p->data==ch) return p; //找到，返回该结点指针		while(p->RTag==Thread&&p->rchild!=T)          {	          p=p->rchild;              if(p->data==ch) return p; //找到，返回该结点指针          }//while	   p=p->rchild;	}//while    return NULL;}//InOrderT_ThrStatus CreateBitree(BiThrTree &T){//按先序次序输入二叉树	char ch;	scanf("%c",&ch);	if(ch==' ') T=NULL;	else{			if(!(T=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(1);			T->data=ch;T->LTag=Link;T->RTag=Link;			CreateBitree(T->lchild);			CreateBitree(T->rchild);		}//else	return OK;}//CreateBitreeStatus printelemt(Elemtype e){	printf("%c",e);	return OK;}Status preordertraverse(BiThrTree t,Status (*visit)(Elemtype e)){	if(t)	{		if(visit(t->data))			if(preordertraverse(t->lchild,visit))					if(preordertraverse(t->rchild,visit))  return OK;		return ERROR;	}	else 		return OK;}Status inordertraverse(BiThrTree t,Status (*visit)(Elemtype e)){	if(t)	{	    if(inordertraverse(t->lchild,visit))		    if(visit(t->data))				if(inordertraverse(t->rchild,visit))  return OK;		return ERROR;	}	else 		return OK;}Status postordertraverse(BiThrTree t,Status (*visit)(Elemtype e)){	if(t)	{	    if(postordertraverse(t->lchild,visit))			if(postordertraverse(t->rchild,visit))  						if(visit(t->data)) return OK;		return ERROR;	}	else 		return OK;}BiThrTree InNext(BiThrTree p) /*在中序线索二叉树中查找p的中序后继结点，并用next指针返回结果*/{ 	BiThrTree Next;	BiThrTree q;	if (p->RTag==1)  		 Next = p->rchild; 	else	{ 		if(p->rchild!=NULL)		{			for(q=p->rchild; q->LTag==0 ;q=q->lchild);			Next=q; 		}		else			Next = NULL;	} 	return(Next);}BiThrTree InPre(BiThrTree p)/* 在中序线索二叉树中查找p的中序前驱, 并用pre指针返回结果 */{  	BiThrTree q;	if(p->LTag==1)		pre = p->lchild; 	else 	{ 		for(q = p->lchild;q->RTag==0;q=q->rchild);		pre=q;	} return(pre);}int main(){	char ch;	BiThrTree T,Thrt,p,q;	CreateBitree(T);//创建	preordertraverse(T,printelemt);	printf("\n");	inordertraverse(T,printelemt);	printf("\n");	postordertraverse(T,printelemt);	printf("\n");	InOrderThreading(Thrt,T);//线索化	printf("中序遍历该线索二叉树得到的序列为：\n"); 	InOrderTraverse_Thr(Thrt);//遍历访问    getchar();    printf("请输入树中的一个字符");    scanf("%c",&ch);	p=InOrderSearch_Thr(T,ch);	q=InNext(p);	printf("后继结点：%c\n",q->data);	q=InPre(p);	printf("先趋结点：%c\n",q->data);	return OK;}