Chapter5 树与二叉树

\[ 树形结构 \begin{cases} 二叉树 \begin{cases} 概念：定义，存储结构\\ 操作 \begin{cases}三种遍历\\线索二叉树 \end{cases}\\ 应用 \begin{cases}并查集\\哈夫曼树 \end{cases}\\ \end{cases}\\ 树和树林 \begin{cases} 概念：定义，存储结构\\ 操作 \begin{cases}与二叉树的转换\\遍历 \end{cases}\\ 应用：并查集 \end{cases}\\ \end{cases}\\ \]

5.1 树的基本概念

5.1.1 树的定义

树是n(n>=0)个结点的有限集。n=0时称为空树。

任意一颗非空树满足：

有且只有一个根结点（树的根结点没有前驱，除根结点以外的所有结点有且只有一个前驱。树中的所有结点都可以有零个或多个后继）
n>1时，其余结点可分为m(m>0)个不相交的有限集T1,T2,...Tm，其中每个集合本身又是一棵树，并且称为根的子树

显然，树的定义是递归的，即树的定义中又用到了其自身。

5.1.2 基本术语

祖先、子孙、双亲、孩子、兄弟：从根结点到某结点唯一路径上的所有其他结点，称为该结点的（祖先）。而该结点是它所有祖先的（子孙）。相邻层间有连接的为双亲/孩子关系，有共同双亲的的两个结点称为兄弟
结点的度和树的度：某结点的孩子个数称为该结点的度
分支结点和叶结点：度大于0的结点称为分支结点；度为0（没有孩子的结点）的结点称为叶结点。
结点的深度、高度、层次：结点的层次从树根开始定义，根结点为第一层，它的孩子为第二层，以此类推。结点的深度就是结点所在的层次。树的高度（或深度）是树中结点的最大层次。结点的高度是以该结点为根的子树的高度。
有序树和无序树：树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树。
路径和路径长度：树中两个结点之间的（路径）是由这两个之间经过的结点序列构成的，（路径长度）是路径是所经过的边的个数。
森林：森林是m（m>=0）棵互不相交的树的集合。森林的概念与树的概念十分相近，以为只要把树的根结点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，森林就变成了树。

5.1.3 树的性质

树的结点数n = 所有结点的度数之和 + 1

除了根结点，所有结点都有唯一的双亲，因此一个度指向唯一的结点。再加上一个没被指向的根结点，就是树的所有结点
度为m的树中第i层上至多有m^(i-1)个结点(i>=1)

第一层至多有1个结点（即根结点），第二层至多有m个结点，第三层至多有m^{2个结点。以此类推，第i层至多有m}(i-1)个结点
高度为h的m叉树至多有(m^h-1)(m-1)个结点

当各层结点数达到最大时，树中至多有1+m+m^2+...+m(h-1)=(m^h-1)/(m-1)个结点
度为m、具有n个结点的树最小高度为[log_m_(n(m-1)+1)]下取整
度为m、具有n个结点的树的最大高度h为n-m+1

由于树的度为m，说明至少有一个结点有m个孩子，为使高度最大，其他层

5.2 二叉树的概念

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

二叉树的定义

二叉树的每个结点至多只有两棵子树（即不存在度大于2的结点），且二叉树是有序树。子树有左右之分，次序不能颠倒。

二叉树以递归的形式定义。是n(n>=0)个结点的有限集合，n=0时为空二叉树。左子树和右子树又分别是一颗二叉树。

二叉树与度为2的有序树的区别：度为2的树至少有3个结点（至少有1个结点度为2），而二叉树可以为空。
特殊二叉树

满二叉树：一棵高度为h，且有2^h-1个结点的二叉树称为满二叉树，即二叉树中每层都是满结点，除叶结点外每个结点度数均为2。

完全二叉树：高度为h、有n个结点的二叉树，当且仅当每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应。即每个结点都按顺序排列，不存在跨结点

二叉排序树：左子树上所有结点的关键字均小于根结点的关键字；右子树上的所有结点均大于根结点的关键字；而左子树和右子树又遵循这样的规则，各是一颗二叉排序树，是递归的。

平衡二叉树：树中任意一个结点的左子树和右子树的高度之差绝对值不超过1。
二叉树的性质

1 非空二叉树上的叶结点数等于度为2的结点数加1，n0 = n2 + 1。证：n = n0 + n1 + n2，除根结点外，每个结点都有一个入度，设X为总入度，则n = X + 1。由于这些入度是由度为1或2的结点构成的，故有X = n1 + 2n2，于是有n0 + n1 + n2 = n1 + 2n2 + 1。可推出

2 非空二叉树的第k层最多有2^(k-1)个结点，想象图形即可得，每层2的次方增加。

