#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;
}