全面理解线索二叉树

首先，线索二叉树的原理

通过检查各种二进制链表，无论叉形树的形状如何，空链域的数量始终大于非空链域的数量. 确切地说，n个节点的二进制列表具有2n个链域，非空链域为n-1，但是有n + 1个空链域. 如下所示.

因此，提出了一种使用原始空链域来存储指向树中其他节点的指针的方法. 该指针称为线索.

请记住，ptr指向二进制列表中的一个节点. 以下是创建线索的规则:

（1）如果ptr-> lchild为空，则以中阶遍历序列存储指向该节点的前驱节点. 该节点称为ptr的中阶前驱；

（2）如果ptr-> rchild为空，则以中阶遍历序列存储指向此节点的后继节点. 该节点称为ptr的中间序列后继者；

很明显，在确定lchild指向左孩子或前任孩子以及rchild指向右孩子或后继孩子时，需要一个区别标志. 因此，我们向每个节点添加了另外两个标签字段ltag和rtag. 请注意，ltag和rtag只是区分0或1数字的布尔变量，其内存占用空间小于lchild和rchild等指针变量. 节点结构如下所示.

位置:

（1）当ltag为0时，它指向节点的左子节点；当ltag为1时，它指向节点的前体；

（2）当rtag为0时，它指向节点的右子节点；当rtag为1时，它指向节点的后继者；

（3）因此，可以将上图中的二进制列表图修改为下图中的被采用的子代.

第二，线索二叉树结构的实现

二进制线索树的存储结构定义如下:

/* 二叉树的二叉线索存储结构定义*/
typedef enum{Link, Thread}PointerTag;    //Link = 0表示指向左右孩子指针；Thread = 1表示指向前驱或后继的线索
 
typedef struct BitNode
{
       char data;                                      //结点数据
       struct BitNode *lchild, *rchild;                //左右孩子指针
       PointerTag  Ltag;                               //左右标志
       PointerTag  rtal;
}BitNode, *BiTree;

线程的本质是更改二进制列表中的空指针，使其指向前任或后继. 由于只能在遍历二叉树时获得前驱信息和后继信息，因此提示过程是在遍历过程中修改空指针的过程.

中阶遍历线索的递归函数代码如下:

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

除了// ===之间的代码外，以上代码与二叉树中顺序遍历的递归代码完全相同. 只是将打印节点的功能更改为线索功能.

代码的中间部分是这样的:

由于此时尚未访问p节点的后继者，因此只能判断其前任节点pre的右指针rchild，如果（！pre-> rchild）表示如果它为空，则p为pre后继者，因此pre-> rchild = p，并设置pre-> rtag = Thread，完成后继节点的线索. 如图所示:

if（！p-> lchild）表示如果节点的左指针字段为空，因为它的前任节点刚刚访问并分配了pre，则可以将pre分配给p-> lchild并修改p-> ltag =线程（即定义为1）以完成前驱节点的线程化.

完成前任和后继判断之后，请不要忘记将当前节点p分配给pre以便于下一次使用.

拥有线索二叉树时，遍历它实际上等同于操作双向链表结构.

就像一个双向链表节点，如下图所示，将头节点添加到二叉树列表中，并使它的lchild字段指针指向二叉树的根节点（图中的第一步）. ，及其rchild字段指针指向中间顺序遍历访问中的最后一个节点（图中的第二步）. 相反，让二叉树的有序序列的第一个节点，lchild域指针和最后一个节点的rchild域指针都指向头节点（图中的第三和第四步）. 这样做的好处是我们可以连续从第一个节点遍历，也可以从最后一个节点遍历到祖先.

遍历代码如下所示.

//t指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向中序遍历的最后一个结点。
//中序遍历二叉线索树表示二叉树t
int InOrderThraverse_Thr(BiTree t)
{
    BiTree p;
    p = t->lchild;                               //p指向根结点
    while(p != t)                               //空树或遍历结束时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;                         //p进入其右子树
    }
 
    return OK;
}

说明:

（1）在代码中，p = t-> lchild;表示上图中的第一步，让p指向根节点并开始遍历；

（2）而（p！= t）实际上意味着循环直到图中的第四步出现，这意味着p指向头节点，所以它等于t（t是指向头的指针） node），结束循环，否则遍历遍历操作的整个循环；

