#include"conio.h"
#include"stdio.h"
#define NULL 0
#define OVERFLOW 0
#define ERROR 0
typedef struct bitnode{
char data;
struct bitnode *lchild,*rchild;
int ltag,rtag;}bitnode,bitree;
bitree *createbitree()/*建立链表二叉树*/
{ bitree * T;
char x;
scanf("%c",&x);
if(x=='#') T=NULL;
else{
if(!(T=( bitnode *)malloc(sizeof( bitnode)))) exit(OVERFLOW);
T->data=x;
T->ltag=0,T->rtag=0; /*生成根结点*/
T->lchild=createbitree();/*构造左子数*/
T->rchild=createbitree();/*构造右子数*/
}
return(T); }
thread(bitree *r,bitree *pre)
{if(r!=NULL)
{thread(r->lchild,pre);
if(r->lchild==NULL)
{r->lchild=pre;
r->ltag=1;}
if (pre->rchild==NULL)
{pre->rchild=r;
pre->rtag=1;
}
pre=r;
thread(r->rchild,pre);
}}
bitree *crdathread(bitree *b)
{bitree *pre,*root,*p;
root=(bitree*)malloc(sizeof(bitree));
root->data='t';
root->ltag=1;root->rtag=0;
if(b==NULL)
{root->lchild=root;
root->rchild=root;
}
else
{p=root->lchild=b;
root->ltag=0;
pre=root;
thread(p,pre);
pre->rchild=root;
pre->rtag=1;
root->rchild=pre;
root->rtag=1;}
return root;}
InOrderTraverse_Thr(bitree *T)
{ /* 中序遍历二叉线索树T(头结点)的非递归算法。算法6.5 */
bitree *p;
p=T->lchild; /* p指向根结点 */
while(p!=T)
{ /* 空树或遍历结束时,p==T */
while(p->ltag==0)
p=p->lchild;
if(!(printf("%c ",p->data))) /* 访问其左子树为空的结点 */
return ERROR;
while(p->rtag==1&&p->rchild!=T)
{
p=p->rchild;
printf("%c ",p->data); /* 访问后继结点 */
}
p=p->rchild;
}
}
main()
{ bitree *r,*T;
clrscr();
printf("Create bitree\n");
r=createbitree();
T=crdathread(r); /*建立链表二叉树*/
InOrderTraverse_Thr(T);}
