第五章 树与二叉树

5.1树的基本概念

5.1.1树的定义

树是n(n\geqslant0)个结点的有限集。当n=0时，称为空树。在任意一棵非空树中应满足：

1. 有且仅有一个特定的称为根的结点 。
2. 当 n> 1时 , 其余结点可分为 m( m> 0) 个互不相交的有限集 T_{1}, T_{2}, \cdots , T_{m}，其中每个集合本身又是一棵树，并且称为根的子树。

显然，树的定义是==递归的==，即在树的定义中又用到了其自身，树是一种递归的数据结构。树作为一种==逻辑结构==，同时也是一种==分层结构==，具有以下两个特点，

1. 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
2. 树中所有结点都可以有零个或多个后继。

树适用于表示具有层次结构的数据。树中的某个结点(除根结点外)最多只和上一层的一个结点(即其父结点)有直接关系，根结点没有直接上层结点，因此在 n个结点的树中有 n-1条边。而树中每个结点与其下一层的零个或多个结点(即其孩子结点)都有直接关系。

5.1.2基本术语

1. 祖先、子孙、双亲、孩子、兄弟和堂兄弟。
   考虑结点K,从根A到结点K的唯一路径上的所有其他结点，称为结点K的祖先。如结点B是结点K的祖先，而K是B的子孙，结点B的子孙包括E,F,K,L。路径上最接近结点K的结点E称为K的双亲，而K为E的孩子。根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟，如结点K和结点L有相同的双亲E,即K和L为兄弟。双亲在同一层的结点互为堂兄弟，结点G与E,F,H,I,J互为堂兄弟。

2. 结点的度和树的度。
   树中一个结点的孩子个数称为该结点的度，==树中结点的最大度数称为树的度==。如结点B的度为2,结点D​的度为3,树的度为3。

3. 分支结点和叶结点。
   ==度大于0的结点称为分支结点(又称非终端结点)==;==度为0(没有孩子结点)的结点称为叶结点(又称终端结点)==。在分支结点中,每个结点的==分支数==就是该结点的度。

4. 结点的深度、高度和层次。
   结点的层次从树根开始定义，==根结点为第1层==，它的孩子为第2层，以此类推。==结点的深度就是结点所在的层次==。==树的高度(或深度)是树中结点的最大层数==。==结点的高度是以该结点为根的子树的高度。==

5. 有序树和无序树。
   树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树。

6. 路径和路径长度。
   两个结点之间的路径是由这两个路径之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。
   树中的分支是有向的，即从双亲指向孩子。所以树中的路径是从上向下的，同一双亲的两个孩子之间不存在路径。

7. 森林。
   森林是m(m\geq0)棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树。

5.1.3树的性质

树具有如下最基本的性质：

树中结点数和度数的关系的应用

1. 树的结点数n等于所有结点的度数之和加 1。

   结点的度是指该结点的孩子数量，每个结点与其每个孩子都由唯一的边相连，因此树所有结点的度数之和等于树中的边数之和。树中的结点(除根外)都有唯一的双亲，因此结点数n等于边数之和加 1,即所有结点的度数之和加 1。

2. 度为m 的树中第 i层上至多有 m^{i-1} 个结点(i\geqslant1)。
   第 1 层至多有 1 个结点 (即根结点),第 2 层至多有m个结点，第 3 层至多有m^{2}个结点，以此类推。使用数学归纳法可推出第i层至多有m^{i-1}个结点。

3. 高度为h 的 m 叉树至多有(m^h-1)/(m-1)个结点。
   当各层结点数达到最大时，树中至多有1+m+m^2+\cdots+m^{h-1}=(m^h-1)/(m-1)个结点。

指定结点数的三叉树的最小高度分析

4. 度为m、具有n个结点的树的最小高度h为\lceil\log_m(n(m-1)+1)\rceil。
   为使树的高度最小，在前h-1层中，每层的结点数都要达到最大，前h-1层最多有(m^{h-1}-1)/(m-1)个结点，前h 层最多有(m^h-1)/(m-1)个结点。因此(m^{h-1}-1)/(m-1)<n\leqslant (m^h-1)/(m-1),即h-1<\log_m(n(m-1)+1)\leqslant h,解得h_\min=\lceil\log_m(n(m-1)+1)\rceil。

5. 度为m、具有n个结点的树的最大高度h为n-m+1。
   由于树的度为m,因此至少有一个结点有m个孩子，它们处于同一层。为使树的高度最大，其他层可仅有一个结点，因此最大高度(层数)为n-m+1。由此，也可逆推出高度为h、度为m 的树至少有 h+m-1 个结点。

5.2二叉树的概念

5.2.1二叉树的定义及其主要特征

1.二叉树的定义

二叉树是一种特殊的树形结构，其特点是每个结点至多只有两棵子树(即二叉树中不存在度大于 2 的结点),并且二叉树的子树有左右之分，其次序不能任意颠倒。

与树相似，二叉树也以递归的形式定义。二叉树是n(n{\geq}0)个结点的有限集合：

1. 或者为空二叉树，即n=0。
2. 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

==二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。==二叉树的5种基本形态如图所示。

二叉树与度为2的有序树的区别:

