1. 概念

引入一种线性化的方法，将二叉树也具有这种前驱找后继的性能

不管是先序还是后序，最重要的一点就是：要访问左右孩子的时候，无法通过指针NULL去判断它是否存在，只能通过ltag、rtag

2.先序遍历对二叉树线索化

遍历二叉树中所有的结点，然后将每对前驱和后继结点进行判断；
如果前驱结点的右孩子为空，将右孩子指针指向后继结点；
如果后继结点的左孩子为空，将左孩子指向前驱结点。

// 先序遍历方法线索化二叉树
// 注意：前驱的指针传地址，防止丢失
void preOrderThread(ThreadBiTree T, ThreadBiTNode*& preNode)
{
    if (T == NULL)
        return;
    // 左孩子为空，建立前驱线索
    if (T->lchild == NULL)
    {
        T->ltag = 1;    // 标记左孩子指针用于线索
        T->lchild = preNode;
        // printf("%d %c %d\n", T->ltag, T->data, T->rtag);
    }
    // 右子树为空且前驱结点不为空，建立后继线索
    if (preNode != NULL && preNode->rchild == NULL)
    {
        preNode->rtag = 1;
        preNode->rchild = T;
        // printf("%d %c %d\n", preNode->ltag, preNode->data, preNode->rtag);
    }
    preNode = T;
    // 注意：
    // 前面修改结点的指针域，不是使用T->lchild == NULL的方式判空
    // 可以使用 T->ltag == 0 方式判断左孩子是否存在
    if(T->ltag == 0)
        preOrderThread(T->lchild, preNode);
    if(T->rtag == 0)
        preOrderThread(T->rchild, preNode);
}
void preOrderCreateThreadTree(ThreadBiTree T)
{
    ThreadBiTNode* preNode = NULL;
    preOrderThread(T, preNode);
}

3. 遍历线索化二叉树（先序）

线索化后，就可以通过当前结点获得它的后继，之后即可将整个序列输出。（先序遍历）

根（前驱）→ 左孩子（左子树跟）（后继）；
如果左子树不存在，它的后继就是右孩子（右子树根）；
如果左右孩子都不存在，那么右孩子一定是线索，通过线索获得后继；
即左孩子不存在，后继一定是右孩子指针域指向的结点

// 遍历先序线索化二叉树
void preOrderThreadTree(ThreadBiTree T)
{
    ThreadBiTNode* postNode = NULL; // 后继结点
    ThreadBiTNode* preNode = T;  // 前驱结点
    // 先序遍历时，第一个前驱结点一定时根结点
    // 先序遍历：根 -> 左孩子 -> 右孩子
    while (preNode != NULL)
    {
        // 如果左孩子存在，一定是preNode的后继
        if (preNode->ltag == 0)
        {
            postNode = preNode->lchild;
        }
        else
        {
            postNode = preNode->rchild;
        }
        printf("%c ", preNode->data);
        preNode = postNode;     // 将后继更新为前驱
    }
}

递归遍历

void preOrderThreadTree2(ThreadBiTree T)
{
    if (T == NULL)
        return;
    printf("%c ", T->data);
    if (T->ltag == 0)
    {
        preOrderThreadTree2(T->lchild);
    }
    else
        preOrderThreadTree2(T->rchild);
}

4. 中序遍历线索化二叉树

关键过程与先序遍历线索化找后继有区别，但本质还是前驱带后继的规律。

左孩子为空，指向它中序遍历序列的前驱；右孩子为空，指向它中序遍历的后继。
生成中序遍历线索树的过程，无非就是使用中序遍历获得前驱与后继，然后再将这些以获得的信息当作线索存储到结点中。
最后，就能使用前驱带后继的方式来获得整个中序遍历序列。

// 中序遍历方法线索化二叉树
// 注意：前驱的指针传地址，防止丢失
void inOrderThread(ThreadBiTree T, ThreadBiTNode*& preNode)
{
    if (T == NULL)
        return;
    inOrderThread(T->lchild, preNode);
    if (T->lchild == NULL)
    {
        T->ltag = 1;
        T->lchild = preNode;
        printf("%d %c %d\n", T->ltag, T->data, T->rtag);
    }
    if (preNode != NULL && preNode->rchild == NULL)
    {
        preNode->rtag = 1;
        preNode->rchild = T;
        printf("%d %c %d\n", preNode->ltag, preNode->data, preNode->rtag);
    }
    preNode = T;
    if (T->rtag == 0)
        inOrderThread(T->rchild, preNode);
}
void inOrderCreateThreadTree(ThreadBiTree T)
{
    ThreadBiTNode* preNode = NULL;
    inOrderThread(T, preNode);
}

4. 遍历线索化二叉树（中序）

在中序遍历中，访问完根之后，下一个访问根的后继节点，一定是在右子树中。
并且，不管是左子树还是右子树中，第一个访问的结点一定是最坐下的结点。
如果前驱结点的右孩子不存在，那么线索化完成之后，右孩子指针一定指向后继，可以通过右孩子指针获得后继。

获取中序线索树中第一个被访问的结点

// 寻找中序线索二叉树中第一个被中序遍历的结点
ThreadBiTNode* getFirstInOrderNode(ThreadBiTree T)
{
    ThreadBiTNode* pNode = T;
    // 注意：访问最左下结点
    // 左孩子存在的依据是 ltag 为 0
    while (pNode->ltag == 0)
    {
        pNode = pNode->lchild;
    }
    return pNode;
}

在中序线索树中寻找一个结点的后继

// 在中序线索二叉树中找到结点pNode的后继结点
// 在右子树的最坐下节点
ThreadBiTNode* getNextInOrderNode(ThreadBiTNode* pNode)
{
    if (pNode->rtag == 0)   // 若存在右子树
    {
        // 后继结点为右子树第一个被访问的结点
        return getFirstInOrderNode(pNode->rchild);
    }
    else    // 若不存在右子树，rchild 指向的即为后继节点
        return pNode->rchild;
}

中序遍历线索二叉树

// 中序线索树找中序后继
void inOrderThreadTree(ThreadBiTree T)
{
    ThreadBiTNode* preNode = NULL;  // 指向前驱结点
    preNode = getFirstInOrderNode(T);
    while (preNode != NULL)
    {
        printf("%c ", preNode->data);
        preNode = getNextInOrderNode(preNode);  // 更新前驱
    }
}