赫夫曼树的特点

《赫夫曼树的特点》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、赫夫曼树的特点1.权值越大的叶子离根越近，权值越小的叶结点越远离根结点。2.具有n个叶子结点的赫夫曼树共有2n-1个节点。3.赫夫曼树中没有度为1的结点。严格的二叉树：没有度为1的结点的二叉树。三、哈夫曼树的构造算法设置一个结构数组HuffmanTree保存哈夫曼树中各结点的信息，数组元素的结构形式如下：typedefstruct{unsingnedintweight;unsingnedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树，0号单元不用Typedefchar**Huff

2、manCode;//动态分配数组存储哈夫曼编码weightlchildrchildparent其中，weight域保存结点的权值，lchild和rchild域分别保存该结点的左、右孩子结点在数组HuffmanTree中的序号，从而建立起结点之间的关系。为了判定一个结点是否已加入到要建立的哈夫曼树中，可通过parent域的值来确定。初始时parent的值为0，当结点加入到树中时，该结点parent的值为其双亲结点在数组HuffmanTree中的序号，就不会是0了。构造哈夫曼树时，首先将由n个字符形成的n个叶结点存放到数组HuffmanTree的前n个分

3、量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HuffmanTree数组中的前n个分量的后面。voidHaffmanTree(HuffmanTree&HT){/*哈夫曼树的构造算法*/inti,j,s1,s2,m1,m2,n,m;scanf(“%d”,&n);/*输入叶子结点个数*/m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode));for(i=1;i<=2*n-1;i++)/*数组初始化*/{HT[i].weight=0;HT[

4、i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(i=1;i<=n;i++)scanf(“%d”,&HT[i].weight);/*输入n个叶子结点的权值*/for(i=n+1;i<=m;i++)/*构造哈夫曼树*/{s1=s2=0;m1=m2=10000;/*取最大权值为10000*/for(j=1;j<=i-1;j++){if(HT[j].weight

5、2&&HT[j].parent==0){m2=HT[j].weight;s2=j;}}/*查找权值最小且parent为0的两棵子树的序号s1s2*//*将找出的两棵子树合并为一棵子树*/HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weigh;}}四、哈夫曼树在编码问题中的应用在数据通讯中，经常需要将传送的文字转换成由二进制字符0，1组成的二进制串，我们称之为编码。例如，假设要传送的电文为ABACCDA

6、，电文中只含有A，B，C，D四种字符，字符的四种不同的编码方案字符编码字符编码字符编码字符编码A000A00A0A01B010B01B110B010C100C10C10C001D111D11D111D10总电文长度为21长度为14长度仅为13前缀编码:指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。如何设计一种编码，使得电文的总长度最短呢？具体做法如下：设需要编码的字符集合为{d1，d2，…，dn}，它们在电文中出现的

7、次数或频率集合为{w1，w2，…，wn}，以d1，d2，…，dn作为叶结点，w1，w2，…，wn作为它们的权值，构造一棵哈夫曼树，规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，我们称之为哈夫曼编码。在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是电文的代码总长，所以采用哈夫曼树构造的编码是一种能使电文代码总长最短的不等长编码。采用哈夫曼树进行编码，则不会产生二义性问题。因为，在哈夫曼树中，每个字符结点都是叶结点，它们不可能在根结点到其

8、它字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的非二义性。