文章目录

二叉树

考纲内容

复习提示

1.线索二叉树

1.1线索二叉树的基本概念

1.2中序线索二叉树的构造

1.3中序线索二叉树的遍历

1.4先序线索二叉树和后序线索二叉树

知识回顾

---

二叉树

考纲内容

（一）树的基本概念
（二）二叉树
           二叉树的定义及其主要特征；二叉树的顺序存储结构和链式存储结构；
           二叉树的遍历；线索二叉树的基本概念和构造
（三）树、森林
           树的存储结构；森林与二叉树的转换；树和森林的遍历
（四）树与二叉树的应用
           哈夫曼(Huffman)树和哈夫曼编码；并查集及其应用

复习提示

本章内容多以选择题或综合题的形式考查，但统考也会出涉及树遍历相关的算法题。树和二叉树的性质、遍历操作、转换、存储结构和操作特性等，满二叉树、完全二叉树、线索二叉树、哈夫曼树的定义和性质，都是选择题必然会涉及的内容。

1.线索二叉树

1.1线索二叉树的基本概念

遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点(第一个和最后一个除外)都有一个直接前驱和直接后继。

【命题追踪——后序线索二叉树的定义】

传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。前面提到，在含n个结点的二叉树中，有n+1个空指针。这是因为每个叶结点都有2个空指针，每个度为1的结点都有1个空指针,空指针总数为2n0+n1,又n0=n2+1,所以空指针总数为n0+n1+n2+1=n+1（n0、n1、n2分别表示度为0、1、2的结点个数）

由此设想能否利用这些空指针来存放指向其前驱或后继的指针?这样就可以像遍历单链表那样方便地遍历二叉树。

引入线索二叉树正是为了加快查找结点前驱和后继的速度。
规定:若无左子树，令 lchild指向其前驱结点；若无右子树,令 rchild 指向其后继结点。

如图 5.17所示，还需增加两个标志域，以标识指针域指向左(右)孩子或前驱(后继)。

线索二叉树的存储结构描述如下:

typedef struct ThreadNode{
    ElemType data;                      //数据元素
    struct ThreadNode *lchild,*rchild;  //左、右孩子指针
    int ltag,rtag;                      //左、右线索标志
}ThreadNode,*ThreadTree;

以这种结点结构构成的二叉链表作为二叉树的存储结构，称为线索链表，其中指向结点前驱和后继的指针称为线索。加上线索的二叉树称为线索二叉树。

1.2中序线索二叉树的构造

二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树。

【命题追踪——中序线索二叉树中线索的指向】

以中序线索二叉树的建立为例。附设指针 pre 指向刚刚访问过的结点，指针p指向正在访问的结点，即 pre 指向p的前驱。在中序遍历的过程中，检査p的左指针是否为空，若为空就将它指向 pre；检査 pre 的右指针是否为空，若为空就将它指向p，如图 5.18 所示。

通过中序遍历对二叉树线索化的递归算法如下：

void InThread(ThreadTree &p,ThreadTree &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 CreateInThread(ThreadTree T){
    ThreadTree pre=NULL;
    if(T!=NULL){            //非空二叉树，线索化
        InThread(T pre);    //线索化二叉树
        pre->rchild=NULL;   //处理遍历的最后一个结点
        pre->rtag=l;
    }
}

为了方便，可以在二叉树的线索链表上也添加一个头结点，令其lchild域的指针指向二叉树的根结点，其 rchild 域的指针指向中序遍历时访问的最后一个结点；

令二叉树中序序列中的第一个结点的 lchild域指针和最后一个结点的 rchild 域指针均指向头结点。

这好比为二叉树建立了一个双向线索链表，方便从前往后或从后往前对线索二叉树进行遍历，如图 5.19 所示。

1.3中序线索二叉树的遍历

中序线索二叉树的结点中隐含了线索二叉树的前驱和后继信息。在对其进行遍历时，只要先找到序列中的第一个结点，然后依次找结点的后继，直至其后继为空。

在中序线索二叉树中找结点后继的规律是：若其右标志为“1”，则右链为线索，指示其后继，否则遍历右子树中第一个访问的结点(右子树中最左下的结点)为其后继。

不含头结点的线索二叉树的遍历算法如下。

1) 求中序线索二叉树的中序序列下的第一个结点:

ThreadNode *Firstnode(ThreadNode*p){
    while(p->ltag==0) p=p->lchild;     //最左下结点(不一定是叶结点)
    return p;
}

2) 求中序线索二叉树中结点p在中序序列下的后继:

ThreadNode *Nextnode(ThreadNode*p){
    if(p->rtag==0) return Firstnode(p->rchild);  //右子树中最左下结点
    else return p->rchild;      //若rtag==1则直接返回后继线索
}

请读者自行分析并完成求中序线索二叉树的最后一个结点和结点p前驱的运算

3) 利用上面两个算法，可写出不含头结点的中序线索二叉树的中序遍历的算法:

void Inorder(ThreadNode *T){
    for(ThreadNode *p=Firstnode(T); p!=NULL; p=Nextnode(p))
        visit(p);
}

1.4先序线索二叉树和后序线索二叉树

上面给出了建立中序线索二叉树的代码，建立先序线索二叉树和建立后序线索二叉树的代码类似，只需变动线索化改造的代码段与调用线索化左右子树递归函数的位置。

以图 5.20(a)的二叉树为例给出手动求先序线索二叉树的过程:

1. 先序序列为 ABCDF，然后依次判断每个结点的左右链域，若为空，则将其改造为线索。
2. 结点A,B均有左右孩子；结点C无左孩子，将左链域指向前驱 B，无右孩子，将右链域指向后继D；
3. 结点D无左孩子，将左链域指向前驱 C，无右孩子，将右链域指向后继F；
4. 结点F无左孩子，将左链域指向前驱 D，无右孩子，也无后继，所以置空；

得到的先序线索二叉树如图 5.20(b)所示。

求后序线索二叉树的过程:

1. 后序序列为 CDBEA，结点 C无左孩子，也无前驱，所以置空，无右孩子，将右链域指向后继 D；
2. 结点 D无左孩子，将左链域指向前驱C，无右孩子，将右链域指向后继B；
3. 结点F无左孩子，将左链域指向前驱 B，无右孩子，将右链域指向后继 A；

得到的后序线索二叉树如图 5.20(c)所示。

如何在先序线索二叉树中找结点的后继？

若有左孩子，则左孩子就是其后继；若无左孩子但有右孩子，则右孩子就是其后继；若为叶结点，则右链域直接指示了结点的后继。

【命题追踪——后序线索二叉树中线索的指向】

在后序线索二叉树中找结点的后继较为复杂，可分三种情况：

①若结点x是二叉树的根，则其后继为空;

②若结点x是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲；

③若结点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点。

图5.20(c)中找结点B的后继无法通过链域找到，可见在后序线索二叉树上找后继时需知道结点双亲，即需采用带标志域的三叉链表作为存储结构。

知识回顾