3 高度为h的二叉树至多有2^h - 1 个结点（满二叉树）（等比数列求和）

4 对完全二叉树按上到下，从左到右的顺序依次编号1，2，...，n。有关系如

5 具有n(n>0)结点的完全二叉树的高度为上取整[log2(n+1)] 或下取整[log2n] + 1（可由性质3推导）

5.2.2 二叉树的存储结构

顺序存储结构

二叉树的顺序存储指用一组连续的存储单元依次自上而下，从左到右存储完全二叉树上的结点。即将完全二叉树上编号为i的结点存储在数组下标为i或i-1的位置。（因为数组下标起始为0，建议从1开始，保证数组下标与结点编号一致）。对于非完全二叉树，空结点可以用特殊值表示空，例如0，-1等等。
链式存储结构

由于顺序存储的空间利用率低（空结点也占用空间），所以二叉树一般采用链式存储结构（只在简单低级的，无法动态分配空间的情况下使用顺序存储）。使用链表结点来存储二叉树中的每个结点，至少包含三个域：数据域data、左指针域lchild和右指针域rchild

lchild data rchild
```
//二叉树的链式存储结构描述
typedef struct BiTNode{
    ElemType data;                  //数据域
    struct BiTNode *lchild,*rchild; //左、右孩子指针
}BiTNode,*BiTree;
```
可以推出，在含有n个结点的二叉链表中，含有n+1个空链域（在另一种链表结构，即线索链表中，空链表域可以构成线索指针）

对于不同的存储结构，实现二叉树操作的算法也不同，所以需要根据不同应用场景选择合适的存储结构

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

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

5.3.1 二叉树的遍历

先序遍历（NLR）

//若二叉树为空，则什么也不做
//1访问根结点，2先序遍历左子树，3先序遍历右子树
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);               //访问根结点
        PreOrder(T->lchild);    //递归遍历左子树
        PreOrder(T->rchild);    //递归遍历右子树
    }
}

中序遍历（LNR）

//若二叉树为空，则什么也不做
//1中序遍历左子树，2访问根结点，3中序遍历右子树
void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);     //递归遍历左子树
        visit(T);               //访问根结点
        InOrder(T->rchild);     //递归遍历右子树
    }
}

后序遍历（LRN）

//若二叉树为空，则什么也不做
//1后序遍历左子树，2后序遍历右子树，3访问根结点
void PreOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild);   //递归遍历左子树
        PostOrder(T->rchild);   //递归遍历右子树
        visit(T);               //访问根结点
    }
}

递归算法和非递归算法的转化

转非递归算法，需要借助栈来实现，本例以非递归的中序遍历举例，非递归前序遍历和非递归中序基本是一致的，需要注意的是非递归后续遍历，因为要保证左孩子和右孩子已被访问并且左孩子在右孩子前访问才能访问根结点，为流程的控制带来了一些难度。

//非递归中序遍历
//1 沿根的左孩子，依次入栈，直到左孩子为空，说明找到可以输出的结点
//2 栈顶元素出栈并访问；若其右孩子为空，继续执行2；若其右孩子不空，将右子树转执行1
void InOrder_NonRecursive(BiTree T){
    InitStaCK(S);           //初始化栈S
    BiTree p=T;             //p是遍历指针
    while(p||!IsEmpty(S)){  //栈不空或p不空时循环
        if(p){              //一路向左
            Push(S,p);      //当前结点入栈
            p=p->lchild;    //左孩子不空，一直向左走
        }
        else{               //出栈，并转向出栈结点的右子树
            Pop(S,p);       //栈顶元素出栈，访问出栈结点
            visit(p);       //向右子树走，p赋值为当前结点的右孩子
            p=p->rchild;    //返回while循环继续进入if-else
        }
    }
}

层序遍历

//层次遍历，即按照层次顺序自上而下，从左到右遍历
//进行层次遍历，需要借助一个队列。
//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->rchild);//若右孩子不空，则右孩子入队
        }
    }
}

遍历序列倒推二叉树

对于一颗给定的二叉树，其先序序列、中序序列、后序序列和层序序列都是唯一确定的。但任一序列对应的二叉树并不唯一。

故给以上其中一个序列，无法倒推出二叉树，但若给出中序序列 + 前序、后序、层序任一序列，则可以确定一颗二叉树。

技巧：使用前序、后序、层序找到根结点。在中序序列中可以确认该根结点，划分出左右子树，再对左右子树递归地使用该技巧，即可确定一颗二叉树。

5.3.2 线索二叉树

遍历序列以一定规则将二叉树中的结点排列成一个线性序列，使得该序列中每个结点（除了第一个和最后一个）都有一个直接前驱和直接后继

lchild	ltag	data	rtag	rchild

ltag：0表示lchild指向结点的左孩子，1表示lchild指向结点的前驱

