线索二叉树

WHY

方便从任一个结点出发，找到其前驱、后继；方便遍历

普通二叉树中，对任意一个结点，若想找到其前驱/后继结点，只能再进行一次相应的前/中/后序遍历才行，复杂度太高。

为此，我们引入前驱线索，后继线索的概念。其中，前驱线索由左孩子指针充当，后继线索由右孩子指针充当。

typedef struct  BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

构建出如下图所示的结构：

但是，

*lchild(*rchild)有可能指向存在的结点，为此我们引入线索标志。当线索标志为1时，表示孩子指针指向前驱后继，线索标志为0时，表示孩子指针指向左右孩子。此时

typedef struct  ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;//左右线索标志
}ThreadNode,*ThreadTree;

这样，每一个线索链表中的结点就可以图示为:

HOW

如何分别用代码实现前中后序遍历下的线索链表

1.中序线索化

其实中序线索化的过程就是再进行一遍中序遍历，为每个节点添加额外的信息(lchild, rcild, ltag, rtag).

🍔初始定义结构体

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;
}ThreadNode,*ThreadTree;

🍔定义前驱指针

ThreadNode *pre=NULL;

前驱指针还可以定义在局部，这里为了方便起见，将pre定义为全局。

🍔开始定义处理函数

void CreatInThread(ThreadTree T){
    pre=NULL;
    if(T!=NULL){
        InThread(T);
        if(pre->rchild==NULL){
            pre->rtag=1;
        }
    }
}

注意：最后一个节点单独处理

🍔中序遍历二叉树，顺便线索化

void InThead(ThreadTree T){
    if(T!=NULL){
        //左根右
        InThead(T->lchild);
        visit(T);
        InThead(T->rchild);
    }
}

🍔访问节点时加上线索信息

void visit(ThreadNode q){
    if(q->lchild==NULL){
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL && pre->rchild==NULL){
        pre->rchild=p;
        pre->rtag=1;
    }
    pre=q;
}

此外，合并之后：

void InThread(ThreadTree p,Thread &pre){
    if(p!=NULL){
        //左
        InThread(p->lchild,pre);
        //根
        if(p->lchild==NULL){
            p->lchild=pre;
            p->ltag=1;
        }
        if(pre!=NULL && pre->rchild==NULL){
            pre->rchild=p;
            pre->rtag=1;
        }
        pre=p;
        //右
        InThread(p->rchild,pre);
    }
}
void CreatInThread(ThreadTree T){
   ThreadTree pre=NULL;
    if(T!=NULL){
        InThread(T,pre);
        //处理最后一个节点
        pre->rchild==NULL
        pre->rtag=1;        
    }
}

注意在CreatInThread并不需要判断pre->rchild是否为NULL

因为，按照中序遍历的顺序“左根右”，最后退出循环之后pre不可能有rchild，否则还会按照“根右”的顺序继续执行InThread,所以退出循环的pre必然为中序遍历下的最后一个结点。

2.先序线索化

代码参考中序线索化

void PreThead(ThreadTree T){
    if(T!=NULL){
        //根左右
        visit(T);
        PreThead(T->lchild);
        PreThead(T->rchild);
    }
}

由于先进行根节点的vist操作，如图，在vist(4)完成之后，根据规则，④的lchild指针指向②，因此就会陷入无限循环的困境……

为此，只需在进行PreThead(T->lchild)前加一句判断即可，具体如下：

void InThead(ThreadTree T){
    if(T!=NULL){
        //根左右
        visit(T);
        if(T->ltag==0){//lchild不是前驱线索时才访问lchild
                PreThead(T->lchild);
        }
        PreThead(T->rchild);
    }
}

其余参考中序线索化即可。

3.后续线索化

void PreThead(ThreadTree T){
    if(T!=NULL){
        //左右根
        PreThead(T->lchild);
        PreThead(T->rchild);
         visit(T);
    }
}

其余参考中序线索化即可。

WHERE

如何使用线索二叉树实现前中后序遍历下的查找前驱后继的问题

1.中序线索二叉树

对于一颗中序线索化后的二叉树

🍖当某结点ltag==1时，前驱后继分别为lchild,rchild

🍖当某结点ltag==0时，根据中序遍历“左根右”的顺序：

  • 前驱为lchild在中序遍历下最后被访问的那个结点
  • 后继为rchild在中序遍历下最先被访问的那个结点

2.先序线索二叉树

🍖对于后继，参考中序线索二叉树即可。

🍖对于前驱，由于先序遍历“根左右”的遍历顺序，该节点无法找到前驱😰

  • 解决办法一：从头至尾进行一次先序遍历，找到其前驱。

  • 解决办法二：引入三叉树，为每个节点存储parent指针，即指向父节点，此时前驱为：

    image-20210515141736890

3.后序线索二叉树

参考先序线索二叉树

4. 另外

🧐中序遍历下最后被访问的那个结点如何通过代码找到？

根据中序遍历 左根右 的顺序，即为最“右下”的结点，但不一定是叶节点哦

ThreadNode *Lastnode(ThreadNode *p){
    while(p->rtag==0) p=p->rchild
    return p;
}