线索二叉树

线索二叉树原理

image.png

通过观察上图可以看到，指针域利用的并不充分，有许多的"^"，也就是空指针域的存在，这实在不是个好现象，我们想想能如何利用起来。
首先，我们来看一下共有多少空指针域？对于一个有n个结点的二叉树，则共有2n个指针域（因为每个结点都有两个指针域分别指向左右孩子），而n个结点的二叉树一共有n-1条分支线，也就是说，其实有2n-(n-1)=n+1个空指针域。如上图中，有10个结点，而带有"^"的空指针域有11个。
在二叉树链表上，我们只能知道每个结点指向其左右孩子结点的地址，而不知道某结点的前驱、后继分别为谁，要想知道则必须将二叉树遍历一遍，且以后每需要知道一次必须遍历一次，这无疑是一个糟糕的使用体验。
综合上面分析，我们是否可以考虑利用那些空指针地址，存放指向某结点在某种遍历次序下的前驱或后继结点的地址呢？答案是可以的。我们把这种指向前驱和后继的指针称为线索，加上线索的二叉树链表称为线索表，相应的二叉树称为线索二叉树。我们对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。
线索化的二叉树，在进行遍历的时候，其实就等价于操作一个双向链表结构，因为类似双向链表结构，所以我们在二叉树线索链表上加上一个头结点。使头结点满足以下3个条件：

• 将头结点的lchild域指针指向二叉树的根结点，且标志为左孩子；
• 将头结点的rchild域指针指向遍历时的最后一个结点；
• 使二叉树中遍历的第一个结点中，lchild域指针和最后一个结点的rchild指针域指针都指向头结点；

线索化二叉树-前序遍历

void PreThreading(BiThrTree p){
    if(p != NULL){
        if(p->lchild == NULL){
            p->lchild = pre;
            p->LTag = Thread;
        }
        else{
            p->LTag = Link;
        }
        
        if(pre->rchild == NULL){
            pre->rchild = p;
            pre->RTag = Thread;
        }
        else{
            pre->RTag = Link;
        }
        pre = p;
        
        if(p->LTag == Link){
            PreThreading(p->lchild);
        }
        if(p->RTag == Link){
            PreThreading(p->rchild);
        }
    }
}
Status PreOrderThreading(BiThrTree *Thrt , BiThrTree T){
    *Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
    if (*Thrt == NULL) return ERROR;
    //建立头结点;
    (*Thrt)->LTag = Link;
    (*Thrt)->RTag = Thread;
    //右指针回指向
    (*Thrt)->rchild = (*Thrt);
    /* 若二叉树空,则左指针回指 */
    if (!T) {
        (*Thrt)->lchild=*Thrt;
    }else{
        (*Thrt)->lchild=T;
        pre=(*Thrt);
        
        //前序遍历进行中序线索化
        PreThreading(T);
        
        //最后一个结点rchil 孩子
        pre->rchild = *Thrt;
        //最后一个结点线索化
        pre->RTag = Thread;
        (*Thrt)->rchild = pre;
        
    }
    
    return OK;
}
Status PreOrderTraverse_Thr(BiThrTree T){
    BiThrTree p;
    p = T->lchild;
    
    while(p != T){//空树或者遍历完成
        printf("%c ", p->data);
        if(p->LTag == Link){//当LTag=0时,循环到中序的第一个结点
            p = p->lchild;
        }
        else{
            p = p->rchild;
        }
    }
    
    return OK;
}

线索化二叉树-中序遍历

BiThrTree pre; /* 全局变量,始终指向刚刚访问过的结点 */
void InThreading(BiThrTree p){
    if(p != NULL){
        InThreading(p->lchild);
        if(p->lchild == NULL){
            p->lchild = pre;
            p->LTag = Thread;
        }
        else{
            p->LTag = Link;
        }
        
        if(pre->rchild == NULL){
            pre->rchild = p;
            pre->RTag = Thread;
        }
        else{
            pre->RTag = Link;
        }
        pre = p;
        InThreading(p->rchild);
    }
}

Status InOrderThreading(BiThrTree *Thrt , BiThrTree T){
    *Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
    if (*Thrt == NULL) return ERROR;
    //建立头结点;
    (*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;
}

Status InOrderTraverse_Thr(BiThrTree T){
    BiThrTree p;
    p = T->lchild;
    
    while(p != T){//空树或者遍历完成
        while(p->LTag == Link){//当LTag=0时,循环到中序的第一个结点
            p = p->lchild;
        }
        printf("%c ", p->data);
        while (p->RTag == Thread && p->rchild != T) {
            p = p->rchild;
            printf("%c ", p->data);
        }
        p = p->rchild;
    }
    
    return OK;
}

线索化二叉树-后序遍历

后序遍历与前序、中序略不同，后序遍历可归纳为以下4点：
1、若结点p为根，则无后继；
2、若结点p为其双亲的右孩子，则其后继为其双亲；
3、若结点p为其双亲的左孩子，且双亲无右子女，则其后继为其双亲；
4、若结点p为其双亲的左孩子，且双亲有右子女，则结点*p的后继是其双亲的右子树中按后序遍历的第一个结点。

Status CreateBiThrTreeForPost(BiThrTree *T, BiThrTree p)
{
    char ch = str[indexs++];
    if(ch == '#'){
        *T = NULL;
        return OK;
    }
    else
    {
        *T= (BiThrTree)malloc(sizeof(BiThrNode));
        if(*T == NULL) return ERROR;
        (*T)->data = ch;//生成根节点
        (*T)->parent = p;//指回原来的结点
        (*T)->LTag=Link;
        CreateBiThrTreeForPost(&(*T)->lchild,(*T));//创建左子树
        (*T)->RTag=Link;
        CreateBiThrTreeForPost(&(*T)->rchild,(*T));//创建右子树
    }
    return 1;
}
void PostThreading(BiThrTree p){
    if(p != NULL){
        PostThreading(p->lchild);
        PostThreading(p->rchild);
        
        if(p->lchild == NULL){
            p->lchild = pre;
            p->LTag = Thread;
        }
        else{
            p->LTag = Link;
        }
        if(pre != NULL){
            if(pre != NULL && pre->rchild == NULL){
                pre->rchild = p;
                pre->RTag = Thread;
            }
            else if(pre != NULL){
                pre->RTag = Link;
            }
        }
        pre = p;
    }
}
//后序遍历时，已经去掉了头结点，因为在后序遍历中，最后的结点就是头结点，所以无需再增加头结点
Status PostOrderTraverse_Thr(BiThrTree T){
    BiThrTree p;
    p = T;
    pre = NULL;
    while(p!=NULL){
        while(p->LTag == Link){//先找到最左叶子结点
            p = p->lchild;
        }
        while(p->RTag == Thread){//找左叶子结点的后继
            visit(p->data);//打印左叶子结点
            pre = p;//修改pre的值
            p = p->rchild;//p变成前一个结点的后继
        }
        if(p==T){//p是否是头结点，如果是则表示已经遍历完成
            visit(p->data);
            break;
        }
        while(p && p->rchild == pre){//如果p的右孩子与前一个结点相同
            visit(p->data);
            pre = p;//修改pre的值
            p = p->parent;//本来，p的后继为p的parent，但由于p的parent存在右子树，所以此时需要通过parent找到p的后继
        }
        if(p && p->RTag == Link)
            p = p->rchild;
    }
    return OK;
}