rtag：0表示rchild指向结点的左孩子，1表示rchild指向结点的前驱

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

5.4 树、森林

5.4.1 树的存储结构

树的存储方式有多种，即可采用顺序存储也可采用链式存储。但不论怎么存储，都要求能唯一地反映树中各结点之间的逻辑关系。

tree

双亲表示法

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

#define MAX_TREE_SIZE 100   //树中最多结点数

typedef struct{             //树的结点定义
    ElemType data;          //数据元素
    int parent;             //双亲位置域
}PTNode;

typedef struct{             //树的类型定义
    PTNode nodes{MAX_TREE_SIZE};//全部结点
    int n;                  //结点数
}PTree

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

孩子表示法

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

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

又称二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法每个节点包括三部分内容：结点值、指向结点的第一个孩子结点指针、指向结点下一个兄弟结点的指针
```
typedef struct CSNode{
    ElemType data;                          //数据域
    struct CSNode *firstchild,*nextsibling; //第一个孩子和右兄弟指针
}CSNod,*CSTree;
```
孩子兄弟表示法比较灵活，其最大优点是可以方便地实现树转换为二叉树的操作，易于查找结点的孩子等，缺点是查找当前节点的双亲比较麻烦。若为每个结点增设一个parent域指向父结点，则可以解决该缺点。

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

树转为二叉树

左孩子右兄弟法：每个结点的左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟。由于根结点没有兄弟，因此树转换得到的二叉树没有右子树。
森林转为二叉树

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

森林转二叉树的逆向

5.4.3 树和森林的遍历

树的遍历

先根遍历：若树非空，先访问根节点，再依次遍历根结点的每棵子树，遍历子树时遵循先根后子树的规则后根遍历：若树非空，先依次遍历根结点的每棵子树，遍历子树时仍遵循先子树后根的规则
森林的遍历

先序遍历：若森林非空，先访问森林中第一颗树的根结点。再先序遍历第一颗树中根结点的子树森林。再先序遍历除去第一颗树之后剩余的树构成的森林中序遍历：若森林非空，中序遍历森林中第一颗树的根结点的子树森林。再访问第一颗树的根结点。再中序遍历除去第一棵树之后剩余的树构成的子树森林

5.5 树与二叉树的应用

5.5.1 哈夫曼树和哈夫曼编码

哈夫曼树的定义

路径长度：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。路径上的分支数目即为路径长度

权：在树的应用中，树中结点常赋予一个表示某种意义的数值，称为权

带权路径长度：从树的根到一个结点的路径长度与该结点上的权值的乘积，即为带权路径长度，WPL = sum(n,i=i)w(i)l(i)

w(i)是第i个叶结点所带的权，l(i)是该叶结点到根结点的路径长度。

哈夫曼树：在含有n个带权结点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为哈夫曼树，也称为最优二叉树。
哈夫曼树的构造

给定n个权值分别为w1，w2，。。。，wn的结点

1 将这n个结点分别作为n棵仅有根结点的二叉树，构成森林F

2 构造一个新结点，从F 中选取两个权值最小的树作为新结点的左右子树，新结点的权值为左、右子树上根结点的权值之和

3 将得到的新的树加入F中，并且从F中删除刚才选出的两颗树

4 重复步骤2和步骤3，直到F只剩下一颗树为止
哈夫曼编码

固定长度编码：数据通信中，每个字符用相等长度的二进制位表示。

可变长度编码：允许对不同字符用不等长的二进制位表示。

可变长度编码比固定长度编码要好得多，其特点是对频率高的字符赋予短编码，对频率较低的字符赋予长一些的编码，从而使得字符的平均编码长度减短，起到压缩数据的效果。

前缀编码：没有一个编码是另一个编码的前缀，这样的编码称为前缀编码。解码这样的编码很简单。识别出第一个编码后，再依次识别其余编码，就可以解码出来

可以通过二叉树来设计二进制前缀码，而由哈夫曼树得到哈夫曼编码是很自然的过程，首先将每个字符当作独立的结点，其权值为它出现的频度（或次数），构造对应的哈夫曼树。然后将从根到叶子结点的路径上分支标记的字符串作为该字符的编码。

5.5.2 并查集

并查集的概念

并查集是简单的集合表示，它支持以下三种操作

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

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

Find(S,x)：查找集合S中单元素x所在的子集合，并返回该子集合的根结点。
并查集的存储结构

通常用树的双亲表示法作为并查集的存储结构，每个子集合以一颗树表示，所有表示子集合的树，构成表示全集合的森林，存放在双亲表示数组内。

通常用数组元素的下标代表元素名，用根结点的下标代表子集合名，根结点的双亲域为负数，负数可设置为该子集合元素数量的负数