1. 度为2的树至少有3个结点,而二叉树可以为空。
2. 度为 2 的有序树的孩子的左右次序是相对于另一个孩子而言的，若某个结点只有一个孩子，则这个孩子就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，即二叉树的结点次序不是相对于另一结点而言的，而是确定的。

2.几种特殊的二叉树

1. 满二叉树。一棵高度为h,且有 2^h-1 个结点的二叉树称为满二叉树，即二叉树中的每层都含有最多的结点，满二叉树的叶结点都集中在二叉树的最下一层，并且除叶结点之外的每个结点度数均为2。
   可以对满二叉树按层序编号：约定编号从根结点(根结点编号为1)起，自上而下，自左向右。这样，每个结点对应一个编号，对于编号为i 的结点，若有双亲，则其双亲为\left\lfloor {i/2} \right\rfloor , 若有左孩子，则左孩子为 2i; 若有右孩子，则右孩子为2i+1。

完全二叉树中结点数和叶结点数的关系

2. 完全二叉树。高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为 1\sim n的结点一一对应时，称为完全二叉树，其特点如下：

• 若i\leqslant\lfloor n/2\rfloor,则结点i为分支结点，否则为叶结点。可以看一下满二叉树的特性

• 叶结点只可能在层次最大的两层上出现。对于最大层次中的叶结点，都依次排列在该层最左边的位置上。

• 若有度为 1 的结点，则最多只可能有一个，且该结点只有左孩子而无右孩子。按层序编号后，一旦出现某结点(编号为i)为叶结点或只有左孩子，则编号大于i的结点均为叶结点。

• 若n为奇数，则每个分支结点都有左孩子和右孩子；若n为偶数，则编号最大的分支结点(编号为n/2)只有左孩子，没有右孩子，其余分支结点左、右孩子都有。

3. 二叉排序树。左子树上所有结点的关键字均小于根结点的关键字；右子树上所有结点的关键字均大于根结点的关键字；左子树和右子树又各是一棵二叉排序树。
4. 平衡二叉树。树中任意一个结点的左子树和右子树的高度之差的绝对值不超过 1。关于二又排序树和平衡二叉树的详细介绍，见 7.3 节。

正则k叉树树高和结点数的关系的应用

5. 正则二叉树。树中每个分支结点都有 2个孩子，即树中只有度为 0 或 2 的结点。

3.二叉树的性质

1. ==非空二叉树上的叶结点数等于度为2的结点数加1，即n_0=n_2+1。==
   证明：设度为 0,1 和 2 的结点个数分别为n_0,n_1和n_2,结点总数n=n_0+n_1+n_2。再看二叉树中的分支数，==除根结点外，其余结点都有一个分支进入==，设B为分支总数，则n=B+1。由于这些分支是由度为 1 或 2 的结点射出的，因此又有B=n_1+2n_2。于是得n_0+n_1+n_2=n_1+2n_2+1,则n_0=n_2+1。
2. 非空二叉树的第k层最多有2^{k-1}个结点(k\geqslant1)。
   第 1 层最多有2^{1-1}=1个结点(根),第 2 层最多有2^{2-1}=2个结点，以此类推，可以证明其为一个公比为 2 的等比数列2^{k-1}。
3. 高度为h的二叉树至多有2^h-1 个结点(h\geqslant1)。
   该性质利用性质 2 求前h项的和，即等比数列求和的结果。

注意性质 2和性质 3还可以拓展到m叉树的情况，即m叉树的第k层最多有m^{k-1}个结点，高度为 h 的 m 叉树至多有(2^h-1)/(m-1)个结点。

4. 对完全二叉树按从上到下、从左到右的顺序依次编号1,2,\cdots,n,则有以下关系：
   1. 若i\leqslant\lfloor n/2\rfloor,则结点i为分支结点，否则为叶结点，即最后一个分支结点的编号为[n/2]。
   2. 叶结点只可能在层次最大的两层上出现(若删除满二叉树中最底层、最右边的连续2个或以上的叶结点,则倒数第二层将会出现叶结点)。
   3. 若有度为1的结点,则只可能有一个,且该结点只有左孩子而无右孩子(度为1的分支结点只可能是最后一个分支结点,其结点编号为\lfloor n/2\rfloor)。
   4. 按层序编号后，一旦出现某结点(如结点i)为叶结点或只有左孩子的情况，则编号大于i的结点均为叶结点(与结论1和结论3是相通的)。
   5. 若n为奇数，则每个分支结点都有左、右孩子；若n为偶数，则编号最大的分支结点(编号为n/2)只有左孩子，没有右孩子，其余分支结点都有左、右孩子。
   6. 当i>1时，结点i的双亲结点的编号为\lfloor i/2\rfloor。
   7. 若结点i有左、右孩子，则左孩子编号为2i,右孩子编号为2i+1。
   8. 结点i所在层次(深度)为\lfloor\log_2i\rfloor+1
