第七章 图7.0 前言 7.1 图的定义和术语 7.2 图的存储表示 7.3 图的遍历 7.4 图的连通性 7.5 有向无环图及其应用 7.6 最短路径 6.1、哈夫曼树 6.1.1.带权二叉树 6.1.2.给定确定权值的带权二叉树 6.1.3.哈夫曼树的建立 6.1.4.哈夫曼树构造算法分析 6.1.5.哈夫曼树构造算法描述6.1.1、带权二叉树最优二叉树，也称哈夫曼（Haffman）树，是 指对于一组带有确定权值的叶结点，构造的具有 最小带权路径长度的二叉树。 二叉树的带权路径长度在前面我们介绍过路径和结点的路径长度的概念，而二叉树 的路径长度则是指由根结点到所有叶结点的路径长度之和。 如果二叉树中的叶结点都具有一定的权值，则可将这一概念 加以推广。设二叉树具有n个带权值的叶结点，那么从根结 点到各个叶结点的路径长度与相应结点权值的乘积之和叫做 二叉树的带权路径长度，记为：二叉树的带权路径长度示例其中Wk为第k个叶结点的权值， Lk 为第k个叶结点的路径长度。如右图所示的二叉树， 它的带权路径长度值： WPL2242 523228。 6.1.2.给定确定权值的带权二叉树 在给定一组具有确定权值的叶结点，可以构造出不同的 带权二叉树。例如，给出4个叶结点，设其权值分别为1 ，3，5，7，我们可以构造出形状不同的多个二叉树。这些形状不同的二叉树的带权路径长度将各不相同。 图给出了其中5个不同形状的二叉树。 给定确定权值的带权二叉树示例这五棵树的带权路径长度分别为：（a）WPL1232527232（b）WPL1333527129（c）WPL1233537133（d）WPL7353321143（e）WPL71523313296.1.3.哈夫曼树的建立由此可见，由相同权值的一组叶子结点所构成 的二叉树有不同的形态和不同的带权路径长度，那 么如何找到带权路径长度最小的二叉树（即哈夫曼 树）呢？根据哈夫曼树的定义，一棵二叉树要使其WPL 值最小，必须使权值越大的叶结点越靠近根结点， 而权值越小的叶结点越远离根结点。哈夫曼（Haffman）算法：（1）由给定的n个权值W1，W2，Wn构造n棵只有 一个叶结点的二叉树，从而得到一个二叉树的集合FT1， T2，Tn； （2）在F中选取根结点的权值最小和次小的两棵二叉树作 为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点 的权值为其左、右子树根结点权值之和； （3）在集合F中删除作为左、右子树的两棵二叉树，并将 新建立的二叉树加入到集合F中； （4）重复（2）（3）两步，当F中只剩下一棵二叉树时， 这棵二叉树便是所要建立的哈夫曼树。哈夫曼算法示例6.1.4.哈夫曼树构造算法分析在构造哈夫曼树时，可以设置一个结构数组HuffNode保存 哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n 个叶子结点的哈夫曼树共有2n1个结点，所以数组 HuffNode的大小设置为2n1，数组元素的结构形式如下： weight域保存结点的权值，lchild和rchild域分别保存该结 点的左、右孩子结点在数组HuffNode中的序号，从而建立 起结点之间的关系。 6.1.4.哈夫曼树构造算法分析为了判定一个结点是否已加入到要建立的哈夫曼树中，可 通过parent域的值来确定。初始时parent的值为1，当结 点加入到树中时，该结点parent的值为其双亲结点在数组 HuffNode中的序号，就不会是1了。构造哈夫曼树时，首先将由n个字符形成的n个叶结 点存放到数组HuffNode的前n个分量中，然后根据前面介 绍的哈夫曼方法的基本思想，不断将两个小子树合并为一 个较大的子树，每次构成的新子树的根结点顺序放到 HuffNode数组中的前n个分量的后面。6.1.5.哈夫曼树构造算法描述#define MAXVALUE 10000 /*定义最大权值*/ #define MAXLEAF 30 /*定义哈夫曼树中叶子结点个数*/ #define MAXNODE MAXLEAF*2-1 typedef structint weight;int parent;int lchild;int rchild; HNodeType;6.2、哈夫曼编码 6.2.1.哈夫曼编码 6.2.2.哈夫曼编码算法 6.2.3.哈夫曼编码算法描述 编码方案字符ABCD的四种编码方案：在数据通讯中，经常需要将传送的文字转换成由二 进制字符0，1组成的二进制串，我们称之为编码。6.2.1.哈夫曼编码例如，假设要传送的电文为ABACCDA，电文中只含有A，B， C，D四种字符，若这四种字符采用方案一所示的编码，则电文 的代码为000010000100100111 000，长度为21。在传送电文时，总是希望传送时间尽可能短，这就要求电文 代码尽可能短，显然，这种编码方案产生的电文代码不够短。方案二所示为另一种编码方案，用此编码对上述电文进行编 码所建立的代码为00010010101100，长度为14。6.2.1.哈夫曼编码在这种编码方案中，四种字符的编码均为两位，是一种等长 编码。如果在编码时考虑字符出现的频率，让出现频率高的字符采 用尽可能短的编码，出现频率低的字符采用稍长的编码，构造 一种不等长编码，则电文的代码就可能更短。如当字符A，B，C，D采用方案三所示的编码时，上述电文的 代码为0110010101110，长度仅为13。 6.2.1.哈夫曼编码哈夫曼树可用于构造使电文的编码总长最短的编码方案。 具体做法如下： 设需要编码的字符集合为 d1，d2，dn， 出现的次数或频率集合为w1，w2，wn， 则以d1，d2，dn作为叶结点，w1，w2，wn作为它们的 权值，构造一棵哈夫曼树，规定哈夫曼树中的左分支代表0，右 分支代表1，则从根结点到每个叶结点所经过的路径分支组成的 0和1的序列便为该结点对应字符的编码，我们称之为哈夫曼编 码。 在哈夫曼编码树中，树的带权路径长度，为电文的代码总长， 所以采用哈夫曼树构造的编码是一种能使电文代码总长最短的 不等长编码。 6.2.1.哈夫曼编码在建立不等长编码时，必须使任何一个字符的编码都不是另一 个字符编码的前缀，这样才能保证译码的唯一性。例如方案四的编码方案，字符A的编码01是字符B的编码010的 前缀部分，这样对于代码串0101001，既是AAC的代码，也是 ABD和BDA的代码，因此，这样的编码不能保证译码的唯一性， 我们称之为具有二义性的译码。然而，采用哈夫曼树进行编码，则不会产生上述二义性问题。 因为，在哈夫曼树中，每个字符结点都是叶结点，它们不可能 在根结点到其它字符结点的路径上，所以一个字符的哈夫曼编 码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码 的非二义性。6.2.2.哈夫曼编码算法实现哈夫曼编码的算法可分为两大部分：（1）构造哈夫曼树； （2）在哈夫曼树上求叶结点的编码。求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶结点 开始，沿结点的双亲链域回退到根结点，每回退一步，就走 过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于 一个字符的哈夫曼编码是从根结点到相应叶结点所经过的路 径上各分支所组成的0，1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码。6.2.3.哈夫曼编码算法描述/*定义哈夫曼编码的最大长度*/ #define MAXBIT 10 typedef struct int bitMAXBIT;int start; HCodeType;