[学习笔记]二叉树的线索化和遍历

在啃二叉树的线索话的时候遇到了一点疑惑,google和度娘和很多文章也没有对此的详解,遂做下笔记,方便自己也说不定也对此问题有同样疑惑的童鞋有帮助:)

线索化的原因:充分利用空闲指针域&&遍历的方便.

如下二叉树:

     A

   /    \

 B      C

/   \      \

D     E      F

结点C的左指针域,结点D,E,F的左右指针域都为空,通过观察与总结可以得出对于一个有n个结点的二叉树来说一共有2n个指针域,分支有n-1条,空指针域则有2n-(n-1)=n+1个.

线索化:对二叉树以某种次序遍历使其变为线索二叉树的过程就叫做二叉树.简单来讲就是如果空指针域为左指针域,则指向该结点的前驱,即它的双亲.如果空指针域为右指针域,则指向该结点的后继.

把上面的二叉树按照中序遍历并且进行线索化后如下图:

1 (1).png

因为不知道某一节点的左指针域和右指针域到底是指向孩子还是前驱(或后继),于是对二叉树的的结构进行以下调整:

typedef enum {Link,Thread}PointerTag;//枚举,当Link==0表示为左右孩子指针

typedef struct BiThrNode{
    int Data;//结点数据
    struct BiThrNode *lchild,*rchild;//左右孩子指针
    PointerTag LTag,RTag;//判断左右结点的标志
}BiThrNode,*BiThrNode;

然后<<大话>>上面给出了中序线索化的代码:

BiThrTree Pre;

void InThreading(BiThrTree T)
{
    if(T)
    {
        InThreading(T->lchild);//递归左孩子线索化
        
        if(!T->lchild)//左孩子线索化
        {
            T->LTag=Thread;
            T->lchild=Pre;
        }
        if(!Pre->rchild)//右孩子线索化
        {
            Pre->RTag=Thread;
            Pre->rchild=p;
        }
        
        Pre=p;//Pre更新位置
        
        InThreading(T->rchild);//递归右孩子线索化
    }
}

这里就是不断地递归来进行线索化.上面代码中左孩子的线索化我倒是明白,但是右孩子线索化就不是很理解了.找遍了网络也没有见对这里详解的文章.直到第二天我进行一步步的递推后才恍然大悟.下面详细说一下:

仍然来上面的那个二叉树来举例子.首先我们的Pre是指向头指针的.然后InThreading(头指针),根据上面的函数,在遇到第一个语句InThreading(T->lchild)于是进行递归调用InThreading(结点B),然后再次递归调用InThreading(T->lchild).x现在变成了InThreading(结点D).也就是下图:

1 (2).png

然后执行函数InThreading(结点D),进入函数体后执行InThreading(结点D->lchild).因为为空,返回.接着执行判断if(!T->lchild),发现左孩子确实为空,于是把左孩子指向Pre,也就是头指针(见上图Pre==头指针).再接着执行if(!Pre->rchild),不成立,跳过判断接着执行Pre=p;好了,现在Pre==结点D了.执行Inthreading(结点D->rchild).为空返回.好了.这个时候函数InThreading(结点D)也就是InThreading(结点B->lchild)执行完了.接下来执行InThreading(结点B)中的if(!结点B->lchild),不成立,返回,接着if(!Pre->rchild).我们知道刚才Pre更新为结点D,也就是说if(!Pre->rchild)==if(!结点D->rchild).哎呀,正好成立,进入判断体,结点D->rchild指向它的后驱也就是现在的结点B.好了,这就是右孩子线索化.剩下的就自己同理不做详细说明了.所以说实践得真知,动手了才明白...

接着是遍历的C代码,每行代码都写了详细注释就不做说明了,不会的自己动手跟着走一遍就清楚了.

BOOL InOrderTraverse_Thr(BiThrTree T)//T为头指针
{
     BiThrTree p;
     p=T->lChild;//先让p指向二叉树的根结点
     while(p!=T)//当树为空或者已经遍历完成时p==T,
     {
        while(P->LTag==Link)//这里是让结点p指向中序遍历的第一个结点,用上面的二叉树例子来讲就是指向结点D
            p=p->lchild;
        printf("%c",p->Data);//输出该结点
        while(p->Rtag==Thread&&p->rchild!=T)//看当前结点的后继,如果不是指向右孩子同时不是指向头指针,那么不断遍历
        {
            p=p->rchild;//更新当前结点位置
            printf("%c",p->Data);//输出新的当前结点位置的数据
        }
        p=p->rchild;//这里是表示上面的循环结束返回到了某个结点的双亲,那么我们接下来就是把该双亲的右孩子更新为新的当前结点
     }
}

