#define null 0
include
include
include
#include
#include
using namespace std;
typedef struct BIThrNODE{
int data ;
int lflag ,rflag;
struct BIThrNODE *lchild ,*rchild;
}BiThrTree,*bitree;
void creatBiThrTree(BiThrTree *&t)
{ int x = 0 ;
scanf("%d",&x);
if(x==0)
{
t= null;
}
else
{
t = (BiThrTree*)malloc(sizeof(BiThrTree));
t->data = x;
t->rflag = 0;
t->lflag = 0;
creatBiThrTree(t->lchild);
creatBiThrTree(t->rchild);
}
}
BiThrTree *pre = null;
void InThreading(BiThrTree * p)
{
stackst;
do{
while(p!=null){st.push(p);p=p->lchild;}
p=st.top();st.pop();
if(pre!=null)
{if(pre->rchild==null){pre->rchild=p;pre->rflag=1;}
if(p->lchild==null){p->lchild=pre;p->lflag=1;}
}
pre=p;p=p->rchild;
}while(!st.empty()||p!=null);
}
void InOrderThreading(BiThrTree *t,BiThrTree *&Thrt)
{
Thrt =(BiThrTree *)malloc(sizeof(BiThrTree));
Thrt->lflag = 1 ;
Thrt->rflag = 0 ;
if(!t)
Thrt->lchild = Thrt ;
else
{
Thrt->lchild = t ;
pre = Thrt ;
InThreading(t);
Thrt ->rchild =pre ;
pre->rchild =Thrt ;
}
}
void InOrderTraverse_Thr(BiThrTree *Thrt)
{
BiThrTree * p =Thrt->lchild;
while(p != Thrt )
{
while(p->lflag == 0)
{
p = p->lchild;
}
if(p->lflag)
printf("%d，",p->data);
while((p->rflag == 1)&&(p->rchild != Thrt))
{
p = p->rchild ;
printf("%d，",p->data);
}
p = p->rchild ;
}
}
main()
{ BiThrTree *t,*Thrt;
printf("请输入要创建的二叉树：");
creatBiThrTree(t);
InOrderThreading(t,Thrt);
printf("遍历二叉树结果为：");
InOrderTraverse_Thr(Thrt);
printf("\n");
}
