huffman，Huffman编码的算法

本文目录一览

1，Huffman编码的算法
2，Huffman是什么来的
3，什么是霍夫曼编码
4，Huffman树的应用
5，什么是哈夫曼算法
6，到底什么是哈夫曼树啊求例子

1，Huffman编码的算法

a:11 b:10 c:110 d:011 e:111

Huffman编码的算法

2，Huffman是什么来的

人名：哈夫曼

我记得在《数据结构》里看到过，huffman编码。是利用人名huffman叫的。

哈夫曼在百度查它是人名也是一种事物和一种理论方法请采纳谢谢祝：家庭健康包括你

Huffman是什么来的

3，什么是霍夫曼编码

霍夫曼（Huffman）编码原理霍夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。步骤进行：l）将信号源的符号按照出现概率递减的顺序排列。2）将两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。 3）重复进行步骤1和2直到概率相加的结果等于1为止。4）在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。5）记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符号的编码。例：设信号源为 s＝｛s1, s2, s3, s4, s5｝对应的概率为p＝｛0.25，0.22，0.20, 0.18，0.15｝。根据字符出现的概率来构造平均长度最短的异字头码字。霍未曼编码通常采用两次扫描的办法，第一次扫描得到统计结果，第二次扫描进行编码。霍夫曼编码具有一些明显的特点：1) 编出来的码都是异字头码，保证了码的唯一可译性。2) 由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。3) 编码长度不统一，硬件实现有难度。4) 对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达到100％的编码效率；若信号源符号的概率相等，则编码效率最低。5) 由于"0"与"1"的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。

什么是霍夫曼编码

4，Huffman树的应用

哈夫曼树在一般的数据结构的书中，树的那章后面，著者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如JPEG中就应用了哈夫曼编码。首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。（注：码字即为符号经哈夫曼编码后得到的编码，其长度是因符号出现的概率而不同，所以说哈夫曼编码是变长的编码。）然而怎样构造一棵哈夫曼树呢？最具有一般规律的构造方法就是哈夫曼算法。一般的数据结构的书中都可以找到其描述：一、对给定的n个权值二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。四、重复二和三两步，直到集合F中只有一棵二叉树为止。用C语言实现上述算法，可用静态的二叉树或动态的二叉树。若用动态的二叉树可用以下数据结构： struct tree float weight; /*权值*/ union char leaf; /*叶结点信息字符*/ struct tree *left; /*树的左结点*/ }; struct tree *right; /*树的右结点*/ }; struct forest struct tree *ti; /* F中的树*/ struct forest *next; /* 下一个结点*/ }; 例：若字母A，B，Z，C出现的概率为：0.75,0.54,0.28,0.43；则相应的权值为：75，54，28，43。构造好哈夫曼树后，就可根据哈夫曼树进行编码。例如：上面的字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。例如：a,b,c,d的编码为：0，10，101，11，对于编码串：1010就可翻译为bb或ca，因为b的编码是c的编码的前缀。刚才进行哈夫曼编码的规则是从根结点到叶结点（包含原信息）的路径，向左孩子前进编码为0，向右孩子前进编码为1，当然你也可以反过来规定。这种编码方法是静态的哈夫曼编码，它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，（用4Bytes的长度存储频率值，频率值的表示范围为0--2^32-1，这已足够表示大文件中字符出现的频率了）以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。静态哈夫曼编码方法有一些缺点：一、对于过短的文件进行编码的意义不大，因为光以4BYTES的长度存储哈夫曼树的信息就需1024Bytes的存储空间；二、进行哈夫曼编码，存储编码信息时，若用与通讯网络，就会引起较大的延时；三、对较大的文件进行编码时，频繁的磁盘读写访问会降低数据编码的速度。因此，后来有人提出了一种动态的哈夫曼编码方法。动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。动态哈夫曼编码比静态哈夫曼编码复杂的多，有兴趣的读者可参考有关数据结构与算法的书籍。前面提到的JPEG中用到了哈夫曼编码，并不是说JPEG就只用哈夫曼编码就可以了，而是一幅图片经过多个步骤后得到它的一列数值，对这些数值进行哈夫曼编码，以便存储或传输。哈夫曼编码方法比较易懂，大家可以根据它的编码方法，自己编写哈夫曼编码和解码的程序。

5，什么是哈夫曼算法