5. 具有n个(n>0)结点的完全二叉树的高度为\left\lceil \log_2(n+1) \right\rceil 或\lfloor \log_2n \rfloor+1。
   设高度为h,根据性质 3 和完全二叉树的定义有2^{h- 1}- 1< n\leqslant 2^h- 1 或者 2^{h- 1}\leqslant n< 2^h得2^{h-1}<n+1\leqslant2^h,即h-1<\log_2(n+1)\leqslant h,因为h为正整数，所以h=\lceil\log_2(n+1)\rceil,或者得h-1\leqslant\log_2n<h,所以h=\lfloor\log_2n\rfloor+1。

5.2.2二叉树的存储结构

1.顺序存储

二叉树的顺序存储是指用一组连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i 的结点元素存储在一维数组下标为i-1 的分量中。

依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映结点之间的逻辑关系，这样既能最大可能地节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。

特定条件下二叉树树形及占用存储空间的分析

但对于一般的二叉树，为了让数组下标能反映二叉树中结点之间的逻辑关系，只能添加一些并不存在的空结点，让其每个结点与完全二叉树上的结点相对照，再存储到一维数组的相应分量中。然而，在最坏情况下，一个高度为h且只有h个结点的单支树却需要占据近2^h-1个存储单元。二叉树的顺序存储结构如图所示，其中 0 表示并不存在的空结点。

建议从下标1开始存储树中的结点，保证下标和编号一致

2.链式存储结构

由于顺序存储的空间利用率较低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树中的每个结点。在二叉树中，结点结构通常包括若干数据域和若干指针域，二叉链表至少包含 3 个域：数据域data、左指针域 Ichild 和右指针域 rchild,如图所示。

图所示为一棵二叉树及其对应的二叉链表。而实际上在不同的应用中，还可以增加某些指针域，如增加指向父结点的指针后，变为三叉链表的存储结构。

二叉树的链式存储结构描述如下：

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

使用不同的存储结构时，实现二叉树操作的算法也会不同，因此要根据实际应用场合(二叉树的形态和需要进行的运算）来选择合适的存储结构。

容易验证，在含有n个结点的二叉链表中，含有n+1个空链域（重要结论，选择题）。(每个结点都会被一个指针指向，除了根节点)2n-(n-1)=n+1

5.3二叉树的遍历和线索二叉树

5.3.1二叉树的遍历

二叉树的遍历是指按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。由于二叉树是一种非线性结构，每个结点都可能有两棵子树，因此需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，进而便于遍历。

二叉树遍历方式的分析

(算法题)二叉树遍历的相关应用

由二叉树的递归定义可知，遍历一棵二叉树便要决定对根结点 N、左子树 L 和右子树 R 的访问顺序。按照先遍历左子树再遍历右子树的原则，常见的遍历次序有==先序(NLR)、中序(LNR)和后序 (LRN)==三种遍历算法，其中“序”指的是根结点在何时被访问。

1.先序遍历(PreOrder)

若二叉树为空,则什么也不做;否则,

1. 访问根结点;

2. 先序遍历左子树;

3. 先序遍历右子树。图中的虚线表示对该二叉树进行先序遍历的路径,得到先序遍历序列为124635。

对应的递归算法如下：

void PreOrder(BiTree T){
    if(T!=NULL){
		visit(T);//访问根结点
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

2.中序遍历(InOrder)

若二叉树为空，则什么也不能做；否则，

1. 中序遍历左子树;

2. 访问根结点;

3. 中序遍历右子树。

图中的虚线表示对该二叉树进行中序遍历的路径，得到中序遍历序列为264135

对应的递归算法：

void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }  
}

3.后序遍历(PostOrder)

若二叉树为空,则什么也不做;否则,

1. 后序遍历左子树;

2. 后序遍历右子树；

3. 访问根结点。

图二叉树的后序遍历

对应的递归算法如下：

void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);//访问根结点
    }
}

上述三种遍历算法中，递归遍历左、右子树的顺序都是固定的，只是访问根结点的顺序不同。不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，所以时间复杂度都是O(n)。在递归遍历中，递归工作栈的栈深恰好为树的深度，所以在最坏情况下，二叉树是有n个结点且深度为n的单支树，遍历算法的空间复杂度为O(n)。

4.递归算法和非递归算法的转换

在上节介绍的三种遍历算法中，暂时抹去和递归无关的 visit()语句，则 3 个遍历算法完全相同，因此，从递归执行过程的角度看先序、中序和后序遍历也是完全相同的。

图中用带箭头的虚线表示了这三种遍历算法的递归执行过程。其中，向下的箭头表示更深一层的递归调用，向上的箭头表示从递归调用退出返回；虚线旁的三角形、圆形和方形内的字符分别表示在先序、中序和后序遍历的过程中访问根结点时输出的信息。例如，由于中序遍历中访问结点是在遍历左子树之后、遍历右子树之前讲行的，则带圆形的字符标在向左涕归返回和向右递归调用之间。由此，只要沿虚线从 1 出发到 2 结束，将沿途所见的三角形(或圆形或方形)内的字符记下，便得到遍历二叉树的先序(或中序或后序)序列。例如，在图5中，沿虚线游走可以分别得到先序序列为ABDEC、中序序列为DBEAC、后序序列为DEBCA。

借助栈的思路，我们来分析中序遍历的访问过程：