（3）while（p-ltag == Link）的循环来自A-> B-> D->H. 这时线索二叉树是一种存储结构，H节点的ltag不是链接（即，不是）等于0），所以这个循环；

（4）然后只打印H;

（5）而（p-> rtag ==线程&& p-> rchild！= t），因为节点H的rtag =线程（等于1），并且它不指向头节点. 因此，打印H的后继D，然后D的rtag为Link，从而退出循环；

（6）p = p-> rchild;表示p指向节点D的右子I；

（7）.....，只要继续循环和遍历，直到打印出HDIBJEAFCG，结束遍历操作即可.

从此代码可以看出，它等效于链表扫描，因此时间复杂度为O（n）.

由于空指针字段的空间已被充分利用（等于节省空间）线索二叉树是一种存储结构，因此还确保了在创建时一次遍历可以终身使用后续信息（这意味着可以节省时间）. 因此，在实际问题中，如果需要遍历使用的二叉树或在遍历序列中找到需要某种前驱和后继的节点，那么使用线索二进制列表的存储结构是一个很好的选择.

#include <stdio.h>
#include <stdlib.h>
 
#define ERROR  0
#define OK  1
 
typedef enum{Link, Thread} PointerTag;      //link = 0表示指向左右孩子指针
                                            //Thread = 1表示指向前驱或后继的线索
typedef struct BitNode
{
    char data;                              //结点数据
    struct BitNode *lchild;                 //左右孩子指针
    struct BitNode *rchild; 
    PointerTag ltag;                        //左右标志
    PointerTag rtag;
}BitNode, *BiTree;
 
BiTree pre;                                 //全局变量，始终指向刚刚访问过的结点
 
//前序创建二叉树
void CreateTree(BiTree *t)
{
    char ch;
    scanf("%c", &ch);
     
    if(ch == '#')
    {
        *t = NULL;
    }
    else
    {
        (*t) = (BiTree)malloc(sizeof(BitNode));
        if((*t) == NULL)
        {
            return;
        }
        (*t)->data = ch;
        CreateTree(&((*t)->lchild));
        CreateTree(&((*t)->rchild));
    }
}
 
 
//t指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向中序遍历的最后一个结点。
//中序遍历二叉线索树表示的二叉树t
int InOrderThraverse_Thr(BiTree t)
{
    BiTree p;
    p = t->lchild;           //p指向根结点
    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;           //p进入其右子树
    }
 
    return OK;
}
 
//中序遍历进行中序线索化
void InThreading(BiTree p)
{
    if(p)
    {
        InThreading(p->lchild);              //递归左子树线索化
        if(!p->lchild)                       //没有左孩子
        {
            p->ltag = Thread;                //前驱线索
            p->lchild = pre;             //左孩子指针指向前驱,这里是第3步
        }
        if(!pre->rchild)                 //没有右孩子
        {
            pre->rtag = Thread;              //后继线索
            pre->rchild = p;             //前驱右孩子指针指向后继(当前结点p)
        }
        pre = p;
 
        InThreading(p->rchild);              //递归右子树线索化
    }
}
//建立头结点，中序线索二叉树
int InOrderThread_Head(BiTree *h, BiTree t)
{
    (*h) = (BiTree)malloc(sizeof(BitNode));
    if((*h) == NULL)
    {
        return ERROR;
    }
 
    (*h)->rchild = *h;
    (*h)->rtag = Link;
 
    if(!t)      //如果为NULL
    {
        (*h)->lchild = *h;
        (*h)->ltag = Link;
    }
    else
    {
        pre = *h;
        (*h)->lchild = t;        //第一步
        (*h)->ltag = Link;
        InThreading(t);         //找到最后一个结点
        pre->rchild = *h;        //第四步
        pre->rtag = Thread;
        (*h)->rchild = pre;      //第二步
    }
}
 
int main(int argc, char **argv)
{
    BiTree t;
    BiTree temp;
 
    printf("请输入前序二叉树的内容:\n");
    CreateTree(&t);                 //建立二叉树
    InOrderThread_Head(&temp, t);       //加入头结点，并线索化
    printf("输出中序二叉树的内容:\n");
    InOrderThraverse_Thr(temp);
     
    printf("\n");
    return 0;
}

发件人: []（）

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-195333-1.html