线索二叉树

之前我们说过二叉树的顺序存储和链式存储，那么今天我们来说一下线索化二叉树是如何实现的。

线索化二叉树其实就是在二叉树的节点上添加线索，对二叉树进行某种遍历，使其变为线索二叉树的过程。

二叉事的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个节点都有唯一前驱和后继（除第一个节点和最后一个节点）。对于一个二叉树节点，找到其左右节点是非常方便的，但是其前驱后继只有在遍历中的到，为了容易找到前驱和后继，就有了二叉树的线索化。

因此，二叉树的线索化优点：
1、节省了内存空间
2、方便寻找节点的前驱和后继（主要优点）

图1为一个二叉树

图1.png

图2为中序遍历线索化过程

图2.png

从图2可以明显的看出来，每个节点的左孩子指向的为该节点的后继节点，而该节点的右孩子指向中序遍历次序的下一个节点，因此，我们可以很容易的得到每一个节点的前驱和后继节点。

那么问题又出现了， 我们如何区分一个节点的左孩子指针指向的是左孩子还是前驱节点

我们可以通过一个结构体标示，来记录该节点的左孩子，有孩子，前驱和后继，
对记录的值进行判断，来得到一个节点的左孩子是前驱还是指向左孩子

15880436508319.png

下面我们通过代码来实现一下线索二叉树过程。

先对数据进行存储

//二叉树构造
int indexs = 1;
typedef char String[24];    /*  0号单元存放串的长度 */
String str;

Status StrAssign(String T,char *s){
    int i;
    if(strlen(s)>MAXSIZE)
        return ERROR;
    else{
        T[0] = strlen(s);
        for (i = 1; i<=T[0]; i++) {
            T[i] = *(s+i-1);
        }
        return OK;
    }
}

对二叉树进行构造，通过枚举值进行记录该节点是有前驱和后继的线索和左右孩子指针
并用前序遍历对二叉树进行赋值

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

typedef enum {Link,Thread}  PointerTag;

//线索话二叉树的构造

typedef struct BiThrNode{
    //数据
    ElemType data;
    
    //左右孩子指针
    struct BiThrNode *lChild,*rChild;
    
    //左右标记
    PointerTag LTag;
    PointerTag RTag;
}BiThrNode,*BiThrTree;


//1、首先构造二叉树
Status CreateBiThrTree(BiThrTree *T){
    ElemType 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;
}

对二叉树进行中序线索化
通过一个全局变量记录刚刚访问过的节点，用递归遍历，将刚刚访问过的节点的后继指向p节点，并创建新的头节点，将最后一个左子树节点的左孩子指针和最后右子树节点的右孩子指向头节点，将头节点指向根节点，来实现线索二叉树

//2、中序遍历二叉树T，将其中序线索化，Thrt指向头节点

//全局变量，始终指向刚刚访问过的节点
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;
        }else{
            pre->RTag = Link;
        }
        //保持pre指向p的前驱
        pre = p;
        //递归右子树线索化
        InThreading(p->rChild);
        
    }
}

//中序遍历二叉树T,并将其中序线索化,p指向头结点

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

最后，中序遍历线索二叉树，从左子树依次向右子树进行遍历，若不为空则打印输出。

//中序遍历二叉树线索化
Status InOrderDisplay(BiThrTree T){
    BiThrTree p;
    //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;
            printf("%c ",p->data);
        }
        //访问后继节点
        p = p->rChild;
    }
    return OK;
}

main函数调用

 printf("二叉树线索化!\n");
    BiThrTree P,T;
    
    StrAssign(str, "ABDH##I##EJ###CF##G##");
    
    //按前序产生二叉树
    CreateBiThrTree(&T);
    //中序遍历中序线索化二叉树
    InOrderThread(&P, T);
    InOrderDisplay(P);
    printf("\n");

打印结果：

15880442626394.png