下载掌阅APP，畅读海量书库
立即打开
树是由一个或多个结点组成的有限集合T，它满足以下两个条件。
（1）有一个特定的结点，称为根结点；
（2）其余的结点分成m（m≥0）个互不相交的有限集合。其中每个集合又都是一棵树，称T 1 ,T 2 , …,T m －1 为根结点的子树。
显然，以上定义是递归的，即一棵树由子树构成，子树又由更小的子树构成。由条件（1）可知，一棵树至少有一个结点（根结点）。一个结点的子树数目称为该结点的度（次数），树中各结点度的最大值称为树的度（树的次数）。度为0的结点称为叶子结点（树叶），除叶子结点外的所有结点称为分支结点，根以外的分支结点称为内部结点。例如，如图1-2所示的树，根结点的度数为3，结点2的度数为4，结点4的度数为1，结点9的度数为2，其他结点的度数为0，该树的度数为4。
在用图形表示的树中，对两个用线段连接的相关联的结点而言，称位于上端的结点是位于下端的结点的父结点或双亲结点，称位于下端的结点是位于上端的结点的（孩）子结点，称同一父结点的多个子结点为兄弟结点，称处于同一层次上，不同父结点的子结点为堂兄弟结点。例如，在图1-2中，结点1是结点2、3、4的父结点。反之，结点2、3、4都是结点1的子结点。结点2、3、4是兄弟结点，而结点5、6、7、8、9是堂兄弟结点。
图1-2 树的例子
定义一棵树的根结点所在的层次为0，其他结点所在的层次等于它的父结点所在的层次加1。树中各结点层次的最大值称为树的层次。
因为树是非线性结构，为了存储树，必须要把树中结点之间的关系反映在存储结构中。最常用的存储结构是标准存储和带逆存储结构。
在树的标准存储结构中，树中的结点内容可以分成两部分，分别为结点的数据和指向子结点的指针数组。对于N度树，在其标准存储结构中指针数组有N个元素。
例如，设树的次数为5，树的结点数据仅限于字符，用C代码描述树结点的标准存储结构的数据类型如下：
带逆存储结构在标准存储结构的基础上增加一个指向其父结点的指针，用C代码描述树结点的带逆存储结构的数据类型如下：
按照某种顺序逐个获得树中全部结点的信息，称为树的遍历。常用的树的遍历方法主要有以下3种。
（1）前序遍历：首先访问根结点，然后从左到右按前序遍历根结点的各棵子树。
（2）后序遍历：首先从左到右按后序遍历根结点的各棵子树，然后访问根结点。
（3）层次遍历：首先访问处于0层上的根结点，然后从左到右依次访问处于1层上的结点，然后再从左到右依次访问处于2层上的结点，等等，即自上而下从左到右逐层访问树中各层上的结点。
按上述遍历的定义，图1-3所示树的各种遍历如下结果如下。
（1）前序遍历：1，2，5，6，7，8，3，4，9，a，b。
（2）后序遍历：5，6，7，8，2，3，a，b，9，4，1。
（3）层次遍历：1，2，3，4，5，6，7，8，9，a，b。
二叉树是一个有限的结点集合，该集合或者为空，或者是由一个根结点及其两棵互不相交的左、右叉子树所组成的。二叉树的结点中有两棵子二叉树，分别称为左子树和右子树。因二叉树可以为空，所以二叉树中的结点可能没有子结点，也可能只有一个左子结点（或右子结点），也可能同时有左右两个子结点。如图1-3所示的是二叉树的4种可能形态（如果把空树计算在内，则共有5种形态）。
图1-3 二叉树的4种不同形态
与树相比，二叉树可以为空，空的二叉树没有结点（树至少有一个结点）；在二叉树中，结点的子树是有序的，分左、右两棵子二叉树。
二叉树常采用类似树的标准存储结构来存储，其结点类型可以用C语言定义如下：
二叉树具有下列重要性质（此处省略了推导过程，有兴趣的读者可自行推导）。
性质 1：在二叉树的第i层上最多有2 i – 1 个结点（i≥1）。
性质 2：深度为k的二叉树最多有2 k –1个结点（k≥1）。
性质 3：对任何一棵二叉树，如果其叶子结点数为n 0 ，度为2的结点数为n 2 ，则n 0 ＝n 2+1 。
一棵深度为k且有2 k –1个结点的二叉树称为满二叉树。如图1-4就是一棵满二叉树，对结点进行了顺序编号。
如果深度为k，有n个结点的二叉树中的结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称这样的二叉树为完全二叉树。例如图1-5（a）是一棵完全二叉树，而（b）、（c）是两棵非完全二叉树。显然，满二叉树是完全二叉树的特例。
图1-4 满二叉树的例子
图1-5 完全二叉树、非完全二叉树的例子
根据完全二叉树的定义，显然，在一棵完全二叉树中，所有的叶子结点都出现在第k层或k-1层（最后两层）。
性质 4：具有n个结点的完全二叉树的深度为[log 2 n]+1（注：[m]表示不大于m的最大整数，如[4]=4、[4.1]=4、[4.9]=4，下同）。
性质 5：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第[log 2 n]+1层，每层从左到右），则对任一结点i（1≤i≤n），有：
（1）如果i＝1，则结点i无双亲，是二叉树的根；如果i＞1，则其双亲是结点[i/2]。
（2）如果2i＞n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。
（3）如果2i+1＞n，则结点i无右孩子；否则，其右孩子是结点2i+1。
树的所有遍历方法也同样适用于二叉树，此外，由于二叉树自身的特点，还有中序遍历方法。
（1）前序遍历（先根遍历，先序遍历）：首先访问根结点，然后按前序遍历根结点的左子树，再按前序遍历根结点的右子树。
（2）中序遍历（中根遍历）：首先按中序遍历根结点的左子树，然后访问根结点，再按中序遍历根结点的右子树。
（3）后序遍历（后根遍历，后序遍历）：首先按后序遍历根结点的左子树，然后按后序遍历根结点的右子树，再访问根结点。
例如，图1-6所示的二叉树，其前序遍历、中序遍历和后序遍历结果分别如下。
图1-6 二叉树遍历的例子
（1）前序遍历：1，2，4，5，7，8，3，6。
（2）中序遍历：4，2，7，8，5，1，3，6。
（3）后序遍历：4，8，7，5，2，6，3，1。
以上3种遍历方法都是递归定义的，可通过递归函数分别给以实现。
性质 6：一棵二叉树的前序序列和中序序列可以唯一地确定这棵二叉树。
根据性质6，给定一棵二叉树的前序遍历序列和中序遍历序列，我们可以写出该二叉树的后序遍历序列。例如，某二叉树的前序遍历序列为 ABHFDECKG、中序遍历序列为 HBDFAEKCG，则构造二叉树的过程如图1-7所示。
图1-7 已知前序遍历序列和中序序列，求二叉树的过程
二叉排序树又称为二叉查找树，其定义为：二叉排序树或者是一棵空树，或者是具有如下性质（BST性质）的二叉树。
（1）若它的左子树非空，则左子树上所有结点的值均小于根结点；
（2）若它的右子树非空，则右子树上所有结点的值均大于根结点；
（3）左、右子树本身又各是一棵二叉排序树。
例如，图1-8就是一棵二叉排序树。
图1-8 二叉排序树的例子
根据二叉排序树的定义可知，如果中序遍历二叉排序树，就能得到一个排好序的结点序列。二叉排序树上有查找、插入和删除3种操作。下面，我们假设二叉排序树的结点只存储结点的键值，其类型与前面的二叉树的结点类型相同。
静态查找是在二叉排序树上查找键值为key的结点是否存在，可按以下步骤在二叉排序树ST上找值为key的结点：
（1）如果二叉排序树ST为空二叉树，则查找失败，结束查找；
（2）如果二叉排序树根结点的键值等于key，则查找成功，结束查找；
（3）如果key小于根结点的键值，则沿着根结点的左子树查找，即根结点的左子树作为新的二叉排序树ST继续查找；
（4）如果key大于根结点的键值，则沿着根结点的右子树查找，即将根结点的右子树作为新的二叉排序树ST继续查找。
在二叉排序树上，为插入和删除操作而使用的查找称为动态查找，动态查找应得到两个指针，一个指向键值为key的结点，另一个指向该结点的父结点。为此，查找函数可设4个参数：查找树的根结点指针root、待查找值key、存储键值为key结点的父结点的指针pre，存储键值为key以及结点的指针p。但函数要考虑以下几种不同的情况：
（1）二叉排序树为空，查找失败，函数使*p=NULL，*pre=NULL；
（2）二叉排序树中没有键值为key的结点，函数一直寻找至查找路径的最后一个结点，*pre指向该结点，*p=NULL，如果插入键值为key的结点，就插在该结点下；
（3）查找成功，*p指向键值为key的结点，*per指向它的父结点。
首先利用动态查找函数确定新结点的插入位置，然后分以下几种情况作为相应的处理：
（1）如果相同键值的结点已在二叉排序中，则不再插入；
（2）如果二叉排序为空树，则以新结点为二叉排序树；
（3）根据要插入结点的键值与插入后的父结点的键值比较，就能确定新结点是父结点的左子结点，还是右子结点，并进行相应的插入。
删除二叉排序树上键值为key的结点的操作可按以下步骤进行。
（1）调用查找函数确定被删结点的位置；
（2）如果被删除结点不在二叉排序树上，则函数返回。否则，按以下情况分别处理。
①如果被删除的结点是根结点，又可分以下两种情况。
● 被删除结点无左子树，则以被删除结点的右子树作为删除后的二叉排序树；
● 被删除结点有左子树，则用被删除结点的左子结点作为根结点，并把被删除结点的右子树作为被删除结点的左子树按中序遍历的最后一个结点的右子树。
②如果被删除结点不是根结点，且被删除结点无左子结点，则：
● 被删除结点是它父结点的左子结点，则把被删除结点的右子树作为被删除结点父结点的左子树；
● 被删除结点是它父结点的右子结点，则把被删除结点的右子树作为被删除结点父结点的右子树；
③如果被删除结点不是根结点，且被删除结点无左子结点，则被删除结点的右子树作为被删除结点的左子树按中序遍历的最后一个结点的右子树，同时进行以下操作：
● 被删除结点是它父结点的左子结点，则把被删除结点的左子树作为被删除结点父结点的左子树；
● 被删除结点是它父结点的右子结点，则把被删除结点的左子树作为被删除结点父结点的右子树。
树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。在一些应用中，赋予树中结点的一个有某种意义的实数，这些数字称为结点的权。结点到树根之间的路径长度与该结点上权的乘积，称为结点的带权路径长度。树中所有叶子结点的带权路径长度之和，称为树的带权路径长度（树的代价），通常记为：
其中n表示叶子结点的数目，w i 和l i 分别表示叶子结点k i 的权值和根到结点k i 之间的路径长度。
在权为w 1 ，w 2 ，…，w n 的n个叶子所构成的所有二叉树中，带权路径长度最小（即代价最小）的二叉树称为最优二叉树或哈夫曼树。
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w 1 ，w 2 ，…，w n ，则哈夫曼树的构造规则如下：
（1）将w 1 ，w 2 ，…，w n 看成是有n 棵树的森林（每棵树仅有一个结点）；
（2）在森林中选出两个根结点权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
（3）从森林中删除选取的两棵树，并将新树加入森林。
重复第（2）步和第（3）步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。
例如，如果叶子结点的权值分别为1、2、3、4、5、6，则构造哈夫曼树的过程如图1-9所示。
图1-9 哈夫曼树的构造过程
在构造哈夫曼树的过程中，每次都是选取两棵最小权值的二叉树进行合并，因此使用的是贪心算法。
给定结点序列＜c i ，p i ＞（c i 为编码字符，p i 为c i 的频度），哈夫曼编码的过程如下：
（1）用字符c i 作为叶子，p i 作为c i 的权，构造一棵哈夫曼树，并将树中左分支和右分支分别标记为0和1；
（2）将从根到叶子路径上的标号依次相连，作为该叶子所表示字符的编码。该编码即为最优前缀码。
给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程是：依次以叶子结点c[i](0≤i≤n–1)为出发点，向上回溯至根为止。向上时走左分支则生成代码0，走右分支则生成代码1。需要注意以下几个问题：
（1）由于生成的编码与要求的编码反序，将生成的代码先从后往前依次存放在一个临时串中，并设一个指针start指示编码在该串中的起始位置（start初始时指示串的结束位置）；
（2）当某字符编码完成时，从临时串的start处将编码复制到该字符相应的位串bits中即可；
（3）因为字符集大小为n，故变长编码的长度不会超过n，加上一个结束符“\0”，bits的大小应为n+1。
给定一个序列的集合，若不存在一个序列是另一个序列的前缀，则该序列集合称为前缀码。相反，给定一个序列的集合，若不存在一个序列是另一个序列的后缀，则该序列集合称为后缀码。平均码长或文件总长最小的前缀编码称为最优的前缀码，最优的前缀码对文件的压缩效果亦最佳。
式中p i 为第i个字符的概率，l i 为码长。
利用哈夫曼树很容易求出给定字符集及其概率（或频度）分布的最优前缀码。哈夫曼编码是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据文件压缩掉20%～90%，其压缩效率取决于被压缩文件的特征。