数据结构与算法——线索二叉树

一、概念

对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索。在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。
这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

二、存储结构

线索二叉树中的线索能记录每个结点的前驱和后继信息，为了区别线索指针和孩子指针，在每个结点中设置两个标志ltag和rtag。
当ltag和rtag为0时，leftChild和rightChild分别是指向左孩子和右孩子的指针；否则，leftChild是指向结点前驱的线索(pre)，rightChild是指向结点的后继线索(suc)。由于标志只占用一个二进位，每个结点所需要的存储空间节省很多。
线索二叉树结点结构如下：

线索二叉树.png

其中：ltag=0 时lchild指向左儿子；ltag=1 时lchild指向前驱；rtag=0 时rchild指向右儿子；rtag=1 时rchild指向后继。
线索二叉树代码：

#include <stdio.h>
#include "stdlib.h"
#include "string.h"
#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

/* 存储空间初始分配量 */
#define MAXSIZE 100
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;
int indexs = 1;
typedef  char String[24];
String str;
Status StrAssign(String T,char *chars)
{
    int i;
    if(strlen(chars)>MAXSIZE)
        return ERROR;
    else
    {
        T[0]=strlen(chars);
        for(i=1;i<=T[0];i++)
            T[i]=*(chars+i-1);
        return OK;
    }
}
typedef char CElemtype;
/* Link==0表示指向左右孩子指针, */
/* Thread==1表示指向前驱或后继的线索 */
typedef enum {Link,Thread} PointerTag;
CElemtype Nil = '#';
typedef struct ThreadBinaryNode{
    //结点数据
    CElemtype data;
    //左孩子右孩子
    struct ThreadBinaryNode *lchild,*rchild;
    //左右标志
    PointerTag rtag,ltag;
}ThreadBinaryNode,*ThBizTree;
//1.1打印
Status visit(CElemtype e)
{
    printf("%c ",e);
    return OK;
}
Status CreateThrBiTree(ThBizTree *T){
    CElemtype h;
    h = str[indexs++];
    if (h==Nil) {
        *T = NULL;
    }else{
        *T = (ThBizTree)malloc(sizeof(ThreadBinaryNode));
        if (!*T) {
            exit(OVERFLOW);
        }
        //生成根结点
        (*T)->data = h;
        //递归构造左子树
        CreateThrBiTree(&(*T)->lchild);
        if ((*T)->lchild) {
            (*T)->ltag = Link;
        }
        //递归构造右子树
        CreateThrBiTree(&(*T)->rchild);
        if ((*T)->rchild) {
            (*T)->rtag = Link;
        }
    }
    return OK;
}
ThBizTree pre; /* 全局变量,始终指向刚刚访问过的结点 */
//中序遍历
void InBinaryTree(ThBizTree B){
    if (B) {
        InBinaryTree(B->lchild);
        if (!B->lchild) {
            //没有左孩子,指向前驱
            B->ltag = Thread;
            //指向前驱
            B->lchild = pre;
        }else{
            //指向孩子
            B->ltag = Link;
        }
        if (!pre->rchild) {
                   //没有右孩子,指向前驱
                   pre->rtag = Thread;
                   //指向前驱
                   pre->rchild = B;
               }else{
                   //指向孩子
                   pre->rtag = Link;
               }
        //记录前驱
        pre = B;
        InBinaryTree(B->rchild);
    }
}
//中序遍历二叉树T，并将其中序线索化，Thrt指向头结点
Status InOderThreading(ThBizTree *Thrt,ThBizTree T){
    *Thrt = (ThBizTree)malloc(sizeof(ThreadBinaryNode));
    if (!*Thrt) {//分配失败
        exit(OVERFLOW);
    }
    //建立头结点
    (*Thrt)->ltag = Link;
    (*Thrt)->rtag = Thread;
    //右指针回指向
    (*Thrt)->rchild = (*Thrt);
    //若二叉树为空
    if (!T) {
        (*Thrt)->lchild = *Thrt;
    }else{
        
        (*Thrt)->lchild=T;
        pre=(*Thrt);
        
        //中序遍历进行中序线索化
        InBinaryTree(T);
        
        //最后一个结点rchil 孩子
        pre->rchild = *Thrt;
        //最后一个结点线索化
        pre->rtag= Thread;
        (*Thrt)->rchild = pre;
    }
    return OK;
}
Status visitOrderBiTree(ThBizTree T){
    ThBizTree p;
    //指向根结点
    p = T->lchild;
    while (p!=T) {
        while (p->ltag == Link)
            {
                p=p->lchild;
            }
            if(!visit(p->data)){
                return ERROR;
            }
            while (p->rtag == Thread && p->rchild!=T) {
                p=p->rchild;
                visit(p->data);
            }
            p = p->rchild;
    }
    return OK;
}
int main(int argc, const char * argv[]) {
    // insert code here...
     printf("Hello, 线索化二叉树!\n");
       ThBizTree H,T;
       
       //StrAssign(str,"ABDH#K###E##CFI###G#J##");
       StrAssign(str,"ABDH##I##EJ###CF##G##");
    CreateThrBiTree(&T);/* 按前序产生二叉树 */
    InOderThreading(&H,T);/* 中序遍历,并中序线索化二叉树 */
    visitOrderBiTree(H);

       printf("\n\n");    return 0;
}