线索二叉树
一、线索二叉树的原理

通过考察各种二叉链表，不管儿叉树的形态如何，空链域的个数总是多过非空链域的个数。准确的说，n各结点的二叉链表共有2n个链域，非空链域为n-1个，但其中的空链域却有n+1个。如下图所示。

image.png

因此，提出了一种方法，利用原来的空链域存放指针，指向树中其他结点。这种指针称为线索。
记ptr指向二叉链表中的一个结点，以下是建立线索的规则：
（1）如果ptr->lchild为空，则存放指向中序遍历序列中该结点的前驱结点。这个结点称为ptr的中序前驱；
（2）如果ptr->rchild为空，则存放指向中序遍历序列中该结点的后继结点。这个结点称为ptr的中序后继；

显然，在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继，需要一个区分标志的。因此，我们在每个结点再增设两个标志域ltag和rtag，注意ltag和rtag只是区分0或1数字的布尔型变量，其占用内存空间要小于像lchild和rchild的指针变量。结点结构如下所示。

image.png

其中：

（1）ltag为0时指向该结点的左孩子，为1时指向该结点的前驱；

（2）rtag为0时指向该结点的右孩子，为1时指向该结点的后继；

（3）因此对于上图的二叉链表图可以修改为下图的养子。

image.png

二、线索二叉树代码实现

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

typedef char ElemType;

//线索存储标志
//Link（0）：表示指向左右孩子的指针
//Thread（1）：表示指向前驱后继的线索
typedef enum {Link ,Thread} PointerTag;//枚举类型

typedef struct BiThrNode{
    char data;
    struct  BiThrNode *lchild,*rchild;
    PointerTag ltag;
    PointerTag rtag;
} BiThrNode,*BiThrTree;
//全局变量，始终指向刚刚访问过的结点 
BiThrTree pre; 

//创建一棵二叉树，约定用户遵照前序遍历的方式输入数据
CreateBiThrTree(BiThrTree *T){
    char c;
    scanf("%c",&c);
    if(' '==c){
        *T = NULL;
    }else{
        *T=(BiThrNode*)malloc(sizeof(BiThrNode));
        //初始化
        (*T)->data = c;
        (*T)->ltag = Link;
        (*T)->rtag = Link; 
        
        CreateBiThrTree(&(*T)->lchild);
        CreateBiThrTree(&(*T)->rchild);
    }
} 
//中序遍历线索化 
InThreading(BiThrTree T) {
    if (T){
        InThreading(T->lchild);//递归左孩子线索化 
        if(!T->lchild){//如果该结点没有左孩子，设置ltag为Thread，并把lchild指向刚刚访问的结点 
            T->ltag = Thread;
            T->lchild = pre;
        }
        if(!pre->rchild){ 
            pre->rtag = Thread;
            pre->rchild = T;
        } 
        pre = T;
        InThreading(T->rchild);
    }
}
//建立头指针 
InOrderThreading(BiThrTree *p,BiThrTree T){
    *p = (BiThrTree)malloc(sizeof(BiThrNode));
    (*p)->ltag = Link;
    (*p)->rtag = Thread;
    (*p)->rchild = *p; 
    if(!T){
        (*p)->lchild=*p;
    }else{
        (*p)->lchild=T;
        pre=*p;
        InThreading(T);
        //收尾
        pre->rchild = *p;
        pre->rtag = Thread;
        (*p)->rchild = pre;
    }
}
int main(){ 
    BiThrTree P,T =NULL;
    CreateBiThrTree(&T);
    InOrderThreading(&P,T);
    
    return 0;
}

参考博客：https://blog.csdn.net/shenaisi/article/details/81291898