前言

遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列，得到二叉树中结点的先序序列、中序序列、后序序列、这实质上是对一个非线性结构进行线性化的操作，使每个结点在这些线性序列中有且仅有一个直接前驱和直接后继。
但是，当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接找到结点在任一序列中的前驱和后继的信息。
如何保存这种在遍历过程中得到的信息呢？对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。

规则

1. 结点左子树为空，利用左孩子的指针指向前驱结点；
2. 结点右子树为空，利用右孩子的指针指向后继结点；
3. 所有的前驱、后继按照某一个遍历逻辑；

代码实现

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */

typedef int Status;
typedef char TElemType;
typedef TElemType SqBiTree[MAX_TREE_SIZE];
TElemType Nil = '#';

#pragma mark--二叉树构造

int indexs = 1;
typedef char String[24];
String str;
Status StrAssign(String T,char *chars) {
    int i;
    if(strlen(chars) > 100) {
        return ERROR;
    }
    T[0] = strlen(chars);
    for(i = 1; i <= T[0]; i++)
        T[i] =* (chars + i - 1);
    return OK;
}

#pragma mark - Thread BiTree

typedef enum {
    Link,
    Thread
} PointerTag;

typedef struct BiThrNode {
    TElemType data;
    struct BiThrNode *lchild, *rchild;
    PointerTag LTag, RTag;
} BiThrNode, *BiThrTree;

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

Status CreateBiThrTree(BiThrTree *T) {
    TElemType e = str[indexs++];
    if (e == Nil) {
        *T = NULL;
    } else {
        *T = (BiThrTree)malloc(sizeof(BiThrNode));
        if (T == NULL) {
            exit(OVERFLOW);
        }
        
        (*T)->data = e;
        CreateBiThrTree(&(*T)->lchild);
        if ((*T)->lchild) {
            (*T)->LTag = Link;
        }
        CreateBiThrTree(&(*T)->rchild);
        if ((*T)->rchild) {
            (*T)->RTag = Link;
        }
    }
    return OK;
}

BiThrTree pre;
void InThreading(BiThrTree p) {
    if (p) {
        InThreading(p->lchild);
        if (!p->lchild) {
            p->LTag = Thread;
            p->lchild = pre;
        } else {
            p->LTag = Link;
        }
        if (!pre->rchild) {
            pre->RTag = Thread;
            pre->rchild = p;
        } else {
            pre->RTag = Link;
        }
        
        pre = p;
        InThreading(p->rchild);
    }
}

Status InOrderThreading(BiThrTree *Thrt , BiThrTree T) {
    *Thrt = (BiThrTree)malloc(sizeof(BiThrNode));
    if (*Thrt == NULL) {
        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 InOrderTraverse_Thr(BiThrTree T) {
    BiThrTree p;
    p = T->lchild;
    while (p != T) {
        while (p->LTag == Link) {
            p = p->lchild;
        }
        visit(p->data);
        
        while (p->RTag == Thread && p->rchild != T) {
            p = p->rchild;
            visit(p->data);
        }
        p = p->rchild;
    }
    
    return OK;
}