线索二叉树小结

观察二叉树的链式存储结构，我们发现结点的指针域并没有充分的被利用，存在很多空指针（即指针域为NULL）

对于一个有n个结点的二叉树链表，每个结点都有指向左右子树的两个指针域，一共有2n个指针域。而n个结点的二叉树又有n - 1条分支树，也就是存在2n-(n-1) = n + 1个空指针域。

因此，可以用空指针域来存放结点的前驱和后继，这就是线索二叉树。

结点结构

如果只是在原二叉树的基础上利用空指针域，就存在一个问题：如何区别某一个结点的左子树指针域是指向他的左子树还是前驱结点？右子树指针域是指向右子树还是后继结点？

所以，在每个结点都增设两个标志域LTag和RTag，存放0和1的布尔型变量。

LTag为0是指向该结点的左子树，为1是指向该结点的前驱
RTag为0是指向该结点的右子树，为1是指向该结点的后继

typedef char TElemType;

/* Link = 0，表示指向左右子树  Thread = 1, 表示指向前驱或者后继 */
typedef enum { Link, Thread } PointerTag;

typedef struct BiThrNode {
    TElemType data;
    struct BiThrNode *leftChild, *rightChild;
    PointerTag LTage, RTag;
}BiThrNode, *BiThrTree;

线索化

对普通二叉树以某种次序遍历使其成为线索二叉树的过程就叫线索化

因为前驱和后继结点只有在二叉树的遍历过程中才能得到，所以线索化的具体过程： 在二叉树遍历中修改空指针

线索化具体实现

这里以中序遍历二叉树的线索化为例，线索化的具体实现就是将二叉树的中序遍历进行修改。

设置一个pre指针，永远指向遍历当前结点的前一个结点。
若遍历的当前结点左指针域为空，则把当前结点左指针指向pre
当pre的右指针域为空，则把pre的右指针指向当前结点
最后把当前结点赋给pre
递归遍历完成线索化

中序遍历线索化的递归函数，代码如下：

void inThreading(BiThrTree T, BiThrTree *pre) {
    if (!T) { return; }
    
    inThreading(T->leftChild, pre);
    
    if (!T->leftChild) {
        T->LTag = Thread;
        T->leftChild = *pre;
    }
    if (!(*pre)->rightChild) {
        (*pre)->RTag = Thread;
        (*pre)->rightChild = T;
    }
    *pre = T;
    
    inThreading(T->rightChild, pre);
}

蹭设头结点

线索化后的二叉树，就如同一条双向链表。为二叉树增设一个头结点，这样就和双向链表一样了，即能够从第一个结点正向遍历，也可以从最后一个结点逆向遍历

头结点

左指针域指向二叉树的根结点
右指针指向中序遍历访问的最后一个结点
二叉树中序序列的第一个结点，左指针域指向头结点
二叉树中序序列的最后一个结点，右指针域指向头结点

代码如下：

void inOrderThreading(BiThrTree T, BiThrTree *head) {
    *head = (BiThrTree)malloc(sizeof(BiThrNode));
    if (head == NULL) {
        return;
    }
    (*head)->LTag = Link;
    (*head)->RTag = Thread;
    (*head)->rightChild = *head;
    if (!T) {
        (*head)->leftChild = *head;
        return;
    }
    
    BiThrTree pre = *head;
    (*head)->leftChild = T;
    inThreading(T, &pre);
    
    pre->rightChild = *head;
    pre->RTag = Thread;
    (*head)->rightChild = pre;
}

中序遍历线索二叉树

遍历线索二叉树，就是通过之前建立的线索，沿着后继线索依次访问

void InOrderTraverse(BiThrTree T) {
    BiThrNode *p = T->leftChild;

    while (p != T) {
        while (p->LTag == Link) {
            p = p->leftChild;
        }
        printf("%c  ", p->data);
        
        while (p->RTag == Thread && p->rightChild != T) {
            p = p->rightChild;
            printf("%c  ", p->data);
        }
        p = p->rightChild;
    }
}

完整代码