什么是线索？

在 二叉树存储 二叉链表中提到，n个结点的二叉链表中，有 n + 1 个空指针，那这么多的空指针能用来干嘛呢？
大佬们想到用其按照 前/中/后序 将二叉树的结点排列成线性结构（将这些空指针改造为前继或继指针，称为线索）。那线索二叉树必然属于存储结构（二叉链表存储）。
具体怎么实现的看本章内容咯。

怎么将二叉树的结点排列成一个线性结构呢？那就是按照 先 / 中 / 后序遍历 的结点访问顺序咯（除第一个和最后一个外，每个结点都有唯一前驱和唯一后继）。线索二叉树的目的正是方便结点直接获得 其在遍历中的前驱和后继。那么理所应当的有 前/中/后序 线索二叉树o(*￣▽￣*)ブ。

概念

中序线索二叉树

若结点的左指针为空，左指针指向 中序遍历下 该结点的前驱（为空则仍为NULL）；

若结点的右指针为空，右指针指向 中序遍历下 该节点的后继（为空则仍为NULL）。

这样处理的好处在于，对于下图结点D，左指针指向B，右指针指向A，对应中序遍历下的 BDA 序列。

先序线索二叉树

后序线索二叉树

存储类型表示

如果直接像上面图片中那样 结点数据仍由 lchild data rchild组成可行嘛？

不行的！不然怎么区分左指针指的是 左孩子还是 遍历前驱，右指针指的是 右孩子 还是 遍历后继。

因此为了区分，还需要加上 ltag 和 rtag。ltag = 0 – 左孩子；ltag = 1 – 遍历前驱；rtag = 0 – 右孩子；rtag = 1 – 遍历后继。

typedef char ElemType;

typedef struct ThreadNode
{
    /* data */
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
    // 构造函数 （方便建树）
    ThreadNode(ElemType x): data(x), lchild(nullptr), rchild(nullptr), ltag(0), rtag(0){}
};

操作 – 线索化、遍历

在写具体的操作算法前，要分析该操作可行性。

可以看到 先序线索二叉树和中序线索二叉树 均能 从根节点出发，沿着指针获得相应的遍历结果。

但是后序线索二叉树不行（如图找 B结点的后继无法找到），因此用 二叉链表作为存储结构 的 后序线索二叉树 无法实现遍历【只通过指针】操作。（课本：采用带标志域的三叉链表作为存储结构来解决此问题）- 阿Q表示：到一边玩泥巴去，咱不弄了。

中序线索二叉树

线索化

何为线索化？ 将二叉树的空指针改成指向前驱或后继的线索，因此需要中序遍历一遍二叉树，并在遍历途中进行线索化操作即可。

阿Q觉得蛮绕的，直接写代码有点复杂，因此先思考写出伪代码（思绪理清）。

阿Q注：可以先看看 阿Q对递归的思考

// 伪代码
// Pre指向前一个访问的结点，P指向当前访问结点
// 整体思想不难: P和Pre都进行了中序遍历，只不过 P比Pre快了一步，即P永远是Pre的 中序遍历后继

线索化:
    若P（指向当前访问结点）不为空;
      线索化左孩子;
      
      若P的左子树为空:
        // 说明当前访问结点的 中序遍历前驱 没有更改，因此要进行线索化
        访问当前结点;
        将上一个访问的结点的地址（Pre） 赋值给 当前结点的左指针;// 当前结点 中序遍历前驱是 上一个访问的结点
      
      若已经访问了结点（Pre不为空） && 上一个访问的结点的右子树为空:
        // 说明上一个访问结点的 中序遍历后继 没有更改，因此要进行线索化
        访问上一个访问结点;
        将当前访问结点的地址（P）赋值给 上一个结点的右指针; // 上一个访问结点的 中序遍历后继是 当前访问结点
      
      将P（指向当前访问结点） 赋给 Pre（指向上一个访问结点）; 
      线索化右孩子；

/*
需要注意的是上述线索化过程少了最后一个访问结点的处理(如A,B,C,D,E,F - Pre到了F递归全部就结束了，但此时未对其后继进行处理)，因此不是最终线索化的结果
*/
建立线索化:
  Pre 设置为NULL;
  若树不为空树:
    调用线索化函数;
    // 处理最后一个访问结点的后继
    访问最后一个访问结点;
    最后一个访问结点（Pre所指的结点）的右孩子设置为NULL;