<<大话>>上只有中序线索化,我就想了,既然遍历法都有前序中序和后序,那么肯定也有其相应的线索化方法.于是我自己又接着摸索了下,下面上代码:

1.前序线索化:

BiThrTree Pre;

void PreThreading(BiThrTree T)
{
    if(T)
    {
    
    
        if(!T->lchild)//左孩子线索化
        {
            T->LTag=Thread;
            T->lchild=Pre;
        }
        if(!Pre->rchild)//右孩子线索化
        {
            Pre->RTag=Thread;
            Pre->rchild=p;
        }
        
        Pre=p;//Pre更新位置
        
        if(Link==T->LTag)
            InThreading(T->lchild);//递归左孩子线索化
        if(Link==T->RTag)
            InThreading(T->rchild);//递归右孩子线索化
    }
}

上面代码中的递归左右孩子线索化时为什么要加一个判断呢?在我摸索时我发现如果不加判断的话,用上面的二叉树来举例子,当递归到结点D时,对结点D的左孩子线索化后且更新了Pre为结点D,而此时接着执行InThreading(T->lchild)时发现结点D->lchild不是空的,也就是说会陷入死循环递归,而我们从根结点处递归下来就没有问题,我就发现了在前序线索化的时候只有双亲才会进行递归调用InThreading()函数.这就是这两个判断的由来:)

那么如何遍历呢?很简单呀,先输出结点A,B,然后是B-lchild,然后是C->rchild,然后是E->rchild.然后我们就发现了一个规律了,如果不是叶节点,那么就是先输出当前结点的值,然后更新的当前结点位置为该结点的左孩子.而如果是叶结点的话,那么更新新的结点位置为该结点的右孩子.好了,发现规律了代码也就出来了

BOOL PreOrderTravese_Thr(BiTriTree T)//T为头指针
{
    BiThrTree p;
    
    p=T->lchild;//先让p指向根结点
    while(p!=T)//当树为空或者遍历结束的时候p==T
    {
        printf("%c",p->Data);//输出当前结点的值
        if(p->Ltag==Link)//如果当前结点的lchild为左孩子,那么当前结点更新为其左孩子
        {
            p=p->lchild;
            break;
        }
        else if(p->RTag==Link)//如果当前结点没有左孩子但是又右孩子,那么当前结点更新为其右孩子
        {
            p=p->rchild;
            break;
        }
        
        p=p->rchild;//左右结点都不是孩子,那么肯定是前驱或后继了,那么更新当前结点为其后继
    }
    
    return true;
}

2.后序线索化:

BiThrTree Pre;

void SufixThreading(BiThrTree T)
{
    if(T)
    {
        InThreading(T->lchild);//递归左孩子线索化
        InThreading(T->rchild);//递归右孩子线索化\
        
        if(!T->lchild)//左孩子线索化
        {
            T->LTag=Thread;
            T->lchild=Pre;
        }
        if(!Pre->rchild)//右孩子线索化
        {
            Pre->RTag=Thread;
            Pre->rchild=p;
        }
        
        Pre=p;//Pre更新位置
    }
}

理解了前序和中序线索化,后序也就没有什么问题了.这里也就不多说了.

后序遍历:

BOOL SufixTraverse_Thr(BiTriTree T)//先让结点为根结点
{
    if(!T)//结点不为空
    {
        if(Link==T->LTag)//还有左孩子,递归下去
            SufixTraverseThr(T->lchild);
        else if(Link==T->RTag)//还有右孩子,递归下去
            SuffixTraverseThr(T->rchild);
        
        printf("%c".T->Data);//已经到了叶节点,输出此结点数据
        
        return true;//返回true
    }
    return false;//返回false
}

后序遍历我还是用了递归,因为鼓捣了很久发现当当前结点有左右孩子的时候,下一个结点可能是根结点(如当遍历到上面例子中的C时),也可能是它的右兄弟(如当遍历到上面例子中的B时).最后发现这厮用递归的话最方便啊,而且时间复杂上上面也看的出来是O[n].不过我估计如果数据量超级大的话,额,那个内存的消耗,杠杠滴不过除了这法子之外我实在鼓捣不出更加牛逼的算法了.如果有知道的还望告知下,google了没有发现后序算法