题目的阐述：　　　以ｎ进制编码方式对一个英文字串中的字符进行编码，每个不同的字符其编码不同．使得由新的编码替代原串后总码长最小，且输入０，１，２，．．．，ｎ－１构成的数字串后，依照该编码方式可以正确的对译出唯一的英文原串．　　如：　ｎ＝３　英文原串为　ａｂｂｃｂａｄｄａｃｅ　　其对应的一种编码方式为　　ａ：００　　ｂ：０１　　ｃ：０２０　　ｄ：０２１　　ｅ：０２２　　原串对译后的编码为０００１０１０２００１０００２１０２１０００２００２２　　其码长为２７　　若输入编码串　　　　０１０２００２２００　　则对应的英文原串为　ｂｃｅａ分　析：　　假设英文原串中的字符存放于字符集ｓ中，‖ｓ‖＝　ｘ，每个字符在字串中出现的概率为ｗ［ｉ］，ｌ［ｉ］为字符ｉ的编码长．　　依题意得，对ｓ集合中的不同字符进行ｎ进制编码后要求　　　　１）新字串的码长最短　　　　　　　　　　ｗｐｌ＝∑ｗ［ｉ］＊ｌ［ｉ］（ｉ∈１．．ｘ）　　　　　　　　使得在ｗｐｌ是所有编码方式中的最小值　　　　２）编码无二义性　　　　　　　　任意一字符编码都不为其它字符编码的前缀　　此题以哈夫曼树来解答是非常适宜的．ｎ为此哈夫曼树的分叉数，ｓ字符集里的元素即为此　　ｎ叉哈夫曼树的叶子，概率ｗ［ｉ］即为叶子结点的权重，从根结点到各叶子结点的路径长即为该叶子结点的编码长ｌ［ｉ］．由哈夫曼树的思想可以知道哈夫曼树的建立是一步到位的贪心法，即权重越大的结点越靠近该树的根，这样，出现频率越大的字符其编码就越短．　　　　但具体应该怎样建立起此ｎ叉哈夫曼树呢？我们首先以ｎ＝２为例　：　　ｓ＝｛ａ，ｂ，ｃ，ｄ｝　　ｗ＝［３，１，２，１］　　　首先从ｗ中选出两个最小权，１，１，将其删去，并以２（即１＋１）替代　　　　ｗ＝［３，２，２］；　　再从新的ｗ中取出两个最小权，２，２，将其删去，并以４（即２＋２）替代　　　　ｗ＝［３，４］；　　依此类推，直到ｗ中只一个值时合并结束，此时　ｗ＝［７］　　以上两两合并的过程即为二叉哈夫曼树的建立过程，每一次的合并即是将两棵子树归于一个根结点下，于是可以建立二叉树如下：　　　　　　　　　　　　　　　　　　　　　　　　m 　　　　　　　　　　　　　　　　　　　　　　０?　　?１　　　　　　　　　　　　　　　　　　　　　　m　　　m 　　　　　　　　　　　　　　　　　　　　　ａ　　０?　　?１　　　　　　　　　　　　　　　　　　　　　　　m　　　　m 　　　　　　　　　　　　　　　　　　　　　　　ｃ　　０?　　?１　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　m　　　　　m 　　　　　　　　　　　　　　　　　　　　　　　　　ｂ　　　　　　ｄ　　ｍｉｎ－ｗｐｌ＝３＊１＋１＊３＋２＊２＋１＊３＝１３　从某一根结点出发走向其左子树标记为０，走向其右子树标记为１，则可以得到以下编码　ａ，ｂ，ｃ，ｄ对应的编码为　　　ａ：０　　　ｂ：１１０　　　ｃ：１０　　　ｄ：１１１　ｎ＝３时又是怎样一种情况呢？　　设　ｓ＝｛ａ，ｂ，ｃ，ｄ，ｅ｝　　　　ｗ＝［７，４，２，５，３｝　　则按权重排序可得　　　　ｓ＝｛ｄ，ｂ，ｅ，ｃ，ａ｝　　　　　　　　　ｗ＝［７，５，４，３，２］　　那么此哈夫曼树的树形应为怎样呢？　　是以下的左图，还是右图，或是两者均不是　　　　　　　　　　　m　　　　　　　　　　　　　　　　　　　m 　　　　　　　　?　　a　　　?　　　　　　　　　　　　　　　?　? 　　　　　　　m　　　m　　　l　　　　　　　　　　　　　　l　　m 　　　　　　?　?　　?　?　　ｃ　　　　　　　　　　　　　　　ａ　?　?　　　　　　　　　　　　　l　　l　l　　l　　　　　　　　　　　　　　　　　　l　　m 　　　　　ａ　　ｄ　ｂ　　ｅ　　　　　　　　　　　　　　　　　　ｄ　?　? 　　　　　　　　　　　　　　　　l　　　m 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｂ　　?　? 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　l　l 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｅ　ｃ　显然，要带权路径长ｗｐｌ最短，那么，此树的高度就应尽可能的小，由此可知将此树建成丰满ｎ叉树是最合理的，于是我们尽量使树每一层都为ｎ个分枝．　　对于这道题的情况，我们具体来分析．　　按照哈夫曼树的思想，首先从ｗ中取出权最小的三个值，即２，３，４，并以９（２＋３＋４）来代替，得到新的ｗ＝［９，７，５］；再将这三个值合并成９＋７＋５＝２１这个结点．于是得到三叉哈夫曼树如下：　　　　　　　　　　　　　　　　　　　　　　　　　　m 　　　　　　　　　　　?　　a　　? 　　　　　　　　　　l　　　l　　　m 　　　　　　　　　　ｄ　　　ｂ　?　a　? 　　　　　　　　　　　　　　　　l　l　l 　　　　　　　　　　　　　　　　ｅ　ｃ　ａ　　ｗｐｌ＝１＊７＋１＊５＋２＊２＋２＊３＋２＊４＝３０　　以０．．ｎ－１依次标记每个根结点的ｎ个分枝，则可以得到每个字符相对应的编码：　　　　ａ：２２　　　　ｂ：１　　　　ｃ：２１　　　　ｄ：０　　　　ｅ：２０　　我们发现对于这种情况恰巧每层均为ｎ个分枝，但事实上并非所有的ｎ叉哈夫曼树都可得到每层ｎ个分枝．例于当ｎ＝３，‖ｓ‖＝６时就不可能构成一棵每层都为三个分枝的三叉树．如何来处理这种情况呢？　　最简单的处理方式就是添加若干出现概率为０的空字符填补在ｎ叉树的最下一层，这些权为０的虚结点并无实际意义但却非常方全便于这棵ｎ叉树的建立．空字符的添加个数ａｄｄ的计算如下：　　ｙ＝‖ｓ‖　ｍｏｄ　（ｎ－１）　　ａｄｄ＝０　　　（ｙ＝１）　　　　　ａｄｄ＝１　　　（ｙ＝０）　　ａｄｄ＝ｎ－ｙ　（ｙ＞１）　　　　虚结点的加入使得权重最小的ｎ－ａｄｄ个字符构成了距根结点最远的分枝，使其它字符构成的ｎ叉树保持了丰满的ｎ叉结构．　　例：　ｎ＝３　　　　　　ｓ＝｛ａ，ｂ，ｃ，ｄ，ｅ，ｆ｝　　　　　ｗ＝［１，２，３，４，５，６｝　　则　ｙ：＝６　ｍｏｄ　（３－１）＝０　　　　ａｄｄ＝１　　于是构成ｎ叉树如下：　-为虚结点　　　　　　　　　　　　　　　　?　　　　　　　　　　　　　　?　　a　　? 　　　　　　　　　　　　l　　　l　　　　m 　　　　　　　　　　　　ｆ　　　ｅ　?　　a　　? 　　　　　　　　　　　　　　　　　　l　　l　　　m 　　　　　　　　　　　　　　　　　　ｄ　　ｃ　?　a　? 　　　　　　　　　　　　　　　　　　　　　　　ｂ　ａ　- 　　ｗｐｌ＝１＊６＋１＊５＋２＊４＋２＊３＋３＊２＋３＊１＋３＊０＝３３　　对应编码为：　　　　ａ：２２１　　　　ｂ：２２０　　　　ｃ：２１　　　　ｄ：２０　　　　ｅ：１　　　　ｆ：０

