#include <stdio.h>//测试值：abc@@de@g@@f@@@
#include <stdlib.h>
#define Link 0
#define Thread 1
typedef char TElemType;
typedef struct BiThrNode
{
    TElemType data;
    struct BiThrNode *lchild,*rchild;
    int LTag,RTag;
}BiThrNode,*BiThrTree;
////////
BiThrNode *pre;//全局变量
////////
BiThrTree CreatBiThrTree()//先序创建二叉树
{
    TElemType ch;
    BiThrTree T;
    scanf("%c",&ch);
    if(ch==' ')
        T=NULL;
    else
    {
        T=(BiThrTree)malloc(sizeof(BiThrNode));
        if(!T)
            exit(0);
        T->data=ch;
        ////
        T->LTag=Link;
        T->RTag=Link;
        /////////////indispensable**
        T->lchild=CreatBiThrTree();
        T->rchild=CreatBiThrTree();
    }
    return T;
}
void Visit(char data)
{
    printf("%c",data);
}
/////////////////////////////////////////////////////

void PreThreading(BiThrNode *p)//先遍历二叉树
{
    if (p)
    {
        if (!p->lchild)
        {
            p->LTag=Thread;
            p->lchild=pre;
        }
        if (!p->rchild)
            p->RTag = Thread;
        if (pre&&pre->RTag==Thread)
            pre->rchild = p;
        pre=p;
        if (p->LTag==Link)
            PreThreading(p->lchild);
        if (p->RTag==Link)
            PreThreading(p->rchild);
    }
}
BiThrNode* PreOrderThreading(BiThrNode *T)//先序线索化二叉树
{
    BiThrNode *Thrt;
    Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
    if(!Thrt)
        exit(0);
    Thrt->LTag=Link;
    Thrt->RTag=Thread;
    Thrt->rchild=Thrt;
    if(!T)
        Thrt->lchild=Thrt;
    else
    {
        Thrt->lchild=T;
        pre=Thrt;
        PreThreading(T);//先序遍历进行先序线索化
        pre->rchild=Thrt;//最后一个结点线索化
        pre->RTag=Thread;
        Thrt->rchild=pre;
    }
    return(Thrt);
}

void PreorderTraverse_Thr(BiThrNode *T)//**先序**遍历线索二叉树
{
        //遍历先序线索二叉树
    BiThrTree p=T->lchild;//
    Visit(p->data);
    while (p->rchild!=T)//根左右
    {
       if (p->LTag==Link)
            p=p->lchild;
       else
            p=p->rchild;
        Visit(p->data);
    }
}



//////////////////////////////////////////////////////////
void InThreading(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;//保持pre指向p的前驱
        InThreading(p->rchild);//右子树线索化
    }
}
BiThrNode* InOrderThreading(BiThrNode *T)//中序线索化二叉树
{
    BiThrNode *Thrt;
    Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
    if(!Thrt)
        exit(0);
    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;
    }
    return(Thrt);
}
void InorderTraverse_Thr(BiThrNode *T)//(forward)中序遍历线索二叉树
{
    BiThrNode *p;
    p=T->lchild;
    while(p!=T)//空树或遍历结束时,p=T
    {
        while(p->LTag==Link)
            p=p->lchild;
        Visit(p->data);//访问左子树为空的结点
        while(p->RTag==Thread&&p->rchild!=T)//访问后继结点p->rchild!=T
        {
            p=p->rchild;
            Visit(p->data);
        }
        p=p->rchild;
    }
}
void BackInorderTraverse_Thr(BiThrNode *T)//(back)中序遍历线索二叉树
{
    BiThrNode *p;
    p=T->rchild;
    while(p!=T)
    {
        while(p->LTag==Thread&&p->lchild!=T)
        {
            Visit(p->data);//访问中序遍历的最后一个结点
            p=p->lchild;//直接访问其前驱
        }
        Visit(p->data);//访问根节点
        p=p->lchild;//转向左子树
        while(p->RTag==Link)
            p=p->rchild;//找到左子树在中序遍历时的最后一个结点，进入下一次循环
    }
}

//////////////////////////////////////////////////////
void AfterThreading(BiThrNode *p)//后序遍历二叉树
{
    if (p)
    {
        AfterThreading(p->lchild);
        AfterThreading(p->rchild);
        if (!p->lchild)
        {
            p->LTag=Thread;
            p->lchild=pre;
        }
        if (!p->rchild)
            p->RTag=Thread;
        if (pre&&pre->RTag==Thread)
            pre->rchild=p;
        pre=p;
    }
}
BiThrNode* AfterOrderThreading(BiThrNode *T)//后序线索化二叉树
{
    BiThrNode *Thrt;
    Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
    if(!Thrt)
        exit(0);
    Thrt->LTag=Link;
    Thrt->RTag=Thread;
    Thrt->rchild=Thrt;
    if(!T)
        Thrt->lchild=Thrt;
    else
    {
        Thrt->lchild=T;
        pre=Thrt;
        AfterThreading(T);//后序遍历进行先序线索化
    //    pre->rchild=Thrt;//
    //    pre->RTag=Thread;
    //    Thrt->rchild=pre;
    }
    return(Thrt);
    printf("*********!\n");
}

void AfterorderTraverse_Thr(BiThrNode *T)//**后序**遍历线索二叉树
{
        //遍历后序线索二叉树
    BiThrTree p=T->lchild;//
    Visit(p->data);
    while (p->rchild!=T)//左右根
    {
        if (p->LTag==Link)
            p=p->lchild;
        if(p->RTag==Thread)//直接后继结点
        {
            p=p->lchild;
            Visit(p->data);
        }
        if(p->LTag==Thread&&p->RTag==Link)//左儿子空，右儿子不空，访问右儿子
        {
            p=p->rchild;
            Visit(p->data);
        }
        if(p->LTag==Thread&&p->RTag==Thread)//左儿子空，右儿子空，访问根结点
            Visit(p->data);
    }
}
void main()
{
    BiThrNode *t,*thr;
    printf("请按先序遍历序列输入二叉树中各个结点的值(字符)，若为空树时输入空格键:\n");
    printf("<说明：例如参考数据为:abc@@de@g@@f@@@，则用空格键表示@,输完后再输入一个回车键.>\n");
    t=CreatBiThrTree();
    printf("中序线索化二叉树...\n");
    thr=InOrderThreading(t);
    printf("线索化工作已经完成!\n");
    printf("中序(前向)遍历中序线索二叉树:\n");
    InorderTraverse_Thr(thr);
    printf("\n");
    printf("中序(逆向)遍历中序线索二叉树:\n");
    BackInorderTraverse_Thr(thr);
    printf("\n");
    printf("先序线索化二叉树...\n");
    thr=PreOrderThreading(t);
    printf("先序遍历先序线索二叉树:\n");
    PreorderTraverse_Thr(thr);
    printf("\n");
    printf("后序线索化二叉树...\n");
    thr=AfterOrderThreading(t);
    printf("后序遍历后序线索二叉树:\n");
    AfterorderTraverse_Thr(thr);
    printf("\n");
}