（知识点）二叉树的总长度和75编码

在电报通信中，消息以 0 和 1 的二进制序列传输。 在发送端，需要将报文中的字符序列转换为0和1的二进制序列（即编码），在接收端，需要将接收到的0和1的序列转换为对应的字符序列（即解码）。

(1)等长编码

最简单的二进制编码方法是等长编码。 例如，假设消息中只使用了A、B、C、D、E、F这六个字符，如果将它们进行等长编码，则各自需要三个二进制字符，可以按顺序编码为000， 001, 010, 011, 100 ,101。 如果将这6个字符作为6个叶子节点，则生成一棵二叉树，二叉树中每个分支节点的左右分支分别用0和1编码，从根节点到每个叶子节点。 路径上分支的0和1的编码序列应等于叶节点的二进制编码，则相应的编码二叉树如图6-13所示。

编码二叉树

从常识可知，一条消息中每个字符出现的频率（即出现的次数）一般是不同的。 假设在一条消息中，这6个字符出现的频率为4、2、6、8、3、2，那么编码消息的总长度L可以通过以下公式计算：

其中，n表示消息中使用的字符数，ci和li分别表示消息中对应字符ki的出现频率和编码长度。 结合我们的例子，L可以得到：

可以看出，采用等长编码时，传输的报文总长度为75。

(2)不等长编码

现在我们来讨论如何缩短传输报文的总长度，从而节省传输时间？ 我们自然想到，如果采用不等长编码，出现频率高的字符编码较短，出现频率低的字符编码较长，这样可能会缩短传输消息的总长度。 使用不等长编码应避免解码二义或歧义。 假设用0表示字符D，用01表示字符C，那么当收到编码串...01...，翻译字符0时，是立即翻译对应的字符D，还是直接翻译？与下一个字符 1 一起翻译吗？ 字符 C，造成歧义。 因此，如果某个字符集采用不等长编码，则要求该字符集中任意字符的编码不能是其他字符编码的前缀。 满足此要求的编码称为无前缀编码。 显然等长编码是一种无前缀编码。 这从等长编码对应的编码二叉树也可以直观地看出。 任何叶节点都不能是其他叶节点的父节点。 也就是说，只有当一个节点是另一个节点的父节点时，该节点的字符编码才会是另一个节点的字符编码的前缀。

为了使不等长编码成为无前缀编码，可以将字符集中的每个字符作为叶子节点，生成编码二叉树。 为了获得传输消息的最短长度，可以将每个字符出现的频率作为字符节点，为该节点分配一个权重，这棵树的最小加权路径长度等于发送的消息。 因此，寻找传输消息的最短长度的问题就转化为寻找以字符集中所有字符为叶节点，以字符出现频率为权重生成的哈夫曼树的问题。

基于上面讨论的例子，生成的编码哈夫曼树如图6-14所示。 通过对哈夫曼树进行编码得到的字符编码称为哈夫曼编码（Code）。 图6-14中，A、B、C、D、E、F这6个字符的哈夫曼码分别为：00、1010、01、11、100、1011。报文的最小传输长度为：

显然，这比等长编码得到的传输报文总长度75要小得多。

编码哈夫曼树

(3)查找哈夫曼编码的算法描述

通过对已经介绍的求哈夫曼树带权路径长度的算法稍加修改，我们可以得到哈夫曼编码的算法描述，如下所示。

求霍夫曼编码算法

	void HuffManCoding(struct BTreeNode* FBT, int len)
	 /*根据FBT所指向的哈夫曼树输出每个叶子的编码，len初值为0*/
	 {
	 /*定义一个静态数组a，保存一个叶子的编码，数组的长度要
	 至少等于哈夫曼树的深度减1*/
	 static int a[10];
	 if(FBT!=NULL) {
	 /*访问到叶子结点时输出其保存在数组a中的0和1序列编码*/
	 if(FBT->left==NULL && FBT->right==NULL) {
	 int i;
	 printf("结点权值为%d的编码:",FBT->data);
	 for(i=0; ileft,len+1);
	 a[len]=1; HuffManCoding(FBT->right,len+1);
	 }
	 }
	 }