1.沿着根的左孩子，依次入栈，直到左孩子为空，说明已找到可以输出的结点，此时栈内元素依次为ABD。2.栈顶元素出栈并访问：若其右孩子为空，继续执行2;若其右孩子不空，将右子树转执行1。栈顶D出栈并访问，它是中序序列的第一个结点；D右孩子为空，栈顶B出栈并访问；B右孩子不空，将其右孩子E入栈，E左孩子为空，栈顶E出栈并访问；E右孩子为空， 栈顶A 出栈并访问：A 右孩子不空，将其右孩子C 入栈，C 左孩子为空，栈顶C 出栈并访问。由此得到中序序列DBEAC。可根据上述分析画出遍历过程的出入栈示意图。

根据分析可以写出中序遍历的非递归算法如下：

void InOrder2(BiTree T){
	InitStack(S);
    BiTree p=T;
    while(p||!IsEmpty(S)){
        if(P){
            Push(S,p);
            p=p->lchild;
        }else{
            Pop(S,p);
            visit(p);
            p=p->rchild;
        }
    }       
}

先序遍历和中序遍历的基本思想是类似的，只需要把访问结点操作放在入栈操作的前面。

先序遍历的非递归算法如下：

void PreInOrder2(BiTree T){
	InitStack(S);
    BiTree p=T;
    while(p||!IsEmpty(S)){
        if(P){
            visit(p);
            Push(S,p);
            p=p->lchild;
        }else{
            Pop(S,p);
            p=p->rchild;
        }
    }       
}

后序遍历的非递归实现是三种遍历方法中最难的。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。

后序非递归遍历算法的思路分析：从根结点开始，将其入栈，然后沿其左子树一直往下搜索， 直到搜索到没有左孩子的结点，但是此时不能出栈并访问，因为若其有右子树，则还需按相同的规则对其右子树进行处理。直至上述操作进行不下去，若栈顶元素想要出栈被访问，要么右子树为空，要么右子树刚被访问完(此时左子树早已访问完),这样就保证了正确的访问顺序。

后序遍历的非递归算法：

void PostOrder2(BiTree T){
	InitStack(S);
    BiTNode *p=T; 
    //标志位，标志着上一个出栈的元素，用来查看右子树是否已被访问完
    BiTNode *r=NULL;
    while(p||!IsEmpty(S)){
        if(P){
            Push(S,p);
            p=p->lchild;
        }else{
            //向右
            //读栈顶元素
            GetTop(S,p);
            if(p->rchild&&p->rchild!=r){
                p=p->rchild;
            }else{      
                Pop(S,p);
                visit(p);
                r=p;
                p=NULL;  
            }
        }
    }       
}

按后序非递归算法遍历图(a)中的二叉树，当访问到E时，A,B,D都已入过栈，对于后序非递归遍历，当一个结点的左右子树都被访问后才会出栈，图中D已出栈，此时栈内还有A和B, 这是E的全部祖先。实际上，访问一个结点p时，栈中结点恰好是结点p的所有祖先，从栈底到栈顶结点再加上结点p,刚好构成从根结点到结点p的一条路径。在很多算法设计中都可以利用这一思路来求解，如求根到某结点的路径、求两个结点的最近公共祖先等。

5.层次遍历

图所示为二叉树的层次遍历，即按照箭头所指方向，按照 1,2,3,4 的层次顺序，自上而下，从左至右，对二叉树中的各个结点进行逐层访问。

进行层次遍历，需要借助一个队列。层次遍历的思想如下：1.首先将二叉树的根结点入队。2.若队列非空，则队头结点出队，访问该结点，若它有左孩子，则将其左孩子入队；若它有右孩子，则将其右孩子入队。3重复2步，直至队列为空。

二叉树的层次遍历算法如下：

void LevelOrder(BiTree T){
    InitQueue(Q);
    BiTree p;
    //根结点入队
    EnQueue(Q,T);
    while(!IsEmpty(Q)){
		//出队
        DeQueue(Q,p);
        visit(p);
        if(p->lchild!=NULL){
			EnQueue(Q,p->lchild);
        }
        if(p->rchild!=NULL){
            EnQueue(Q,p->NULL);
        }
    }
    
}

遍历是二叉树各种操作的基础，例如对于一棵给定二叉树求结点的双亲、求结点的孩子、 求二叉树的深度、求叶结点个数、判断两棵二叉树是否相同等。所有这些操作都是在遍历的过程中进行的，因此必须掌握二叉树的各种遍历过程，并能灵活运用以解决各种问题。

6.由遍历序列构造二叉树

先序序列对应的不同二叉树的分析

对于一棵给定的二叉树，其先序序列、中序序列、后序序列和层序序列都是确定的。然而， 只给出四种遍历序列中的任意一种，却无法唯一地确定一棵二叉树。若已知中序序列，再给出其他三种遍历序列中的任意一种，就可以唯一地确定一棵二叉树。

1. 由先序序列和中序序列构造二叉树

先序序列和中序序列相同时确定的二叉树

由先序序列和中序序列构造一棵二叉树

在先序序列中，第一个结点一定是二叉树的根结点；而在中序遍历中，根结点必然将中序序列分割成两个子序列，前一个子序列是根的左子树的中序序列，后一个子序列是根的右子树的中序序列。左子树的中序序列和先序序列的长度是相等的，右子树的中序序列和先序序列的长度是相等的。根据这两个子序列，可以在先序序列中找到左子树的先序序列和右子树的先序序列，如图所示。如此说归地分解下夫，便能唯一地确定这棵二叉树。

