線索化
在二叉樹(shù)中，每個(gè)結(jié)點(diǎn)堤魁，有2個(gè)域，記為 lchild與rchild,用來(lái)記錄結(jié)點(diǎn)的左右孩子返十，如果某結(jié)點(diǎn)為葉子結(jié)點(diǎn)妥泉，或者沒(méi)有左或者右孩子，那么將用空域來(lái)表示吧慢；

在二叉樹(shù)的某個(gè)結(jié)點(diǎn)上涛漂，我們無(wú)法直接得知該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)（prev）與后繼結(jié)點(diǎn)（next），只有在遍歷的時(shí)候检诗，才知道匈仗；

為了讓各結(jié)點(diǎn)鏈接起來(lái)（知道前后結(jié)點(diǎn)），同時(shí)避免空域的空間浪費(fèi)逢慌，我們?cè)诿總€(gè)結(jié)點(diǎn)上新增2個(gè)變量悠轩，lTag, rTag, 分別用來(lái)表示 lchild與rchid的指向；這樣稱為線索化攻泼；

實(shí)現(xiàn)代碼：

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

typedef char ElemType;

// 線索存放標(biāo)志位火架，Link(0) : 表示指向左右孩子的指針；
//              Thread(1) : 表示指向前驅(qū)后繼的線索忙菠；
typedef enum {Link, Thread} PointerTag;

typedef struct BiThrNode {
    ElemType data;
    struct BiThrNode *lchild, *rchild;
    PointerTag ltag;
    PointerTag rtag;
} BiThrNode, *BiThrTree;

// 全局變量何鸡，記錄上次訪問(wèn)過(guò)得結(jié)點(diǎn)
BiThrTree pre;

// 創(chuàng)建一顆二叉樹(shù)，按照前序遍歷的方式插入數(shù)據(jù)
void createBiThrTree(BiThrTree *T) {
    char c;
    scanf("%c",&c);
    
    if(' ' == c) {
        *T = NULL;
    } else {
        *T = (BiThrNode *)malloc(sizeof(BiThrNode));
        (*T)->data = c;
        (*T)->ltag = Link;      // 默認(rèn)有左右孩子
        (*T)->rtag = Link;
        createBiThrTree(&(*T)->lchild);
        createBiThrTree(&(*T)->rchild);
    }
}

// 中序遍歷,線索化
void inThreading(BiThrTree T) {
    if(T) {
        inThreading(T->lchild);     // 遞歸左孩子線索化
        
        // 如果該結(jié)點(diǎn)沒(méi)有左孩子牛欢，設(shè)置ltag為Thread骡男，并將lchild指向上一個(gè)訪問(wèn)的結(jié)點(diǎn)
        if(!T->lchild) {
            T->ltag = Thread;       // 線索
            T->lchild = pre;        // 指向前驅(qū)(prev)
        }
        if(!(pre->rchild)) {        // 設(shè)置后繼(next)
            pre->rtag = Thread;
            pre->rchild = T;
        }
        pre = T;                    // 記錄訪問(wèn)過(guò)的結(jié)點(diǎn)
        
        inThreading(T->rchild);     // 遞歸右孩子線索化
    }
}

// 將二叉樹(shù)線索化,建立初始化頭指針，并賦值給pre
void initInThreadingHead(BiThrTree *p, BiThrTree T) {
    *p = (BiThrTree)malloc(sizeof(BiThrNode));     // 建立頭指針傍睹，并初始化
    (*p)->ltag = Link;
    (*p)->rtag = Thread;
    (*p)->lchild = *p;      //初始化隔盛，指向自己
    
    if(!T) {
        (*p)->rchild = *p;  // 樹(shù)不存在犹菱，前驅(qū)后繼都指向自己
    } else {
        (*p)->lchild = T;
        pre = *p;
        
        inThreading(T);     // 中序線索化
        
        // 中序線索化完成后，收尾工作
        pre->rtag = Thread;
        pre->rchild = *p;
        (*p)->rchild = pre;
    }
}

void visit(char c) {
    printf("%c", c);
}

// 中序遍歷二叉樹(shù)吮炕，非遞歸腊脱，傳入頭指針
void inOrderIterator(BiThrTree T) {
    BiThrTree p;
    p = T->lchild;
    
    while(p != T) {   // 結(jié)點(diǎn)與頭指針判斷 （空樹(shù)或者遍歷結(jié)束）
        while(p->ltag == Link) {    // 左
            p = p->lchild;
        }
        visit(p->data);
        
        while(p->rtag == Thread && p->rchild != T) {           // 右，后繼
            p = p->rchild;
            visit(p->data);
        }
        
        p = p->rchild;
    }
}


//ABC__D__E_F__
int main(int argc, const char * argv[]) {
    BiThrTree P, T = NULL;
    
    createBiThrTree(&T);
    
    initInThreadingHead(&P, T);
    
    inOrderIterator(P);
    
    return 0;
}

線索化后的最終圖
紅色：后繼（next）龙亲；
藍(lán)色：前驅(qū)（prev）;
新加入了頭結(jié)點(diǎn)陕凹，用來(lái)形成環(huán)

中序線索化