#include<iostream>
using namespace std;
typedef char TElemType;
typedef struct BiThrNode{
TElemType data;
struct BiThrNode *lchild,*rchild;
int LTag,RTag;
}BiThrNode,*BiThrTree;
BiThrNode *pre=new BiThrNode;
void InThreading(BiThrTree p)
{
if(p){
InThreading(p->lchild);
if(!p->lchild){
p->LTag=1;
p->lchild=pre;
}
else p->LTag=0;
if(!pre->rchild)
{
pre->RTag=1;
pre->rchild=p;
}
else pre->RTag=0;
pre=p;
InThreading(p->rchild);
}
}
void InOrderThreading(BiThrTree &Thrt,BiThrTree T){
Thrt=new BiThrNode;
Thrt->LTag=0;
Thrt->RTag=1;
Thrt->rchild=Thrt;
if(!T) Thrt->lchild=Thrt;
else{
Thrt->lchild=T;
pre=Thrt;
InThreading(T);
pre->rchild=Thrt;
pre->RTag=1;
Thrt->rchild=pre;
}
}
void CreateBiTree(BiThrTree &T)
{
char ch;
cin>>ch;
if(ch=='#') T=NULL;
else{
T=new BiThrNode;
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
void InOrderTraverse_Thr(BiThrTree T){
BiThrNode *p;
p=T->lchild;
while(p!=T)
{
while(p->LTag==0) p=p->lchild;
cout<<p->data;
while (p->RTag==1&&p->rchild!=T)
{
p=p->rchild;
cout<<p->data;
}
p=p->rchild;
}
}
void main()
{
pre->RTag=1;
pre->rchild=NULL;
BiThrTree tree,Thrt;
cout<<"请输入建立二叉链表的序列:\n";
CreateBiTree(tree);
InOrderThreading(Thrt,tree);
cout<<"中序遍历线索二叉树的结果为:\n";
InOrderTraverse_Thr(Thrt);
cout<<endl;
}