例如，求先序序列(ABCDEFGHI)和中序序列(BCAEDGHFI)所确定的二叉树。首先，由先序序列可知A为二叉树的根结点。中序序列中A之前的BC为左子树的中序序列，EDGHFI为右子树的中序序列。然后，由先序序列可知B是左子树的根结点，D是右子树的根结点。以此类推，就能将剩下的结点继续分解下去，最后得到的二叉树如图(c)所示。

2. 由后序序列和中序序列构造二叉树

由后序序列和树形构造一棵二叉树

同理，由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树。因为后序序列的最后一个结点就如同先序序列的第一个结点，可以将中序序列分割成两个子序列，如图所示，然后用类似的方法递归地进行分解，进而唯一确定这颗二叉树。

3. 由层序序列和中序序列构造二叉树

在层序遍历中，第一个结点一定是二叉树的根结点，这样就将中序序列分割成了左子树的中序序列和右子树的中序序列。若存在左子树，则层序序列的第二个结点一定是左子树的根，可进一步划分左子树；若存在右子树，则中序序列中紧接着的下一个结点一定是右子树的根，可进一步划分右子树，如图所示。采用这种方法继续分解，就能唯一确定这棵二叉树。

需要注意的是，先序序列、后序序列和层序序列的两两组合，无法唯一确定一棵二叉树。例如，图所示的两棵二叉树的先序序列都为AB,后序序列都为BA,层序序列都为AB。

5.3.2线索二叉树

1.线索二叉树的基本概念

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

后序线索二叉树的定义

传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。前面提到，在含n个结点的二叉树中，有n+1个空指针。这是因为每个叶结点都有 2 个空指针，每个度为 1的结点都有 1 个空指针，空指针总数为2n_0+n_1,又n_0=n_2+1,所以空指针总数为n_0+n_1+n_2+1=n+1。由此设想能否利用这些空指针来存放指向其前驱或后继的指针？这样就可以像遍历单链表那样方便地遍历二叉树。引入线索二叉树正是为了加快查找结点前驱和后继的速度。

规定：若无左子树，令 lchild 指向其前驱结点；若无右子树，令 rchild 指向其后继结点。如图所示，还需增加两个标志域，以标识指针域指向左(右)孩子或前驱(后继)。

其中，标志域的含义如下：

\begin{aligned}&\text{1tag}=\begin{cases}0,&\quad\text{1child域指示结点的左孩子}\\1,&\quad\text{1child域指示结点的前驱}\end{cases}\\&\text{rtag}=\begin{cases}0,&\quad\text{rchild域指示结点的右孩子}\\1,&\quad\text{rchild域指示结点的后继}\end{cases}\end{aligned}

线索二叉树的存储结构：

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

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

2.中序线索二叉树的构造

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

中序线索二叉树中线索的指向

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

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

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 CreateThread(ThreadTree T){
    ThreadTree pre=NULL;
    if(T!=NULL){
        //线索化非空二叉树
		InThread(T,pre);
        //处理最后一个结点
        pre->rchild=NULL;
        pre->rtag=1;
    }
    
}

为了方便，可以在二叉树的线索链表上也添加一个头结点，令其lchild 域的指针指向二叉树的根结点，其 rchila 域的指针指向中序遍历时访问的最后一个结点；令二叉树中序序列中的第一个结点的 lchild 域指针和最后一个结点的 rchild 域指针均指向头结点。这好比为二叉树建立了一个双向线索链表，方便从前往后或从后往前对线索二叉树进行遍历，如图所示。

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 
        //若 rtag=1 则直接返回后继线索
        return p->rchild; 
}

如何求最后一个结点以及结点p（若有左子树，则为左子树的最优结点）的前驱？

ThreadNode *Lastnode(ThreadNode *p){
	while(p->rtag==0)
        p=p->rchild; //最右侧结点（不一定是叶结点）
	return p;
}

ThreadNode *Prenode(ThreadNode *p){
	if(p->ltag==0)
        return Lastnode(p->lchild); 
    else 
        return p->lchild; 
}

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

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

4.先序线索二叉树和后序线索二叉树

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

以图的二叉树为例给出手动求先序线索二叉树的过程：先序序列为ABCDF,然后依次判断每个结点的左右链域，若为空，则将其改造为线索。结点A,B均有左右孩子；结点C无左孩子，将左链域指向前驱B,无右孩子，将右链域指向后继D;结点D无左孩子，将左链域指向前驱C,无右孩子，将右链域指向后继F;结点F无左孩子，将左链域指向前驱D,无右孩子， 也无后继，所以置空，得到的先序线索二叉树如图(b)所示。求后序线索二叉树的过程：后序序列为CDBFA,结点C无左孩子，也无前驱，所以置空，无右孩子，将右链域指向后继D:结点D无左孩子，将左链域指向前驱C,无右孩子，将右链域指向后继B;结点F无左孩子，将左链域指向前驱B,无右孩子，将右链域指向后继A,得到的后序线索二叉树如图(c)所示。

