#include<stdio.h>
#define NULL 0
enum PointerTag{Link,Thread};
struct BiThrNode
{char data;
 struct BiThrNode *lchild,*rchild;
 enum PointerTag LTag,RTag;
};
struct BiThrNode *T;
struct BiThrNode *Thrt;
struct BiThrNode *pre;
struct BiThrNode* CreatBiThrTree(struct BiThrNode *t)
{char c;
 scanf("%c",&c);
 if(c==' ')
  t=NULL;
 else
   {t=(struct BiThrNode *)malloc(sizeof(struct BiThrNode));
    t->data=c;
    t->LTag=Link;
    t->RTag=Link;
    t->lchild=CreatBiThrTree(t->lchild);
    t->rchild=CreatBiThrTree(t->rchild);
   }
 return t;
}
void InThreading(struct BiThrNode *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);
  }
}
void InorderThreading()
{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;
   }
}
void Visit(char c)
{printf("%c",c);
}
void InorderTraverse_Thr()
{struct BiThrNode *p;
 p=Thrt->lchild;
 while(p!=Thrt)
   {while(p->LTag==Link)
      p=p->lchild;
    Visit(p->data);
    while(p->RTag==Thread&&p->rchild!=Thrt)
      {p=p->rchild;
       Visit(p->data);
      }
    p=p->rchild;
   }
}
void main(void)
{T=CreatBiThrTree(T);
 InorderThreading();
 InorderTraverse_Thr();
 getchar();
 getchar();
}