Linux安全网 - Linux操作系统_Linux 命令_Linux教程_Linux黑客

会员投稿 投稿指南 本期推荐:
搜索:
您的位置: Linux安全网 > Linux编程 > » 正文

Huffman编码树

来源: 未知 分享至:
先简单回顾一下哈夫曼二叉树的概念:哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+ Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。         构造哈夫曼树的算法如下:         1)对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,..., Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。         2)在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。         3)从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。         4)重复2)和3),直到集合F中只有一棵二叉树为止。        下面举一个很普通的例子:         对于权2,3,5,7,11,13,17,19,23,29,31,37,41,求具有最小带权外部路径长度的二叉树.        1>找到最小权值和次小权值2和3,然后2+3=5构成两个节点的父母,并将5作为下次合并的新权值;                                    5                                  /                                   2        3       2>此时权值更新为5,5,7,11,13,17,19,23,29,31,37,41;然后按照1>的模式找到5和5 并产生其父母10,并作为下次合并的新权值;                                 10                               /                                  5        5                                     /                                       2     3        3>同理 10,7,11,13,17,19,23,29,31,37,41;                                                  17                                                /                                                  7       10                                                        /                                                        5     5                                                             /                                                             2    3           4>  17,11,13,17,19,23,29,31,37,41;                   此时注意最小数和次小树不再是前两位,所以要另起一棵树,由11 和13构成;                                                                                        17                                                                                         /                                                                                      7    10                                            24                                              /                                             /                                              5  5                                           11 13                                             /                                                                                               2  3           5>好了依次比到最后:                 17,17,24,19,23,29,31,37,41;                 19,24,23,29,31,34,37,41;                 24,29,31,34,37,41,42;                 31,34,37,41,42,53;                 37,41,42,53,65;                 42,53,65,78;                 65,78,95;                 95,143;                 238;            完整的树图:                                                                                          238                                                                                    /                                                                                              95                  143                                                                              /                     /                                                                                 42     53              65       78                                                                        /          /              /           /                                                                      19  23   24  29           31  34     37  41                                                                                  /                      /                                                                                   11  13               17     17                                                                                                                   /                                                                                                                   7     10                                                                                                                        /                                                                                                                         5     5                                                                                                                            /                                                                                                                          2     3 

对于哈夫曼树,有一个很重要的定理:对于具有n个叶子节点的哈夫曼树,共有2*n-1个节点。


Tags:
分享至:
最新图文资讯
1 2 3 4 5 6
验证码:点击我更换图片 理智评论文明上网,拒绝恶意谩骂 用户名:
关于我们 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 发展历史