如何在先序线索二叉树中找结点的后继？若有左孩子，则左孩子就是其后继；若无左孩子但有右孩子，则右孩子就是其后继；若为叶结点，则右链域直接指示了结点的后继。

后序线索二叉树中线索的指向

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

1. 若结点 x 是二叉树的根，则其后继为空；
2. 若结点 x 是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲；
3. 若结点 x 是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点。图(c)中找结点B的后继无法通过链域找到，可见在后序线索二叉树上找后继时需知道结点双亲，即需采用带标志域的三叉链表作为存储结构。

5.4树、森林

5.4.1树的存储结构

树的存储方式有多种，既可采用顺序存储结构，又可采用链式存储结构，但无论采用何种存储方式，都要求能唯一地反映树中各结点之间的逻辑关系，这里介绍 3 种常用的存储结构。

1.双亲表示法

这种存储结构采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。

存储结构如下：

#define MAX_TREE_SIZE 100
typedef struct{
    ElemType data;
    int parent;
}PTNode;
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    //结点数
    int n;
}PTree;

双亲法利用了每个结点（根结点除外）只有唯一双亲的特性，可以很快地得到每个结点的双亲结点，但求结点的孩子时则需要遍历整个结构。

区别树的顺序存储结构与二叉树的顺序存储结构。在树的顺序存储结构中，数组下标代表结点的编号，下标中所存的内容指示了结点之间的关系。而在二叉树的顺序存储结构中，数组下标既代表了结点的编号，又指示了二叉树中各结点之间的关系。当然，二叉树属于树，因此二叉树也可用树的存储结构来存储，但树却不都能用二叉树的存储结构来存储。

2.孩子表示法

孩子表示法是将每个结点的孩子结点视为一个线性表，且以单链表作为存储结构，则n个结点就有n个孩子链表(叶结点的孩子链表为空表)。而n个头指针又组成一个线性表，为便于查找，可采用顺序存储结构。图(a)是上一张图(a)中的树的孩子表示法。

与双亲表示法相反，孩子表示法寻找孩子的操作非常方便，而寻找双亲的操作则需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。

3.孩子兄弟表示法

孩子兄弟表示法又称二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针，以及指向结点下一个兄弟结点的指针(沿此域可以找到结点的所有兄弟结点),如图(b)所示。

孩子兄弟表示法的存储结构描述如下：

typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;

孩子兄弟表示法比较灵活，其最大的优点是可以方便地实现树转换为二叉树的操作，易于查找结点的孩子等，但缺点是从当前结点查找其双亲结点比较麻烦。若为每个结点增设一个 parent 域指向其父结点，则查找结点的父结点也很方便。

5.4.2树、森林与二叉树的转换

二叉树和树都可以用二叉链表作为存储结构。从物理结构上看，树的孩子兄弟表示法与二叉表表示法是相同的，因此可以用同一存储结构的不同解释，将一棵树转换为二叉树。

1.树转换为二叉树

树和二叉树的转换及相关性质的推理

树转换为二叉树的规则：每个结点的左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则又称“左孩子右兄弟”。由于根结点没有兄弟，因此树转换得到的二叉树没有右子树，如图 所示，

树转换为二叉树的画法：

1. 在兄弟结点之间加一连线；

2. 对每个结点,只保留它与第一个孩子的连线,而与其他孩子的连线全部抹掉;

3. 以树根为轴心,顺时针旋转45°。

2.森林转换为二叉树

森林和二叉树的转换及相关性质的推理

将森林转换为二叉树的规则与树类似。先将森林中的每棵树转换为二叉树，由于任意一棵树对应的二叉树的右子树必空，若把森林中第二棵树根视为第一棵树根的右兄弟，即将第二棵树对应的二叉树当作第一棵二叉树根的右子树，将第三棵树对应的二叉树当作第二棵二叉树根的右子树，以此类推，就可以将森林转换为二叉树。

森林转换为二叉树的画法：

1. 将森林中的每棵树转换成相应的二叉树；

2. 每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线；

3. 以第一棵树的根为轴心顺时针旋转45°。

3.二叉树转换为森林

由遍历序列构造一棵二叉树并转换为对应的森林

二叉树转换为森林的规则：若二叉树非空，则二叉树的根及其左子树为第一棵树的二叉树形式，所以将根的右链断开。二叉树根的右子树又可视为一个由除第一棵树外的森林转换后的二叉、树，应用同样的方法，直到最后只剩一棵没有右子树的二叉树为止，最后将每棵二叉树依次转换成树，就得到了原森林，如图所示。二叉树转换为树或森林是唯一的。

5.4.3树和森林的遍历

1.树的遍历

树与二叉树遍历方法的对应关系

树的遍历是指用某种方式访问树中的每个结点,且仅访问一次。主要有两种方式:

1. 先根遍历。若树非空,则按如下规则遍历:

   • 先访问根结点。
   • 再依次遍历根结点的每棵子树,遍历子树时仍遵循先根后子树的规则。

   其遍历序列与这棵树相应二叉树的先序序列相同。