// 具体算法实现
// 中序遍历 线索化 -> 中序线索二叉树
void InThread(ThreadNode *&P, ThreadNode *&Pre)
{
    if(!P)
    {
        // 线索化 左孩子
        InThread(P->lchild,Pre);
        
        // P的左子树为空
        // 说明当前访问结点的 中序遍历前驱 没有更改，因此要进行线索化
        if(!P->lchild)
        {
            // 访问当前结点，此处的访问为将 ltag设为1
            P->ltag = 1;
            P->lchild = Pre;
        }

        //若已经访问了结点（Pre不为空） && 上一个访问的结点的右子树为空:
        if(Pre && !Pre->rchild)
        {
            // 访问上一个结点，此处的访问为将 rtag设为1
            Pre->rtag = 1;
            Pre->rchild = P;
        }

        Pre = P;
        // 线索化 右孩子
        InThread(P->rchild,Pre);
    }
}

// 建立中序线索二叉树
void CreateInThread(ThreadTree &T)
{
    ThreadNode *Pre = nullptr;
    if(!T)
    {
        InThread(T,Pre);
        // 处理最后一个访问结点的后继
        // 访问最后一个访问结点，此处的访问为将 rtag设置为1
        Pre->rtag = 1;
        Pre->rchild = nullptr;
    }
}

这种建立的中序线索二叉树仍然有空结点，若要求全部利用起来，则需要建立带头结点的中序线索二叉树。（第一个元素的前驱设为 头结点，最后一个元素的后继设为头结点即可）

遍历

阿Q以下写的均不带头结点！

如何遍历中序线索二叉树从而得到 中序遍历结果呢？只需要解决两个问题即可：

①如何以T为根 找到中序遍历的 第一个结点？

T为根的左子树最左下方的结点即为中序遍历的第一个结点。

②如何找到中序遍历的 当前结点的下一个结点？

若 rtag = 1，直接获取下一个结点；

若 rtag = 0，则需要以当前结点的右孩子为根（T），按①找即可

// 解决①问题
// 以T为根 找中序遍历的 第一个结点
ThreadNode* FirstNode(ThreadNode *T)
{
    // 左子树最左下方的结点即为中序遍历的第一个结点
    while(!T->ltag) T = T->lchild;
    return T;
}

// 解决②问题
// 找到中序遍历的 当前结点的下一个结点
ThreadNode* NextNode(ThreadNode *T)
{
    // 若 rtag = 1，直接获取下一个结点；
    if(T->rtag) return T->rchild;

    // 若 rtag = 0，则需要以当前结点的右孩子为根（T），找第一个结点
    else  return FirstNode(T->rchild);
}

// 中序线索二叉树的中序遍历算法
void InOrder(ThreadTree T)
{
    ThreadTree ptr;
    for(ptr = FirstNode(T); ptr != nullptr; ptr = NextNode(ptr))
    {
        visit(ptr);
    }
}

// 测试代码
int main(){
    ThreadTree Root = new ThreadNode('A');
    Root->lchild = new ThreadNode('B');
    Root->rchild = new ThreadNode('F');
    Root->lchild->lchild = new ThreadNode('C');
    Root->lchild->rchild = new ThreadNode('D');
    CreateInThread(Root);
    InOrder(Root);
    return 0;
}
/*
输出结果：
C  B  D  A  F  
*/

先序线索二叉树

有之前的分析，先序线索二叉树的建立线索化 和 先序遍历过程很快就能写好。

线索化

void PreThread(ThreadNode *&P, ThreadNode *&Pre)
{
    if(P)
    {
        if(!P->lchild)
        {
            P->ltag = 1;
            P->lchild = Pre;
        }

        if(Pre && !Pre->rchild)
        {
            Pre->rtag = 1;
            Pre->rchild = P;
        }

        Pre = P;

        // 线索化 左孩子
        // 仅在左孩子是真实子结点时递归
        if(!P->ltag) PreThread(P->lchild,Pre);

        // 线索化 右孩子
        // 仅在右孩子是真实子结点时递归
        if(!P->rtag) PreThread(P->rchild,Pre);
    }
}

阿Q提醒：在线索化左、右孩子时 需要判断是否为真实结点（先序如果没有加 if(!P->ltag) ，则进入死循环）。（阿Q检查这个问题检查了不少时间，最终还是在DS小姐的帮助下发现的）

遍历

// 先序线索二叉树的先序遍历
ThreadNode* NextNode_Pre(ThreadNode *T)
{
    if(!T->ltag) return T->lchild;
    else return T->rchild;
}

void visit(ThreadNode *ptr)
{
    std::cout << ptr->data << "  ";
}

void PreOrder(ThreadTree T)
{
    ThreadTree ptr;
    for(ptr = T; ptr != nullptr; ptr = NextNode_Pre(ptr))
    {
        visit(ptr);
    }
}

// 测试代码
int main(){
    ThreadTree Root = new ThreadNode('A');
    Root->lchild = new ThreadNode('B');
    Root->rchild = new ThreadNode('F');
    Root->lchild->lchild = new ThreadNode('C');
    Root->lchild->rchild = new ThreadNode('D');
    CreatePreThread(Root);
    PreOrder(Root);
    return 0;
}
/*
输出结果：
A  B  C  D  F  
*/