#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */
typedef
int
Status;
typedef
char
TElemType;
typedef
enum
{Link,Thread} PointerTag;
typedef
struct
BiThrNode
{
TElemType data;
struct
BiThrNode *lchild, *rchild;
PointerTag LTag;
PointerTag RTag;
} BiThrNode, *BiThrTree;
TElemType Nil=
'#'
;
Status visit(TElemType e)
{
printf
(
"%c "
,e);
return
OK;
}
Status CreateBiThrTree(BiThrTree *T)
{
TElemType h;
scanf
(
"%c"
,&h);
if
(h==Nil)
*T=NULL;
else
{
*T=(BiThrTree)
malloc
(
sizeof
(BiThrNode));
if
(!*T)
exit
(OVERFLOW);
(*T)->data=h;
CreateBiThrTree(&(*T)->lchild);
if
((*T)->lchild)
(*T)->LTag=Link;
CreateBiThrTree(&(*T)->rchild);
if
((*T)->rchild)
(*T)->RTag=Link;
}
return
OK;
}
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;
InThreading(p->rchild);
}
}
Status InOrderThreading(BiThrTree *Thrt,BiThrTree T)
{
*Thrt=(BiThrTree)
malloc
(
sizeof
(BiThrNode));
if
(!*Thrt)
exit
(OVERFLOW);
(*Thrt)->LTag=Link;
(*Thrt)->RTag=Thread;
(*Thrt)->rchild=(*Thrt);
if
(!T)
(*Thrt)->lchild=*Thrt;
else
{
(*Thrt)->lchild=T;
pre=(*Thrt);
InThreading(T);
pre->rchild=*Thrt;
pre->RTag=Thread;
(*Thrt)->rchild=pre;
}
return
OK;
}
Status InOrderTraverse_Thr(BiThrTree T)
{
BiThrTree p;
p=T->lchild;
while
(p!=T)
{
while
(p->LTag==Link)
p=p->lchild;
if
(!visit(p->data))
return
ERROR;
while
(p->RTag==Thread&&p->rchild!=T)
{
p=p->rchild;
visit(p->data);
}
p=p->rchild;
}
return
OK;
}
int
main()
{
BiThrTree H,T;
printf
(
"请按前序输入二叉树(如:'ABDH##I##EJ###CF##G##')\n"
);
CreateBiThrTree(&T);
InOrderThreading(&H,T);
printf
(
"中序遍历(输出)二叉线索树:\n"
);
InOrderTraverse_Thr(H);
printf
(
"\n"
);
return
0;
}