Description

本题中，将会给出一个按照先序遍历得出的字符串，空格代表空的子节点，大写字母代表节点内容。请通过这个字符串建立二叉树，并按照题目描述中算法，中序遍历二叉树并中序线索化二叉树，之后中序遍历输出二叉线索树。

在遍历二叉树的过程中，是按照一定的规则将二叉树中的结点排列成一个线性序列，从而得到二叉树中结点的先序序列或中序序列或后序序列。但是，当以二叉链表作为存储结构时，只能找到结点的左右孩子信息，而不能直接得到结点在任意一个序列中的前驱和后继的信息，而这种信息只有在遍历的动态过程中才能够得到。为了保存这种信息，就需要使用线索链表。其中指向结点的前驱和后继的指针，叫做线索。添加上线索的二叉树称之为线索二叉树。

Input

输入只有一行，包含一个字符串S，用来建立二叉树。保证S为合法的二叉树先序遍历字符串，节点内容只有大写字母，且S的长度不超过100。

Output

共一行，包含一串字符，表示按中序遍历二叉线索树得出的节点内容，每个字母后输出一个空格。请注意行尾输出换行。

Sample Input

ABC  DE G  F

Sample Output

C B E G D F A

HINT

通过线索化二叉树建立二叉线索树，将给普通二叉树添加更快捷的遍历方式。在线索树上进行遍历，只需要先找到序列中的第一个结点，然后依次找结点后继直至其后继为空时而止。而对于中序线索二叉树，由于其固有的性质，在遍历的过程中虽然时间复杂度依旧为O(n)，但常数因子将会比普通的算法减小且不需要栈结构辅助，是一种非常优秀的遍历算法。

 

代码：

/**************************************************************
    Problem: 2608
    User: 201717010009
    Language: C
    Result: Accepted
    Time:0 ms
    Memory:1092 kb
****************************************************************/
#include<stdio.h>
#include<stdlib.h>
typedef struct {
    char ch;
}ElemType; 
typedef enum {Link,Thread} PointerTag;
typedef struct BiTNode{
    ElemType elem;
    struct BiTNode *Lchild;
    struct BiTNode *Rchild;
    PointerTag LTag;
    PointerTag RTag;
}BiTNode,*BiTree;
 
BiTree pre;
void CreatTree(BiTree *T);
 
void InOrderThreading(BiTree *Thrt,BiTree T);
void InThreading(BiTree p);
void InOrderTraverse(BiTree T);
void Z_Traverse(BiTree T);
int main()
{
    BiTree T;
     
    CreatTree(&T);
    BiTree Thrt;
    InOrderThreading(&Thrt,T);//中序线索化 
     
    InOrderTraverse(Thrt);//中序遍历 
     
     
     
}
void CreatTree(BiTree *T)//前序遍历建立二叉树 
{
    char a;
    scanf("%c",&a);
    if(a==' ')
    {
        *T=NULL;
    }
    else
    {
        *T=(BiTree)malloc(sizeof(BiTNode));
        (*T)->elem.ch=a;
        (*T)->LTag=Link;//初始化 
        (*T)->RTag=Link;//初始化 
        CreatTree( &( (*T)->Lchild ) );
        CreatTree( &( (*T)->Rchild ) );
    }
}
void InOrderThreading(BiTree *Thrt,BiTree T)
{
    (*Thrt) = (BiTree)malloc(sizeof(BiTNode));
     
    (*Thrt)->Rchild=*Thrt;//右指针回指
    (*Thrt)->RTag=Link;
     
    if(!T)
    {
        (*Thrt)->Lchild=*Thrt;
        (*Thrt)->LTag=Link;
    } 
    else
    {
        pre=*Thrt;
        (*Thrt)->Lchild=T;
        (*Thrt)->LTag=Link;
        InThreading(T);
        pre->Rchild=*Thrt;
        pre->RTag=Thread;
        (*Thrt)->Rchild=pre;
    }
}
void InThreading(BiTree 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 InOrderTraverse(BiTree T)
{
    BiTree p;
    p=T->Lchild;
    while(p!=T)
    {
        while(p->LTag==Link)
        {
            p=p->Lchild;
        }
        printf("%c ",p->elem.ch);
        while(p->RTag==Thread&&p->Rchild!=T)
        {
            p=p->Rchild;
            printf("%c ",p->elem.ch);
        }
        p=p->Rchild;
    }
     
}
 
void Z_Traverse(BiTree T)//中序遍历二叉树 
{
    if(T)
    {
        Z_Traverse(T->Lchild);
        printf("%c",T->elem.ch);
        Z_Traverse(T->Rchild);
    }
}