#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

typedef char DataType;
typedef enum{Link,Thread}PointerTag;

typedef struct TreeNode{    
    DataType data;
    struct TreeNode *lchild ,*rchild;
    PointerTag ltag,rtag;

}ThreadNode,*ThrTree;


ThrTree pre;

//创建二叉树
void createT(ThrTree *t){
    char c;
    scanf("%c",&c);
    if(c=='.'){
        *t =NULL;
    }else{  
        *t = (ThreadNode*)malloc(sizeof(ThreadNode));
        (*t)->data = c;

         //初始化左右tag都为Link  0
        (*t)->ltag = Link;  
        (*t)->rtag = Link;
        
        createT(&(*t)->lchild);
        createT(&(*t)->rchild);
    }
}

void visit(DataType d){
    printf("%c",d);
}

/*中序遍历插入线索*/
void inordertraversalThread(ThrTree *t){
    
    if((*t)){
        inordertraversalThread(&(*t)->lchild);  
        if(!(*t)->lchild){
            (*t)->lchild = pre;
            (*t)->ltag = Thread;
        }
        if(! pre->rchild){
            pre->rtag = Thread;
            pre->rchild=*t;
        }
        pre = *t;  //指向前驱
        inordertraversalThread(&(*t)->rchild);
    }
}


/*中序非递归 遍历线索二叉树*/
void InOrderTraverse(ThrTree thr){

    ThrTree t;
    t = thr->lchild;//获取根节点
    //开始遍历  如果thr==t  等于循环了一圈  就结束遍历
    while( thr != t )  {
        //这一步操作是为了 让t走到中序遍历的第一个元素
        while(t->ltag == Link){
            t = t->lchild;
        }
        //外圈打印当前的元素
        visit(t->data);
        //中序遍历获取每个元素  判断是否有线索的节点  如果有指向下一个并打印数据
        //有两种情况会退出循环 
        // 1  就是rchild==thr  也就是到中序所有都遍历完了 
        // 2  t->rtag!=Thread  也就是元素有右节点 没有线索 退出循环，让外圈循环打印数据
        while(t->rtag==Thread && t->rchild!=thr){
            t = t->rchild;
            visit(t->data);
        }       
        //指向下一个元素
        t = t->rchild;
    }
}

void main(){
    
    ThrTree t= NULL;
    ThrTree thr = (ThreadNode*)malloc(sizeof(ThreadNode));  //线索指针
    
    createT(&t);  //前序创建二叉树
    
    //初始化线索指针
    thr->ltag=Link;    
    thr->rtag = Thread;
    thr->rchild = thr;  //左子数先指向自己 
    
    if(!t){     
        thr->lchild = thr;   //如果数创建失败 还是指向自己
    }else{
        thr->lchild = t;    // 指向根节点
        thr->ltag = Link; 
        pre = thr; //初始化指向头指针  也就是单独的线索指针 
        inordertraversalThread(&t); 

        //中序最后一个元素指向线索指针
        pre->rchild = thr;  
        pre->rtag = Thread;  
        thr->rchild = pre;   //线索指针回指中序最后一个节点
    }
        
    InOrderTraverse(thr);
    printf("\n");
}