#include "stdio.h"

#include "stdlib.h"

#define OK 1

#define ERROR 0

typedef char TElemType;

typedef char Elemtype;

typedef int Status;

typedef enum PointerTag {Link,Thread}; //link==0:pointer,Thread==1:thread

typedef 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

}//InThreading

Status 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;

}//InOrderThreading

Status 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_Thr

BiThrTree 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_Thr

Status 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;

}//CreateBitree

Status 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;

}