6，到底什么是哈夫曼树啊求例子

哈夫曼树是给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。例子：1、将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；2、在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；3、从森林中删除选取的两棵树，并将新树加入森林；4、重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。扩展资料：按照哈夫曼编码构思程序流程：1、切割的顺序是从上往下，直至数组中的元素全部出现在叶节点；2、我们思路正好相反，从数组中找出最小的两个元素作为最下面的叶节点，在向备选数组中存入这两个叶节点的和（这个新的和加入累加运算，这个和也就是所求的最小值的一部分，原因如上图）。3、以本题为例，备选数组中现有元素为4、上述2.3布重复执行直至备选数组中只有一个元素，此时累加结束，返回累加值即可5、求数组中的最小值，可以用小根堆进行提取最为方便；此题用到了贪心的思路，即用相同的策略重复执行，直至我们得到所需的结果。参考资料来源:搜狗百科——哈夫曼树

我们先看一个应用例子：假如你跟别人聊天，输入了“AFTER DATA EAR ARE ART AREA”，要发给对方，在电脑的世界里，最终都是要将相关的字符转换为0 1来表示的二进制来传输，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为为了获得传送报文的最短长度，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，可将每个字符的出现频率作为字符结点的权值赋予该结点上，显然字使用频率越小权值越小，权值越小叶子就越靠下。于是我们构造这颗二叉树的时候，应该先选择最小权值的点来构造树，新树的权值为左右子树的权值之和，然后新的权值放回到原来的权值序列中，再次选择两个权值最小的点来构造树，如此循环最后只剩下一棵树为止。我们以字符集为“A，E，R，T，F，D”，各字母出现的次数为首先选取两个最小权值的点构造树，新的权值放回到序列中，变为 / \1 1再次选择两个权值最小的点构造树，序列变为如下： / \ 2 3 / \ 1 1按照上面的规则直到只有一颗树为止 / \ / \ 2 3 4 5 / \1 1------------------------ / \ / \ 4 5 5 8 / \ 2 3 / \ 1 1------------------------ 22 / \ 9 13 / \ / \E4 R5 5 A8 / \ 2 T3 / \ F1 D1上面的的树便是哈夫曼树了（给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树）这颗树每一个“/” 默认为0， “\”为1，就可以得到叶子结点的编码：如上面F：1000 D：1001 A：11

