二叉树—线索二叉树

1、线索二叉树的引入

在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。

对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索。

没有叶子节点的节点的左右指针浪费了

优势
(1)利用线索二叉树进行中序遍历时，不必采用堆栈处理，速度较一般二叉树的遍历速度快，且节约存储空间。
(2)任意一个结点都能直接找到它的前驱和后继结点。

劣势
(1)结点的插入和删除麻烦，且速度也较慢。
(2)线索子树不能共用。

结点结构

结点结构
中序遍历的结果：HDIBJEAFCG, 线索化是将H D I 等串起来，有孩子的(RTag或LTag)标识Link，没孩子的(RTag或LTag)标识Thread。
线索化的二叉树
预设

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */

/* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int Status;
typedef char CElemType;
/* 字符型以空格符为空 */
CElemType Nil='#';
int indexs = 1;
typedef char String[24]; /*  0号单元存放串的长度 */
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;
    }
}

存储节点

/* Link==0表示指向左右孩子指针, */
/* Thread==1表示指向前驱或后继的线索 */
typedef enum {Link,Thread} PointerTag;

/* 线索二叉树存储结点结构*/
typedef struct BiThrNode{
    
    //数据
    CElemType data;
    
    //左右孩子指针
    struct BiThrNode *lchild,*rchild;
    
    //左右标记
    PointerTag LTag;
    PointerTag RTag;
    
}BiThrNode,*BiThrTree;

构建线索二叉树

/*
 8.1 打印
 */
Status visit(CElemType e)
{
    printf("%c ",e);
    return OK;
}
/*
 8.3 构造二叉树
 按照前序输入线索二叉树结点的值,构造二叉树T
 */

Status CreateBiThrTree(BiThrTree *T){
    
    CElemType h;
    //scanf("%c",&h);
    //获取字符
    h = str[indexs++];
    
    if (h == Nil) {
        *T = NULL;
    }else{
        *T = (BiThrTree)malloc(sizeof(BiThrNode));
        if (!*T) {
            exit(OVERFLOW);
        }
        //生成根结点(前序)
        (*T)->data = h;
        
        //递归构造左子树
        CreateBiThrTree(&(*T)->lchild);
        //存在左孩子->将标记LTag设置为Link
        if ((*T)->lchild) (*T)->LTag = Link;
        
        //递归构造右子树
        CreateBiThrTree(&(*T)->rchild);
        //存在右孩子->将标记RTag设置为Link
        if ((*T)->rchild) (*T)->RTag = Link;
    }
    
    return OK;
}

中序遍历二叉树T, 将其中序线索化

BiThrTree pre; /* 全局变量,始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化*/
void InThreading(BiThrTree p){
    
    if (p) {
        
        InThreading(p->lchild);//递归左子树线索化
       
        if (!p->lchild) { //无左孩子
            
            p->LTag = Thread;//前驱线索
            
            p->lchild  = pre;//左孩子指针指向前驱
        }else {
            p->LTag = Link;
        }
        
        if (!pre->rchild) {//前驱没有右孩子
            
            pre->RTag = Thread;//后继线索
            
            pre->rchild = p;//前驱右孩子指针指向后继(当前结点p)
        }else {
            pre->RTag = Link;
        }
        
        pre = p;//保持pre指向p的前驱
        
        InThreading(p->rchild);//递归右子树线索化
    }
}

线索二叉树—双向链表结构

中序遍历二叉树T,并将其中序线索化,Thrt指向头结点(加个头结点)，遍历最后的节点联向头结点，构成双向循环

加头结点，双向结构

Status InOrderThreading(BiThrTree *Thrt , BiThrTree T){
    
    *Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
    if (! *Thrt) {
        exit(OVERFLOW);
    }
    
    //建立头结点;
    (*Thrt)->LTag = Link;
    (*Thrt)->RTag = Thread;
    
    (*Thrt)->rchild = (*Thrt);//右指针回指向
    
    if (!T) {/* 若二叉树空,则左指针回指 */
        (*Thrt)->lchild= *Thrt;
    }else{
        
        (*Thrt)->lchild=T;
        pre = *Thrt;
        
        //中序遍历进行中序线索化
        InThreading(T);
        
        //最后一个结点rchil 孩子
        pre->rchild = *Thrt;
        //最后一个结点线索化
        pre->RTag = Thread;
        (*Thrt)->rchild = pre;
        
    }
    return OK;
}

中序遍历二叉线索树T

Status InOrderTraverse_Thr(BiThrTree T){
    BiThrTree p;
    p=T->lchild; /* p指向根结点 */
    while(p!=T) { /* 空树或遍历结束时,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");
    BiThrTree H,T;
    
    //StrAssign(str,"ABDH#K###E##CFI###G#J##");
    StrAssign(str,"ABDH##I##EJ###CF##G##");
    
    CreateBiThrTree(&T); /* 按前序产生二叉树 */
    InOrderThreading(&H,T); /* 中序遍历,并中序线索化二叉树 */
    InOrderTraverse_Thr(H);
    printf("\n\n");
    return 0;
}

总结：根据二叉树的遍历方式，其线索化也分为前中后序的线索化。