文档介绍：Ch1 哈夫曼树
一、基本概念
1、路径和路径长度
在一棵树中，如果存在着一个结点序列k,k,…,k,使得k是k的父结点（lWiWj）,
1 2 j i i+1
则称此结点序列是从k到k的路径，因树中每个结点只有一个父结点，所以它率
i i i
和编码长度。结合我们的例子，可以求出L为：
L = f （c x 3） = 3 x （4 + 2 + 6 + 8 + 3 + 2） = 75
i i=1
可知，采用等长编码时，传送电文的总长度为75。
如何通过缩短传送电文的总长度，以节省传送时间呢？如果采用不等长编码，让出现频 率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样有可能缩短传送电 文的总长度。采用不等长编码要避免译码的二义性或多义性。假设用0表示字符D,用01 表示字符C,则当接收到编码串…01…，并译字符0时，是立即译出对应的字符D,还是与 下一个字符1一起译为对应的字符C呢？这种情况下就会产生二义性了。因此，如果对某一 字符集进行不等长编码，则要求字符集中任一字符的编码都不能是其他字符编码的前缀。符 合此要求的编码叫做前缀编码。显然，等长编码是前缀编码，这从等长编码所对应的编码二 叉树也可以直观地看出，任一叶子结点都不可能是其他叶子结点的前驱，也就是说，只有当 一个结点是另一个结点的前驱时，该结点的字符编码才会是另一个结点的字符编码的前缀
为了使不等长编码为前缀编码，可以用该字符集中的每个字符作为叶子结点生成一棵编 码二叉树。为了获得传送电文的最短长度，可以将每个字符的出现频率作为字符结点的权值 赋予该结点上，求出此树的最小带权路径长度就等于求出传送电文的最短长度。因此，求传 送电文的最短长度问题就转化为求由字符集中的所有字符作为叶子结点，由字符的出现频率 作为其权值所产生的哈夫曼树的问题。
根据上面所讨论的例子，生成的哈夫曼树如下图所示，由编码哈夫曼树得到的字符编码 称为哈夫曼编码。在下图中，A、B、C、D、E、F这六个字符的哈夫曼编码依次为：00、
1110、 01、 10、 110、 1111。电文的最短传送长度为：
L 二 WPL = wl
ii
i 二1
—4 x 2 + 2 x 4 + 6 x 2 + 8 x 2 + 3 x 3 + 2 x 4
二 61
显然，这比等长编码所得到的传送总长度75 要小得多。
四、哈夫曼算法的实现 如何用程序实现哈夫曼算法呢？这与实际问题所采用的存储结构有关，现假设用数组 F
来存储哈夫曼二叉树，其中第i个数组元素F[i]是哈夫曼二叉树中的一个结点，其地址为i， 有3个域，Data域存放该结点的权值，lChild域和rChild域分别存放该结点左、右子树的 根结点的地址（下标）。在初始状态下：
F[i].Data=W ；F[i].lChild=0；F[i].rChild=0 （i=1,2,„,n）
i
即先构造好n个叶子结点，以后每步构造一棵新的二叉树时，都对森林中所有二叉树的 根结点进行排序，因此可用数组a作为排序暂存空间，其中第i个数组元素a[i]是森林中 第i棵二叉树的根结点，有2个域，Data是根结点所对应的权值，Addr是根结点在F中的 地址（下标），在初始状态下：
a[i].Data=W ；a[i].Addr=i （i=1,2,„n）
i
下面给出建立哈夫曼二叉树的过程：
Procedure createhfm（f, t,a,n）｛已知n个权值a[i]，构造哈夫曼树f,且根结点地址为t｝ Var i:Integer；
Begin
For i:=1 To n Do Begin ｛初始化｝ f[i].data:=a[i].data； f[i].lchild:=0； f[i].rchild:=0； a[i].addr:=i
End；
t:=n+1； ｛t指向下一个可利用单元｝
i:=n； ｛当前森林中的二叉树是i｝
While i>=2 Do Begin
insert（a,i） ； ｛对a的前i个元素按data域进行排序｝ f[ t].da ta:二a[l].da ta+a[2].da ta； ｛生成新的二叉树｝ f[t].lchild:=a[1].addr；
f[t].rchild:=a[2].addr； a[1].data:=f[t].data； ｛修改森林｝ a[1].addr:=t；
a[2].data:=a[i].data； ｛修改森林｝ a[2].addr:=a[i].add；
i:=i-1； ｛二叉树数目减一｝ t:=t+1；
End；
End； 该算法是使用数组来建立二叉树，使用指针链表来建立二叉树的程序留给读者完成。
Ch2 排序二叉树
一、基