線索二叉樹
一、線索二叉樹的原理

通過考察各種二叉鏈表，不管兒叉樹的形態(tài)如何，空鏈域的個(gè)數(shù)總是多過非空鏈域的個(gè)數(shù)。準(zhǔn)確的說，n各結(jié)點(diǎn)的二叉鏈表共有2n個(gè)鏈域，非空鏈域?yàn)閚-1個(gè)，但其中的空鏈域卻有n+1個(gè)。如下圖所示。

image.png

因此，提出了一種方法，利用原來的空鏈域存放指針，指向樹中其他結(jié)點(diǎn)。這種指針稱為線索。
記ptr指向二叉鏈表中的一個(gè)結(jié)點(diǎn)，以下是建立線索的規(guī)則：
（1）如果ptr->lchild為空，則存放指向中序遍歷序列中該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。這個(gè)結(jié)點(diǎn)稱為ptr的中序前驅(qū)；
（2）如果ptr->rchild為空，則存放指向中序遍歷序列中該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。這個(gè)結(jié)點(diǎn)稱為ptr的中序后繼；

顯然，在決定lchild是指向左孩子還是前驅(qū)，rchild是指向右孩子還是后繼，需要一個(gè)區(qū)分標(biāo)志的。因此，我們在每個(gè)結(jié)點(diǎn)再增設(shè)兩個(gè)標(biāo)志域ltag和rtag，注意ltag和rtag只是區(qū)分0或1數(shù)字的布爾型變量，其占用內(nèi)存空間要小于像lchild和rchild的指針變量。結(jié)點(diǎn)結(jié)構(gòu)如下所示。

image.png

其中：

（1）ltag為0時(shí)指向該結(jié)點(diǎn)的左孩子，為1時(shí)指向該結(jié)點(diǎn)的前驅(qū)；

（2）rtag為0時(shí)指向該結(jié)點(diǎn)的右孩子，為1時(shí)指向該結(jié)點(diǎn)的后繼；

（3）因此對(duì)于上圖的二叉鏈表圖可以修改為下圖的養(yǎng)子。

image.png

二、線索二叉樹代碼實(shí)現(xiàn)

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

typedef char ElemType;

//線索存儲(chǔ)標(biāo)志
//Link（0）：表示指向左右孩子的指針
//Thread（1）：表示指向前驅(qū)后繼的線索
typedef enum {Link ,Thread} PointerTag;//枚舉類型

typedef struct BiThrNode{
    char data;
    struct  BiThrNode *lchild,*rchild;
    PointerTag ltag;
    PointerTag rtag;
} BiThrNode,*BiThrTree;
//全局變量，始終指向剛剛訪問過的結(jié)點(diǎn) 
BiThrTree pre; 

//創(chuàng)建一棵二叉樹，約定用戶遵照前序遍歷的方式輸入數(shù)據(jù)
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){//如果該結(jié)點(diǎn)沒有左孩子，設(shè)置ltag為Thread，并把lchild指向剛剛訪問的結(jié)點(diǎn) 
            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