2. 后根遍历。若树非空,则按如下规则遍历:

   • 先依次遍历根结点的每棵子树,遍历子树时仍遵循先子树后根的规则。

   • 再访问根结点。

   其遍历序列与这棵树相应二叉树的中序序列相同。

   另外，树也有层次遍历，与二叉树的层次遍历思想基本相同，即按层序依次访问各结点

2.森林的遍历

按照森林和树相互递归的定义，可得到森林的两种遍历方法。

1. 先序遍历森林。若森林为非空，则按如下规则遍历：

   • 访问森林中第一棵树的根结点。
   • 先序遍历第一棵树中根结点的子树森林。
   • 先序遍历除去第一棵树之后剩余的树构成的森林。

2. 中序遍历森林。森林为非空时，按如下规则遍历：

   • 中序遍历森林中第一棵树的根结点的子树森林。
   • 访问第一棵树的根结点。
   • 中序遍历除去第一棵树之后剩余的树构成的森林。

森林与二叉树遍历方法的对应关系

当森林转换成二叉树时，其第一棵树的子树森林转换成左子树，剩余树的森林转换成右子树灯知森林的先序和中序遍历即为其对应二叉树的先序和中序遍历。树和森林的遍历与二叉树的遍历关系见表。表中树和森林的遍历与二叉树和森林的遍历与二叉树遍历的对应关系

树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

部分教材也将森林的中序遍历称为后序遍历，称中序遍历是相对其二叉树而言的，称后序遍历是因为根确实是最后才访问的，若遇到这两种称谓，则可理解为同一种遍历方法。

5.5树与二叉树的应用

5.5.1哈夫曼树和哈夫曼编码

1.哈夫曼树的定义

在介绍哈夫曼树之前，先介绍几个相关的概念：

从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。

路径上的分支数目称为路径长度。

在许多应用中，树中结点常常被赋子一个表示某种意义的数值，称为该结点的权。

从树的根到一个结点的路径长度与该结点上权值的乘积，称为该结点的带权路径长度。

树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为

式中，w_i是第 i 个叶结点所带的权值，l_i是该叶结点到根结点的路径长度。

在含有n个带权叶结点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为哈夫曼树， 也称最优二叉树。例如，图中的 3 棵二叉树都有 4 个叶结点a,b,c,d,分别带权 7,5,2,4,它们的带权路径长度分别为

(a) WPL=7\times2+5\times2+2\times2+4\times2=36。

(b) WPL=4\times2+7\times3+5\times3+2\times1=46。

(c) WPL=7\times1+5\times2+2\times3+4\times3=35。
其中，图(c)树的 WPL 最小。可以验证，它恰好为哈夫曼树。

2.哈夫曼树的构造

给定n个权值分别为w_1,w_2,\cdots,w_n的结点，构造哈夫曼树的算法描述如下：

1. 将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。

分析哈夫曼树的路径上权值序列的合法性

2. 构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
3. 从F中删除刚才选出的两棵树，同时将新得到的树加入F 中。
4. 重复步骤2)和 3),直至F中只剩下一棵树为止。

哈夫曼树的性质

从上述构造过程中可以看出哈夫曼树具有如下特点：

1. 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。

2. 构造过程中共新建了n-1 个结点(双分支结点),因此哈夫曼树的结点总数为 2n-1。

3. 每次构造都选择 2 棵树作为新结点的孩子，因此哈夫曼树中不存在度为 1 的结点。
   例如，权值{7,5,2,4}的哈夫曼树的构造过程如图所示。

   

3.哈夫曼编码

在数据通信中，若对每个字符用相等长度的二讲制位表示，称这种编码方式为固定长度编码。若允许对不同字符用不等长的二进制位表示，则这种编码方式称为可变长度编码。可变长度编码比固定长度编码要好得多，其特点是对频率高的字符赋以短编码，而对频率较低的字符则赋以较长一些的编码，从而可以使字符的平均编码长度减短，起到压缩数据的效果。

根据哈夫曼编码对编码序列进行译码

若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。举例：设计字符 A,B 和 C 对应的编码0，10 和 110 是前缀编码。对前缀编码的解码很简单，因为没有一个编码是其他编码的前缀。所以识别出第一个编码，将它翻译为原字符，再对剩余的码串执行同样的解码操作。例如，码串 0010110 可被唯一地翻译为A,A,B和 C。另举反例：若再将字符 D 的编码设计为 11， 此时 11 是 110 的前缀，则上述码串的后三位就无法唯一翻译。

哈夫曼树的构造及相关的分析

前缀编码的分析及应用

可以利用二叉树来设计二进制前缀编码。假设为 A,B,C,D 四个字符设计前缀编码，可以用图所示的二叉树来表示，4 个叶结点分别表示 4 个字符，且约定左分支表示 0,右分支表示1,从根到叶结点的路径上用分支标记组成的序列作为该叶结点字符的编码，可以证明如此得到

哈夫曼编码和定长编码的差异

哈夫曼编码是一种非常有效的数据压缩编码。由哈夫曼树得到哈夫曼编码是很自然的过程。首先，将每个字符当作一个独立的结点，其权值为它出现的频度(或次数),构造出对应的哈夫曼树。然后，将从根到叶结点的路径上分支标记的字符串作为该字符的编码。图所示为一个由哈夫曼树构造哈夫曼编码的示例，矩形方块表示字符及其出现的次数。