这么明确的算法，肯定唯一，数如下： 1.00 / \ /0 \1 0.44 0.56 / \ / \ /0 \1 /0 \1 0.21 0.23 0.27 0.29 / \ /0 \1 0.13 0.16 / \ /0 \1 0.07 0.09编码：0.07:11100.09:11110.13:1100.21:000.23:010.27:10没有谁是谁的前缀，ok. 针对补充问题：不行，生成哈夫曼树时总是取最小的两个权值作为叶子。。针对补充问题002：上面那棵树，从下往上看，所有权值中最小的两个是0.07跟0.09，相加等0.16；原来的权值表成了：0.13，0.16(代替了0.07跟0.09),0.21，0.23，0.27；现在最小的两个是0.13，0.16，相加得到0.29；之前的权值表又成了：0.21，0.23，0.27，0.29(代替了0.13跟0.16)；现在最小的两个是0.21，0.23，相加得到0.44；之前的权值表又成了:0.27，0.29，0.44；接下来是一样的。

一、哈夫曼树的介绍Huffman Tree，中文名是哈夫曼树或霍夫曼树，它是最优二叉树。定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树。这个定义里面涉及到了几个陌生的概念，下面就是一颗哈夫曼树，我们来看图解答。(1) 路径和路径长度定义：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。例子：100和80的路径长度是1，50和30的路径长度是2，20和10的路径长度是3。(2) 结点的权及带权路径长度定义：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。例子：节点20的路径长度是3，它的带权路径长度= 路径长度 * 权 = 3 * 20 = 60。(3) 树的带权路径长度定义：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。例子：示例中，树的WPL= 1*100 + 2*50 + 3*20 + 3*10 = 100 + 100 + 60 + 30 = 290。比较下面两棵树上面的两棵树都是以左边的树WPL=2*10 + 2*20 + 2*50 + 2*100 = 360 右边的树WPL=290左边的树WPL > 右边的树的WPL。你也可以计算除上面两种示例之外的情况，但实际上右边的树就是二、哈夫曼树的图文解析假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，哈夫曼树的构造规则为：1. 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)； 2. 在森林中选出根结点的权值最小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； 3. 从森林中删除选取的两棵树，并将新树加入森林； 4. 重复(02)、(03)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。以第1步：创建森林，森林包括5棵树，这5棵树的权值分别是5,6,7,8,15。第2步：在森林中，选择根节点权值最小的两棵树(5和6)来进行合并，将它们作为一颗新树的左右孩子(谁左谁右无关紧要，这里，我们选择较小的作为左孩子)，并且新树的权值是左右孩子的权值之和。即，新树的权值是11。然后，将"树5"和"树6"从森林中删除，并将新的树(树11)添加到森林中。第3步：在森林中，选择根节点权值最小的两棵树(7和8)来进行合并。得到的新树的权值是15。然后，将"树7"和"树8"从森林中删除，并将新的树(树15)添加到森林中。第4步：在森林中，选择根节点权值最小的两棵树(11和15)来进行合并。得到的新树的权值是26。然后，将"树11"和"树15"从森林中删除，并将新的树(树26)添加到森林中。第5步：在森林中，选择根节点权值最小的两棵树(15和26)来进行合并。得到的新树的权值是41。然后，将"树15"和"树26"从森林中删除，并将新的树(树41)添加到森林中。此时，森林中只有一棵树(树41)。这棵树就是我们需要的哈夫曼树！三、哈夫曼树的基本操作哈夫曼树的重点是如何构造哈夫曼树。本文构造哈夫曼时，用到了以前介绍过的"(二叉堆)最小堆"。下面对哈夫曼树进行讲解。1. 基本定义[html]view plaincopyprintHuffmanNode是哈夫曼树的节点类。[html]view plaincopyprintHuffman是哈夫曼树对应的类，它包含了哈夫曼树的根节点和哈夫曼树的相关操作。2. 构造哈夫曼树[html]view plaincopyprint首先创建最小堆，然后进入for循环。每次循环时：(1) 首先，将最小堆中的最小节点拷贝一份并赋值给left，然后重塑最小堆(将最小节点和后面的节点交换位置，接着将"交换位置后的最小节点"之前的全部元素重新构造成最小堆)； (2) 接着，再将最小堆中的最小节点拷贝一份并将其赋值right，然后再次重塑最小堆； (3) 然后，新建节点parent，并将它作为left和right的父节点； (4) 接着，将parent的数据复制给最小堆中的指定节点。四、哈夫曼树的完整源码1. 哈夫曼树的节点类(HuffmanNode.java)[html]view plaincopyprint2. 哈夫曼树的实现文件(Huffman.java)[html]view plaincopyprint3. 哈夫曼树对应的最小堆(MinHeap.java)[html]view plaincopyprint4. 哈夫曼树的测试程序(HuffmanTest.java)[html]view plaincopyprint五个字符：a,b,c,d,e,它们出现的的频率为8，14，10，4，18构造相应的哈夫曼树，求出每个字符的哈夫曼编码：哈夫曼树：54/ \22 32/ \ / \c10 12 b14 e18/ \d4 a8哈夫曼编码：a:011 b:10 c:00 d:010 e:11今天做题的时候，遇到了一个关于哈夫曼树的题，由于一直不是很明白哈夫曼树的构造过程，所以找了很多资料都不是特别清楚的，直到我遇到了这篇文章，哈哈，在此分享给大家哦！注意：哈夫曼树并不唯一，但带权路径长度一定是相同的。（1）8个结点的权值大小如下：（2）从19，21，2，3，6，7，10，32中选择两个权小结点。选中2，3。同时算出这两个结点的和5。（3）从19，21，6，7，10，32，5中选出两个权小结点。选中5，6。同时计算出它们的和11。（4）从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。（BTW：这时选出的两个数字都不是已经构造好的二叉树里面的结点，所以要另外开一棵二叉树；或者说，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。）（4）从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。（BTW：这时选出的两个数字都不是已经构造好的二叉树里面的结点，所以要另外开一棵二叉树；或者说，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。）（4）从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。（BTW：这时选出的两个数字都不是已经构造好的二叉树里面的结点，所以要另外开一棵二叉树；或者说，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。）（5）从19，21，32，11，17中选出两个权小结点。选中11，17。同时计算出它们的和28。（6）从19，21，32，28中选出两个权小结点。选中19，21。同时计算出它们的和40。另起一颗二叉树。（7）从32，28， 40中选出两个权小结点。选中28，32。同时计算出它们的和60。（8）从 40， 60中选出两个权小结点。选中40，60。同时计算出它们的和100。好了，此时哈夫曼树已经构建好了。这是原作者的链接哦，我觉得还不错呢，大家可以去看看的！注意：哈夫曼树并不唯一，但带权路径长度一定是相同的。（1）8个结点的权值大小如下：（2）从19，21，2，3，6，7，10，32中选择两个权小结点。选中2，3。同时算出这两个结点的和5。（3）从19，21，6，7，10，32，5中选出两个权小结点。选中5，6。同时计算出它们的和11。（4）从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。（BTW：这时选出的两个数字都不是已经构造好的二叉树里面的结点，所以要另外开一棵二叉树；或者说，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。）（4）从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。（BTW：这时选出的两个数字都不是已经构造好的二叉树里面的结点，所以要另外开一棵二叉树；或者说，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。）（4）从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。（BTW：这时选出的两个数字都不是已经构造好的二叉树里面的结点，所以要另外开一棵二叉树；或者说，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。）（5）从19，21，32，11，17中选出两个权小结点。选中11，17。同时计算出它们的和28。（6）从19，21，32，28中选出两个权小结点。选中19，21。同时计算出它们的和40。另起一颗二叉树。（7）从32，28， 40中选出两个权小结点。选中28，32。同时计算出它们的和60。（8）从 40， 60中选出两个权小结点。选中40，60。同时计算出它们的和100。好了，此时哈夫曼树已经构建好了。