#include <stdio.h>
#include <stdlib.h>

// 线索存储标志位
// Link(0): 表示指向左右孩子的指针
// Thread(1): 表示指向前驱后继的线索
typedef char ElemType ;
typedef enum { Link, Thread } PointerTag;
typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    PointerTag ltag, rtag;
}ThreadNode, *ThreadTree;


ThreadTree pre = NULL; 

void CreateInThread(ThreadTree *p);
void Inthread(ThreadTree T);
void InOrderThread(ThreadTree *, ThreadTree p);
void InorderTraverse(ThreadTree T);


int main(){
    
    ThreadTree P,T = NULL;
    CreateInThread(&T);
    InOrderThread(&P, T);
    InorderTraverse(P);
    return 0;
}

//前序建立二叉树, 约定用户遵照前序遍历的方式输入

void CreateInThread(ThreadTree* p){
    char c;
    scanf("%c", &c);
    if (' ' == c) {
        *p = NULL;
    }
    else {
        (*p) = (ThreadTree)malloc(sizeof(ThreadNode));
        (*p)->data = c;
        (*p)->ltag = Link;
        (*p)->rtag = Link;
        CreateInThread(&(*p)->lchild);
        CreateInThread(&(*p)->rchild);
    }
}
// 中序遍历线索化
void Inthread(ThreadTree T) {
    if (T) {
        Inthread(T->lchild);        //递归做孩子线索化
        if (T->lchild == NULL) {    //修改本节点的前驱
            T->ltag = Thread;
            T->lchild = pre;
        }
        if (pre->rchild == NULL) { //修改前一个节点的后继
            pre->rtag = Thread;
            pre->rchild = T;
        }
        pre = T;
        Inthread(T->rchild);        //递归做孩子线索化
    }
    else {
        return;
    }
}
void InOrderThread(ThreadTree* p, ThreadTree T) {
    (*p) = (ThreadTree)malloc(sizeof(ThreadNode)); //*P is head node
    (*p)->ltag = Link;
    (*p)->rtag = Thread;
    (*p)->rchild = (*p);
    if (!T) {
        (*p)->lchild = (*p);
    }
    else {
        (*p)->lchild = T;
        pre = *p;
        Inthread(T); // Inthread函数执行后，pre指向最后一个节点
        pre->rchild = *p;
        pre->rtag = Thread;
        (*p)->rchild = pre;
    }
}
// 中序遍历二叉树, 非递归
//void InorderTraverse(ThreadTree T) {
//  ThreadTree p;
//  p = T->lchild;
//  while (p != T) {
//      while (p->ltag == Link) {
//          p = p->lchild;
//      }
//      printf("%c", p->data);
//      while (p->rtag == Thread && p->rchild != T) {
//          p = p->rchild;
//          printf("%c", p->data);
//      }
//      p = p->rchild;
//  }
//}
//和二叉树的中序遍历没有区别，只不过加了一个判断是不是Link
void InorderTraverse(ThreadTree T) {
    if (T) {
        if (T->ltag == Link) {
            InorderTraverse(T->lchild);
        }
        printf("%c", T->data);
        if (T->rtag == Link) {
            InorderTraverse(T->rchild);
        }
    }
}