假期连载之十二(100)
（树形结构—树和森林、哈夫曼树）
本篇为12号的第三篇连载，基于时间、理论连贯性上的考虑，我们利用下午的时间完成了前两篇关于树的基本概念及其ADT，二叉树及其相关等内容，现在我们介绍树形结构对基础概念的扩展—一般树，以及森林。最后我们会研究一种特殊的二叉树结构，它通常被人称为最优二叉树，是信息传输、数据压缩领域的重要工具。
树、森林和二叉树的关系
在一般树的条件下，分支个数是不定的，因此会出现所谓的多叉树。对于这种一般的树，我们就需要采用一种不同于二叉树二叉链表的存储表示。
1、 广义表表示法
广义表表示树是一种非常有效的方法，树中结点可以分三种：叶结点、根结点以及除根结点之外的其它非叶结点（也称分支结点）。因此在广义表中也可以有三种结点与之对应：原子结点、表头结点、子表结点。
在子表结点内部，我们同样使用从上至下、从左至右的顺序对结点进行排序。其运算也是基于广义表的基本运算进行的。
我们在前面的连载中介绍了广义表的头尾链表和扩展线性链表等存储表示方法，并附加了相关基础运算，但必须注意的是，广义表在一些高级语言中能够特别方便地使用，这也是这种数据结构诞生的初衷，因此在其它高级语言中应尽量在实际应用中避免采用这种并不擅长的方式进行运算。
2、 父指针表示法
利用一组连续的空间来存储树中的结点，在保存每个结点的同时附设一个指示器来指示其父结点在表中的位置。这种结构易于求指定结点的父结点，但当求某结点的子女结点时需遍历结构数组。
3、 子女表示法
这种方法通常是把每个结点的子女结点排列起来，构成一个单链表，称其为子女链表。n个结点共有n个子女链表，其中叶子结点的子女链表为空。而n个结点的数据和n个子女链表的头指针又组成一个顺序表。这种结构适合需要频繁寻找子女结点的应用，并可以和父指针表示法结合，使寻找父结点或子女结点都很方便。
4、 子女-兄弟表示法
这种方法是一种二叉树表示法，也被称为二叉链表表示法。其链表结点中包含三个结点域，分别指向该结点的第一个子女结点指针，指向下一个兄弟结点指针以及数据域。这种存储结构首先比较清晰地描绘了树形结构的容貌，同时非常方便实现树的各类操作。与以上三种表示法相比，子女兄弟表示法既在操作上容易实现了许多，且在空间和时间的效能上也具有一定优势。
根据子女兄弟表示法的启示，我们发现一般树和二叉树均可以用二叉链表进行表示，换一个角度说，我们可以通过一定转换，将一般树按原二叉链表表示的序列转化为二叉树形式，且并不影响对树进行的各种基本运算的结果。
1、 树转换为二叉树
将一棵树转换为二叉树的方法是，将树中的所有兄弟结点之间加一条连线，对树中的每个结点，只保留其与第一个子女结点之间的连线，删去其与其它子女结点之间的连线。最后以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。
可以证明，通过这种方法树转换成的二叉树是唯一的。而且此时二叉树的链表表示与树本身的子女-兄弟表示法所生成的二叉链表完全一致，这时就可以展开对树的各种基本操作。
2、 森林转换为二叉树
森林是若干树的集合。那么采用如下方法可以将森林转换为二叉树表示：首先将森林中的每棵树转换成相应的二叉树，第一棵二叉树不动，从第二棵二叉树开始依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右子结点，当所有二叉树连在一起后，得到的二叉树即是由森林转换得到的二叉树。
3、 二叉树还原为树或森林
树转换成的二叉树，其特点是必无右子结点，而森林转换成的二叉树，其必含右子结点。根据以上特征区分还原的对象。然后按照以下方法还原二叉树：若某结点是其父结点的左子结点，则把该结点的右子结点、右子结点的右子结点、…均与该结点的父结点用线连接起来。此时删除掉原二叉树中所有父结点与右子结点的连线，并加以整理即可。
树与森林的遍历
基于前面建立的子女兄弟存储表示，我们可以得出树和森林的一般遍历算法，它们与二叉树的相关遍历算法有很深厚的联系。
从大方面看，树与森林的遍历分为深度优先遍历和广度优先遍历两种。
1、 深度优先遍历是一种与二叉树遍历类似的遍历算法
a) 树的先根遍历算法，类似于二叉树遍历的先序顺序。其结果与直接用先序遍历算法所演示的结果是相一致的。
b) 后根遍历，实际上类似于二叉树遍历的后序顺序。
我们以树的递归先根次序遍历算法为例，给出具体编程实现先根的两种方法：
if(root!=NULL)
{
Visit(root->data);
p=root->FirstChild;
while(p!=NULL)
{
RootFirst(p); //访问以p为根的子树
p=p->nextSibling;
}
}//以上是方法一
if(root!=NULL)
{
Visit(root->data);
RootFirst(root->FirstChild);
RootFirst(root->NextSibling);
}//方法二消除了循环，也以递归的方式呈现
对于森林的遍历，一般也分先序遍历、中序遍历以及后序遍历，值得注意的是在森林的后序遍历中第一棵树的根结点应放在最后访问，以后其它各树的根结点依次倒数访问，这点需特别留意。
2、广度优先遍历是一种新的遍历方法，它是以结点的序号排列为顺序直接遍历的。在这种算法中并不存在递归结构，通常使用队列的方法，扫描至每一层时，将该层的所有结点入队，然后依次访问。
哈夫曼树
哈夫曼树Huffman Tree又称最优二叉树，是一类加权路径长度最短的二叉树。其在编码设计、决策和算法设计等领域有着广泛的应用。我们大家现今经常使用的图像格式JPEG，就是一种基于DCT(离散余弦变换)和哈夫曼编码的有损高压缩比编码标准。
我们首先给出哈夫曼树的一些概念。
路径path，指从树中一个结点到另一个结点之间的分支构成该两点之间的路径。
路径长度path length，指路径上的分支条数。树的路径长度一般指树的根结点到每个结点的路径长度之和。
由树的定义可知，从根结点到达树中的每一个结点有且仅有一条路径。若设树的根结点位于第1层，某结点处于第k层，则其路径上的分支条数为k-1，因此从根结点到其它各个结点的路径长度等于该结点所处的层次k-1。
一般来说，当结点数相同时，越接近完全二叉树的结构其路径长度越短。
定义一个带权路径长度Weighted Path Length(WPL)，假设有n个权值的集合中，若T是一棵有n个叶结点的二叉树，且将集合中的权值分别赋给T的n个叶结点，此时我们称T是权值为相关值的扩充二叉树。带权结点被称为外结点，其余结点被称做内结点。外结点的带权路径长度为从T的根到该结点的路径长度与该结点上权值的乘积。此时将整个扩充二叉树的带权路径长度定义为WPL，就是每个外结点带权路径长度之和。
我们把WPL最小的扩充二叉树称为最优二叉树。在这种情况里，最小带权路径长度的扩充二叉树就不再一定是完全二叉树。从直观上看，最优二叉树应该是权值大的外结点离根结点越近的扩充二叉树，就是Huffman树。
构造哈夫曼树
构造哈夫曼树的算法是由Huffman提出的，其基本思路为：
1、 根据给定的n个权值，构造具有n棵扩充二叉树的森林，其中每一棵二叉树都有一只权值为相关值的根结点，其左右子树为空。
2、 找最小树，在森林中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左右子树，标记新二叉树的根结点权值为其左右子树的根结点权值之和。
3、 删除与加入，从森林中删除被选中的那两棵二叉树，同时把新构成的二叉树加入到森林中。
4、 判断，重复2、3步骤，直到森林中只含有一棵二叉树时为止。
程序构建哈夫曼树，首先须确定一个静态三叉链表的结点结构，这种结点由四个域构成：分别是权值域、父结点序号、左子结点序号以及右子结点序号。为了计算方便，0号单元不用，从1号开始使用，程序也按照静态链表的构建方法进行。
哈夫曼编码
构造哈夫曼树的实质还是为了求哈夫曼编码。通常计算机中存储的图形符号是以二进制码进行处理的。例如ASCII码就是一种8位二进制编码，且还是一种定长编码。为了压缩数据存储空间，有必要采用不定长编码的方式进行编码。首先介绍几个概念：
1、前缀码，如果在一个编码系统中，任一个编码都不是其它任何编码的前缀（即最左子串），则成该编码系统中的编码是前缀码。例如一组编码01，001，010，100，110就不是前缀码，因为01是010的前缀，去掉其中之一后即为前缀码。
如果采用前缀码，我们就可以在各字符对应的编码之间不需要分隔符。如果非前缀码，不使用分隔符则会产生二义性。
2、哈夫曼编码，对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶子的通路上，各分支的赋值分别构成一个二进制串，该二进制串即位哈夫曼编码。
求解哈夫曼编码的方法也有很多，一般而言，我们首先根据带权结点构建哈夫曼树，此时将哈夫曼树的左分支标记为0，右分支标记为1，根结点不计，我们从根结点出发，把抵达相关叶结点的路径按先后顺序编码，则就构成了哈夫曼编码。
在实际编程中，对0和1的赋值是在求编码的算法中直接进行判断的。
（未完待续）