二叉树的线索化

线索化
在二叉树中，每个结点，有2个域，记为 lchild与rchild,用来记录结点的左右孩子，如果某结点为叶子结点，或者没有左或者右孩子，那么将用空域来表示；

在二叉树的某个结点上，我们无法直接得知该结点的前驱结点（prev）与后继结点（next），只有在遍历的时候，才知道；

为了让各结点链接起来（知道前后结点），同时避免空域的空间浪费，我们在每个结点上新增2个变量，lTag, rTag, 分别用来表示 lchild与rchid的指向；这样称为线索化；

实现代码：

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

typedef char ElemType;

// 线索存放标志位，Link(0) : 表示指向左右孩子的指针；
//              Thread(1) : 表示指向前驱后继的线索；
typedef enum {Link, Thread} PointerTag;

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

// 全局变量，记录上次访问过得结点
BiThrTree pre;

// 创建一颗二叉树，按照前序遍历的方式插入数据
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;      // 默认有左右孩子
        (*T)->rtag = Link;
        createBiThrTree(&(*T)->lchild);
        createBiThrTree(&(*T)->rchild);
    }
}

// 中序遍历,线索化
void inThreading(BiThrTree T) {
    if(T) {
        inThreading(T->lchild);     // 递归左孩子线索化
        
        // 如果该结点没有左孩子，设置ltag为Thread，并将lchild指向上一个访问的结点
        if(!T->lchild) {
            T->ltag = Thread;       // 线索
            T->lchild = pre;        // 指向前驱(prev)
        }
        if(!(pre->rchild)) {        // 设置后继(next)
            pre->rtag = Thread;
            pre->rchild = T;
        }
        pre = T;                    // 记录访问过的结点
        
        inThreading(T->rchild);     // 递归右孩子线索化
    }
}

// 将二叉树线索化,建立初始化头指针，并赋值给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;  // 树不存在，前驱后继都指向自己
    } else {
        (*p)->lchild = T;
        pre = *p;
        
        inThreading(T);     // 中序线索化
        
        // 中序线索化完成后，收尾工作
        pre->rtag = Thread;
        pre->rchild = *p;
        (*p)->rchild = pre;
    }
}

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

// 中序遍历二叉树，非递归，传入头指针
void inOrderIterator(BiThrTree T) {
    BiThrTree p;
    p = T->lchild;
    
    while(p != T) {   // 结点与头指针判断 （空树或者遍历结束）
        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）；
蓝色：前驱（prev）;
新加入了头结点，用来形成环

中序线索化