线索二叉树

对于具有 n 个结点的二叉树，采用二叉链存储结构时，每个结构有两个指针域，总共有 2n 个指针域，又由于只有 n−1 个结点被有效指针域所指向，则共有 2n−(n−1)=n+1 个空指针域。 遍历二叉树的结果是一个结点的线性序列，可以利用这些空链域存放指向结点的前驱结点和后继结点的地址。其规定是当某个结点的左指针为空时，令该指针指向这个线性序列中该结点的前驱结点；当某结点的右指针为空时，令该指针指向这个线性序列中该结点的后继结点，这样指向该线性序列中的“前驱结点”和“后继结点”称为线索。 创建线索的过程称为线索化。线索化的二叉树称为线索二叉树。由于遍历方式不同，产生的遍历线性序列也不同，会得到相应的线索二叉树。一般有先序线索二叉树、中序线索二叉树和后序线索二叉树。创建线索二叉树的目的就是提高该遍历过程的效率。 那么，在线索二叉树中如何区分指向的是左孩子结点还是前驱结点，右指针指向的是右孩子还是右孩子结点呢？为此，在结点的存储结构上增加两个标志位来区分这两种情况：

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 50
typedef char ElemType;
typedef struct node {
    ElemType data;          //结点数据域
    int ltag, rtag;         //增加的线索标记
    struct node *lchild;    //左孩子或线索指针
    struct node *rchild;    //右孩子或线索指针
} TBTNode;
void CreateTBTNode(TBTNode *&b, char *str);
void DispTBTNode(TBTNode *b);
void Thread(TBTNode *&p);
TBTNode *CreateThread(TBTNode *b);
void ThInOrder(TBTNode *tb);
TBTNode *pre;                   //全局变量
//对二叉排序树进行线索化
void Thread(TBTNode *&p) {
    if(p != NULL) {
        Thread(p->lchild);      //左孩子线索化

        if(p->lchild == NULL) { //左孩子不存在，进行前驱结点线索化
            p->lchild = pre;    //建立当前结点的前驱结点线索
            p->ltag = 1;
        } else {
            p->ltag = 0;        //p结点的左子树已线索化
        }

        if(pre->rchild == NULL) { //对pre的后继结点线索化
            pre->rchild = p;    //建立前驱结点的后继结点线索
            pre->rtag = 1;
        } else {
            pre->rtag = 0;
        }

        pre = p;
        Thread(p->rchild);      //右子树线索化
    }
}
//中序线索化二叉树
TBTNode *CreateThread(TBTNode *b) {
    TBTNode *root;
    root = (TBTNode *)malloc(sizeof(TBTNode));  //创建根节点
    root->ltag = 0;
    root->rtag = 1;
    root->lchild = b;

    if(b == NULL)               //空二叉树
        root->lchild = root;
    else {
        root->lchild = b;
        pre = root;              //pre是*b的前驱节点,供加线索用
        Thread(b);                //中序遍历线索化二叉树
        pre->rchild = root;      //最后一个节点的后继处理,加入指向根节点的线索
        pre->rtag = 1;
        root->rchild = pre;      //根节点右线索化
    }

    /*
    在某种遍历方式的线索二叉树中，若开始结点 p 没有左孩子，将 p 结点的左指针改为线索，对其指针仍为空；
    若最后结点 q 没有右孩子，将 q 结点的右指针改为线索，其右指针仍为空。
    对于其他结点 r ，若它没哟右左孩子，将左指针改为指向前驱结点的非空线索；
    若它没有右孩子，将右指针改为后继结点的非空线索。
    为了使创建二叉树的算法设计方便，为线索二叉树中再增加一个头结点。
    头结点的 data 域为空；lchild 指向无线索时的根结点，ltag 为 0 ；
    rtag 指向按某种方式遍历二叉树时的最后一个结点，rtag 为 1 。
    */
    return root;
}
//遍历线索化二叉树
void ThInOrder(TBTNode *tb) {
    TBTNode *p = tb->lchild;                    //p指向根结点

    while(p != tb) {
        while(p->ltag == 0)p = p->lchild;       //找开始结点

        printf(%c, p->data);                  //访问开始结点

        while(p->rtag == 1 && p->rchild != tb) {
            p = p->rchild;
            printf(%c, p->data);
        }

        p = p->rchild;
    }
}