第6章 哈夫曼树.ppt

?6.5.1 哈夫曼树的定义?? ? 在介绍哈夫曼树之前，我们先介绍几个基本概念。 1．路径和路径长度 路径是指从一个结点到另一个结点之间的分支序列，路径长度是指从一个结点到另一个结点所经过的分支数目。 2．结点的权和带权路径长度 在实际的应用中，常常给树的每个结点赋予一个具有某种实际意义的实数，称该实数为结点的权。在树型结构中，把从树根到某一结点的路径长度与该结点的权的乘积，叫做该结点的带权路径长度。 3．树的带权路径长度 树的带权路径长度为树中所有叶子结点的带权路径长度之和，通常记为： 其中n为叶子结点的个数，wi为第i个叶子结点的权值，li为第i个叶子结点的路径长度。 4.哈夫曼树 哈夫曼树又叫最优二叉树，是由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树。 练一练 1: 以数据集合{4,6,8,10,12,15,18,20,22}中的元素为叶子结点的权值构造一棵哈夫曼树，并计算其带权路径长度。 2:以数据集合{5，10，12，15，30，40}为结点的权值，画出构造Huffman树的每一步图示，并计算其带权路径长度。 采用静态数组作为哈夫曼树的存储结构： 对于具有n个叶子结点的哈夫曼树，有n-1个非叶子结点，则哈夫曼树总共有2n-1个结点。 HTNode ht[2*n-1]; 其中：前n个结点为叶子结点，后n-1个结点为分支结点。 { if (n=1) return; m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT+1,i=1; i=n; ++i,++p,++w) *p={*w,0,0,0}; for( ;i=m;++i,++p) *p={0,0,0,0};// i的初值为n for( i=n+1;i=m;++i){ //创建哈夫曼树 Select(HT,i-1,s1,s2); //自己写 HT[s1]-parent=i; HT[s2]-parent=i; HT[i]-lchild=s1; HT[i]-rchild=s2; HT[i]-weight=HT[s1]-weight+ HT[s2]-weight; } } 6.5.3 哈夫曼编码 哈夫曼树被广泛的应用在各种技术中，其中最典型的就是在编码技术上的应用。利用哈夫曼树，我们可以得到平均长度最短的编码。这里我们以计算机操作码的优化问题为例来分析说明： 研究操作码的优化问题主要是为了缩短指令字的长度，减少程序的总长度以及增加指令所能表示的操作信息和地址信息。要对操作码进行优化，就要知道每种操作指令在程序中的使用频率。这一般是通过对大量已有的典型程序进行统计得到的。 设有一台模型机，共有7种不同的指令，其使用频率如下表所示。 由于计算机内部只能识别0、1代码，所以若采用定长操作码，则需要3位（23＝8）。显然，有一条编码没有作用，这是一种浪费。一段程序中若有n条指令，那么程序的总位数为3×n。为了充分地利用编码信息和减少程序的总位数，我们可以采用变长编码。如果对每一条指令指定一条编码，使得这些编码互不相同且最短，是否可以满足要求呢？即是否可以如下表所示这样编码呢？ 这样虽然可以使得程序的总位数达到最小，但机器却无法解码。例如：对编码串0010110该怎么识别呢？第一个0可以识别为I1，也可以和第二个0组成的串00一起被识别为I3，还可以将前三位识别为I6，这样一来，这个编码串就有多种译法。因此，若要设计变长的编码，则这种编码必须满足这样一个条件：任意一个编码不能成为其它任意编码的前缀。我们把满足这个条件的编码叫做前缀编码。 利用哈夫曼算法，可以设计出最优的前缀编码。首先，我们以每条指令的使用频率为权值构造哈夫曼树，如下图所示。 对于哈夫曼树，可以规定向左的分支标记为0，向右的分支标记为1。这样，从根结点开始，沿线到达各频度指令对应的叶子结点，所经过的分支代码序列就构成了相应频度指令的哈夫曼编码，如下表所示。 可以验证，该编码是前缀编码。若一段程序有1000条指令，其中I1大约有400条，I2大约有300条，I3大约有150，I4大约有50条，I5大约有40，I6大约有30，I7大约有30条。对于定长编码，该段程序的总位数大约为3×1000＝3000。 采用哈夫曼编码后，该段程序