线索二叉树

普通二叉链表中有 n+1 个空指针域，线索二叉树利用这些空指针存放遍历序列中的前驱和后继信息。

• 前驱：遍历序列中某结点的前一个结点
• 后继：遍历序列中某结点的后一个结点

线索化规则

• 若左子树为空（$lchild == NULL$），令 lchild 指向遍历序列中的前驱
• 若右子树为空（$rchild == NULL$），令 rchild 指向遍历序列中的后继

typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;   // 0:指向孩子；1:指向前驱/后继
} ThreadNode, *ThreadTree;

ThreadTree pre = NULL;   // 全局变量，记录前驱

void InThread(ThreadTree T) {
    if (T != NULL) {
        InThread(T->lchild);            // 线索化左子树
        if (T->lchild == NULL) { T->ltag = 1; T->lchild = pre; }
        if (pre != NULL && pre->rchild == NULL) {
            pre->rtag = 1; pre->rchild = T;
        }
        pre = T;
        InThread(T->rchild);            // 线索化右子树
    }
}
void CreateInThread(ThreadTree T) {
    pre = NULL;
    if (T != NULL) { InThread(T); pre->rchild = NULL; pre->rtag = 1; }
}

         A
       /   \
      B     C
     / \     \
    D   E     F
中序序列：D B E A C F
线索化后：
D: lchild→NULL(无前驱), rchild→B(后继)
B: lchild→D(前驱), rchild→E(后继)
E: lchild→B(前驱), rchild→A(后继)
A: lchild→E(前驱), rchild→C(后继)
C: lchild→A(前驱), rchild→F(后继)
F: lchild→C(前驱), rchild→NULL(无后继)

// 中序遍历第一个结点：沿左孩子到底
ThreadNode *FirstNode(ThreadNode *p){
    while (p->ltag == 0) p = p->lchild;
    return p;
}
// 找后继：rtag=1 直接返回；否则右子树最左下
ThreadNode *NextNode(ThreadNode *p){
    if (p->rtag == 1) return p->rchild;
    else return FirstNode(p->rchild);
}
// 中序遍历（无需栈）
void InOrderThread(ThreadTree T){
    for (ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p)) visit(p);
}
// 找前驱：ltag=1 直接返回；否则左子树最右下
ThreadNode *PreNode(ThreadNode *p){
    if (p->ltag == 1) return p->lchild;
    else return LastNode(p->lchild);
}

void PreThread(ThreadTree T) {
    if (T != NULL) {
        if (T->lchild == NULL) { T->ltag = 1; T->lchild = pre; }
        if (pre != NULL && pre->rchild == NULL) { pre->rtag = 1; pre->rchild = T; }
        pre = T;
        if (T->ltag == 0) PreThread(T->lchild);   // 需判断 ltag 防循环
        PreThread(T->rchild);
    }
}