这棵哈夫曼树的 WPL 为
{\mathrm{WPL}=1\times45+3\times(13+12+16)+4\times(5+9)=224}
此处的 WPL 可视为该字符串最终编码得到二进制编码的长度，共 224 位。若采用 3 位固定长度编码，则得到的二进制编码长度为300 位 (45+13+12+16+5+9)*3=300，因此哈夫曼编码共压缩了 25%的数据。利用哈夫曼树可以设计出总长度最短的二进制前缀编码。

左分支和右分支究竟是表示0还是表示1没有明确规定，因此构造出的哈夫曼树并不唯一， 但各哈夫曼树的带权路径长度 WPL 相同且为最优。此外，如有若干权值相同的结点，则构造出的哈夫曼树更可能不同，但 WPL 必然相同且为最优。

5.5.2并查集

1.并查集的概念

并查集是一种简单的集合表示,它支持以下3种操作:

1. Initial(S):将集合S中的每个元素都初始化为只有一个单元素的子集合。

2. Union(S,Root1,Root2):把集合S中的子集合Root2并入子集合Root1。要求Root1和Root2互不相交，否则不执行合并。

3. Find(S,x):查找集合s中单元素x所在的子集合，并返回该子集合的根结点。

2.并查集的存储结构

通常用树的双亲表示作为并查集的存储结构，每个子集合以一棵树表示。所有表示子集合的树，构成表示全集合的森林，存放在双亲表示数组内。通常用数组元素的下标代表元素名，用根结点的下标代表子集合名，根结点的双亲域为负数(可设置为该子集合元素数量的相反数)。

例如，若设有一个全集合为S=\{0,1,2,3,4,5,6,7,8,9\},初始化时每个元素自成一个单元素子集合，每个子集合的数组值为-1,如图所示。

经过一段时间的计算后，这些子集合合并为3个更大的子集合，即S_{\mathrm{l}}=\{0,6,7,8\},S_{2}=\{1,4,9\},S_3=\{2,3,5\},此时并查集的树形和存储结构如图所示。

为了得到两个子集合的并，只需将其中一个子集合根结点的双亲指针指向另一个集合的根结点。因此，S_1\cup S_2可以具有如图所示的表示。

在采用树的双亲指针数组表示作为并查集的存储表示时，集合元素的编号从0到SIZE-1其中 SIZE 是最大元素的个数。

3.并查集的基本实现

并查集的结构定义如下：

#define SIZE 100
int UFSets[SIZE];

并查集主要运算的实现：

1. 并查集的初始化操作

void Initial(int S[]){
    for(int i=0;i<SIZE;i++){
        s[i]=-1;
    }
}

2. 并查集的Find操作

在并查集S中查找并返回包含元素x的树的根。

int Find(int S[],int x){
    //寻找x的根，指向双亲结点
    while(S[x]>0){
        x=S[x];
    }
    return x;
}

判断两个元素是否属于同一集合，只需要分别找到它们的根，再比较根是否相同即可。

3. 并查集的Union操作

求两个不相交子集和的并集，若将两个元素所在的集合合并为一个集合，则需要先找到两个元素的根，再令一颗子集树的根指向另一颗子集树的根。

void Union(int S[],int Root1,int Root2){
    if(Root1==Root2){
        return;
    }
    //根Root2指向根Root1
    S[Root2]=Root1;
}

Find操作和Union操作的时间复杂度分别为O(d)和O(1),其中d为树的深度。

4.并查集实现的优化

在极端情况下，n 个元素构成的集合树的深度为n,则 Find 操作的最坏时间复杂度为O(n)。改进的办法是：在做 Union 操作之前，首先判别子集中的成员数量，然后令成员少的根指向成员多的根，即把==小树合并到大树==，为此==可令根结点的绝对值保存集合树中的成员数量==（注意是负数，绝对值等于所有结点的数目，包括根结点）。

1. 改进的 Union 操作

void Union(int S[],int Root1,int Root2){
    if(Root1==Root2) return;
    //Root2结点数更少，因为是负数
    if(S[Root2]>S[Root1]){
        //累加集合树的结点数
        S[Root1]+=S[Root2];
        S[Root2]=Root1;
    }else{
        S[Root2]+=S[Root1];
        S[Root1]=Root2;
    }
}

采用这种方法构造得到的集合树，其深度不超过\lfloor\log_2n\rfloor+1。

随着子集逐对合并，集合树的深度越来越大，为了进一步减少确定元素所在集合的时间，还可进一步对上述 Find 操作进行优化，当所查元素 x 不在树的第二层时，在算法中增加一个“压缩路径”的功能，即将从根到元素 x 路径上的所有元素都变成根的孩子。

2. 改进的 Find 操作

int find(int S[],int x){
    int root=x;
    //循环找到根
    while(S[root]>=0){
        root=S[root];
    }
    //压缩路径
    while(x!=root){
        int t=S[x];
        S[x]=root;
        x=t;
    }
    return root;
}

通过Find操作的“压缩路径”优化后，可使集合树的深度不超过O(a(n))，其中a(n)是一个增长极其缓慢的函数，对于常见的正整数n，通常a(n)<=4。