#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef char TElemType;
typedef enum PointerTag{Link,Thread};
typedef struct BiThrNode{
    TElemType data;
    struct BiThrNode *lchild,*rchild;
    PointerTag LTag,RTag;
}BiThrNode,*BiThrTree;
BiThrTree pre;

Status CreateBiThrTree(BiThrTree &T)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#') T=NULL;
    else
    {
        if(!(T=(BiThrNode*)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
        T->data=ch;
        T->LTag=Link;
        T->RTag=Link;
        CreateBiThrTree(T->lchild);
        CreateBiThrTree(T->rchild);
    }
    return OK;
}


Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e))
{   
    BiThrTree p;
    p=T->lchild;
    while(p!=T)
    {
        while(p->LTag==Link) p=p->lchild;
        if(!Visit(p->data)) return ERROR;
        while(p->RTag==Thread&&p->rchild!=T)
        {
            p=p->rchild; Visit(p->data);
        }
        p=p->rchild;
    }
    return OK;
}
void InThreading(BiThrTree 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);
    }
}


Status InOrderThreading(BiThrTree &Thrt,BiThrTree T)
{
    if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrTree)))) exit(OVERFLOW);
    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 OK;
}

Status PrintElement(TElemType e) {
    printf("%c", e);
    return OK;
}
















void PreThreading(BiThrTree p) //前序线索化二叉树  
{  
    if(p)  
    {
        if(!p->lchild)  { p->LTag = Thread; p->lchild = pre;   }  
        if(!pre->rchild)  {pre->RTag = Thread; pre->rchild = p;  }
        pre = p;
        if(p->LTag==Link)  PreThreading(p->lchild);
        if(p->RTag==Link)  PreThreading(p->rchild);  
    }  
}  

Status PreOrderThreading(BiThrTree &Thrt,BiThrTree T)
{
    if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrTree)))) exit(OVERFLOW);
    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 OK;
}

Status PreOrderTraverse_Thr(BiThrTree L,Status(*Visit)(TElemType e)) //前序遍历线索化二叉树  
{  
    BiThrTree p;
    p = L->lchild;  
    while(p != L)  
    {  
        Visit(p->data);  
        if(p->LTag == Link)  
            p = p->lchild;  
        else  
            p = p->rchild;  
    }  
    return OK;  
}  
   

void main()
{
    BiThrTree T,L,Thrt;
    //TElemType b,d,e;
    //char a;
    printf("创建二叉树，按先序次序输入二叉树中结点的值：\n");
    CreateBiThrTree(T);
    if(InOrderThreading(Thrt,T)==OK) printf("成功建立中序线索化链表!\n");
    printf("中序遍历线索二叉树，结果是:\n");
    InOrderTraverse_Thr(Thrt,PrintElement);
    printf("\n");
    if(PreOrderThreading(Thrt,T)==OK) printf("成功建立先序线索化链表!\n");
    printf("先序遍历线索二叉树，结果是:\n");
    PreOrderTraverse_Thr(Thrt,PrintElement);
    printf("\n");
//    if(PostOrderThreading(Thrt,T)==OK) printf("成功建立后序线索化链表!\n");
    printf("后序遍历线索二叉树，结果是:\n");
//    PostOrderTraverse_Thr(Thrt,PrintElement);
    printf("\n");
      
}