① 用字符ci作为叶子，wi 做为叶子ci的权，构造一棵哈夫曼树，并 将树中左分支和右分支分别标记为0和1； ② 将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的 编码。该编码即为最优前缀码（也称哈夫曼编码）。
(3) 哈夫曼树求得编码为最优前缀码的原因 ① 每个叶子字符ci的码长恰为从根到该叶子的路径长度li，平均码 长(或文件总长)又是二叉树的带权路径长度WPL。而哈夫曼树是WPL最小 的二叉树，因此编码的平均码长(或文件总长)亦最小。 ② 树中没有一片叶子是另一叶子的祖先，每片叶子对应的编码就不可 能是其它叶子编码的前缀。即上述编码是二进制的前缀码。
可以验证，该编码是前缀编码，若一段程序有1000条指令，其中A大约
有400条，B大约有300条，C大约有50条，D大约有40，E大约有30条，F
大约有30条。对于定长编码，该段程序的总位数大约为3×1000=3000.
采用哈夫曼编码后，该段程序的总位数大约为
1×400+2×300+3×150+5×（50+40+30+30）=2200.可见，哈夫曼编码
//由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode {
00
D
01
E
000
F
001
这样虽然可以使得程序的总位数达到 G
010
最小，但机器却无法解码。例如对编码串0010110该怎么识别呢？第一
个0可以识别A，也可以识别与第二个0组成的串00一起被识别为C，还可
以将前三位识别为F，这样一来，这个编码串就有多种译法。因此，若
要设计变长编码，则这种编码必须满足这样一个条件：任意一个编码不
能成为其它任意编码的前缀。我们把这个条件的编码叫做前缀编码。
根据以上描述，利用哈夫曼算 法，我们可以设计出最优的前缀编
指令 A
编码 0
码。首先，我们以每条指令的使用频 B
率为权值构造哈夫曼树，如图(三)所
示
C
0.60
D
0.30
1.00
E
0.30
0.15
F
0.40
0.15
G
0.09
0.06
0.04
0.05
} else if(haffTree[j].weight < m2 && haffTree[j].flag == 0)
{ m2 = haffTree[j].weight; x2 = j;
} } //将找出的两棵权值最小的子树合并为一棵子树
haffTree[x1].parent = n+i; haffTree[x2].parent = n+i; haffTree[x1].flag = 1; haffTree[x2].flag = 1; haffTree[n+i].weight = haffTree[x1].weight+haffTree[x2].weight; haffTree[n+i].leftChild = x1; haffTree[n+i].rightChild = x2; } } 哈夫曼编码算法如下： void HaffmanCode(HaffNode haffTree[], int n, Code haffCode[])
7 3 1
5
7 2
3 5 1 7
5
1 3 1
3
7 5
7 1 3 5
（a）
（b）
（c）
（d）
（e）
图(二 ) 具有相同叶子结点和不同带权路径长度的二叉树
由此可见，由相同权值的一组叶子结点所构成的二叉树有不同的形 态和不同的带权路径长度，那么如何找到带权路径长度最小的二叉树 （即哈夫曼树）呢？根据哈夫曼树的定义，一棵二叉树要使其WPL值最 小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远 离根结点。哈夫曼（Haffman）依据这一特点于1952年提出了一种方 法，这种方法的基本思想是：
d) 重复（b）（c）两步，当F中只剩下一棵二叉树时，这棵二叉 树便是所要建立的哈夫曼树。
由于这种算法是哈夫曼最早提出的，所以将最优二叉树称为哈夫曼 树。
(2) 根据最优二叉树构造哈夫曼编码
哈夫曼树被广泛应用在各种技术中，其中最典型的就是在编码技术上
的应用。利用哈夫曼树很容易求出给定字符集及其概率(或频度)分布的
a) 由给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶结点 的二叉树，从而得到一个二叉树的集合F＝{T1，T2，…， Tn}；
b) 在F中选取根结点的权值最小和次小的两棵二叉树作为左、右 子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为 其左、右子树根结点权值之和；
c) 在集合F中删除作为左、右子树的两棵二叉树，并将新建立的 二叉树加入到集合F中；
中虽然大部分编码的长度大于定长编码的长度3，却使得程序的总位数
变小了。可以算出该哈夫曼的平均码长为
li×wi =1×0.40+2×0.30+3×0.15+5×0.05+5×0.40+5×0.30+5×0.30=2.2
7
∑
i=1
根据上述例子我们可以总结出，利用哈夫曼树获得哈夫曼编码，即最优 前缀编码的具体操做：
(4) 哈夫曼编码的算法 思路：给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程 是：依次以叶子C[i](0≤i≤n-1)为出发点，向上回溯至根为止。上溯 时走左分支则生成代码0，走右分支则生成代码1。
注意： ①由于生成的编码与要求的编码反序，将生成的代码先从后往前依次存 放在一个临时向量中，并设一个指针start指示编码在该向量中的起始 位置（start初始时指示向量的结束位置）。 ②当某字符编码完成时，从临时向量的start处将编码复制到该字符相 应的位串bits中即可。 ③因为字符集大小为n，故变长编码的长度不会超过n，加上一个结束 符'\0'，bits的大小应为n+1。
2、 最优二叉树原理分析
(1) 最优二叉树的基本概念
最优二叉树，也称哈夫曼（Haffman）树，是指对于一组带有确定权 值的叶结点，构造的具有最小带权路径长度的二叉树。那么什么是二叉 树的带权路径长度呢？
如果设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结 点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度， 记为： WPL＝Wk·Lk，其中Wk为第k个叶结点的权值，Lk 为第k个叶结点的 路径长度。如图(一)所示的二叉树，它的带权路径长度值WPL＝2×2＋ 4×2＋5×2＋3×2＝28。
m1 = m2 = MaxValue; x1 = x2 = 0; for(j = 0; j < n+i;j++) { if(haffTree[j].weight < m1 && haffTree[j].flag == 0)
{ m2 = m1; x2 = x1; m1 = haffTree[j].weight; x1 = j;
0.03
0.03
10 110 11100 11101 11110 11111
图（三）构造哈夫曼树
表（三）指令的哈夫曼编码
对于该二叉树，我们可以规定向左的分支标记为1，向右的分支标记为
0。这样从根结点开始，沿线到达各频度指令对应的结点，所以经过的
分枝代码序列就构成了相应频度指令的哈夫曼编码，如表（三）所示。
D
0.15 0.05
E
0.04
F
0.03
为了充分利用编码信息和减少程序 的总位数，我们可以采用变长编码。 如果对每一条指令指定一条编码，使 得这些编码互不相同且最短，是否可 以满足要求呢？即是否可以如表(二) 所示这样编码呢？
表（二） 指令的变长编码
G
0.03
表（一）指令的使用频率
指令
编码
A
0
B
1
C
最优前缀码。
首先我们来看一个例子：
设有一台模型机，共有7种不同的 指令，其使用频率如表(一)所示。
指令
由于计算机内部只能识别0,1代码，
所以采用定长操作码，则需3位
A
使用频率（
wi）
0.40
（23=8）。显然，有一条编码没有作 B
0.30
用，这是一种浪费。一段程序中若有n C 条指令，那么程序的总位数为3×n。
//左孩子下标
int rightChild;
//右孩子下标
};
struct Code
//存放哈夫曼编码的数据
元素结构
{
int bit[MaxN];
//数组
int start;
//编码的起始下标
int weight;
//字符的权值
};
哈夫曼树构造算法如下：
void Haffman(int weight[], int n, HaffNode haffTree[])
(5) 哈夫曼编码的算法的实现 ①哈夫曼编码的数据结构设计 weight
flag
parent
leftChild
rightChild
为了在构造哈夫曼树时能方便的实现从双亲结点到左右孩子结点的操 作，在进行哈夫曼编码时能方便的实现从孩子结点到双亲结点的操作。 设计哈夫曼树的结点存储结构为双亲孩子存储结构。采用仿真指针实
else
haffTrerent = 0;
haffTree[i].flag = 0;
haffTree[i].leftChild = -1;
haffTree[i].rightChild = -1; } //构造哈夫曼树haffTree的n-1个非叶结点 for(i = 0;i < n-1;i++) {