哈夫曼树的构造原理,哈夫曼树的构建过程

哈夫曼树的构造原理,哈夫曼树的构建过程详细介绍

本文目录一览： 哈夫曼树的构造规则

哈夫曼树的构造规则是若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
哈夫曼树的数据为使不等长编码为前缀编码(即要求一个字符的编码不能是另一个字符编码的前缀)，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，显然字使用频率越小权值越小，权值越小叶子就越靠下。
于是频率码长，频率高编码短，这样就保证了此树的最小带权路径长度效果上就是传送报文的最短长度。
因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。

【离散数学】树（一）哈夫曼编码基本原理

本节我们将介绍以下内容：
给定 n 个叶子结点，每个结点带权值，构造一棵二叉树，如果带权路径长度最短，则称为哈夫曼树（最优二叉树），权值最大的结点最接近根结点
给定一组符号S及其权值W（出现的概率）
根据这张表格，我们来构造一棵哈夫曼树
哈夫曼压缩是一种能够大幅度压缩自然语言文件空间的数据压缩技术，不再使用8位二进制数表示每一个字符，而是用较少的比特表示出现频率高的字符，而用较多的比特表示出现频率低的字符
在我们构造出哈夫曼树后，将所有的权值删去，并给每条边赋值0或1 在此我们定义 左 0 右 1

据此，我们尝试解码一个短串：
011011111
从根结点开始，遇到 0 ，向左下移动一次，得到字符 A
开始解码下一个字符，从根结点开始，遇到2个 1 ，向右下移动2次，遇到 0 ，向左下移动一次，得到字符 C
开始解码下一个字符，从根结点开始，遇到5个 1 ，向右下移动5次，得到字符 E
所以我们解码得到的字符为 ACE
关于哈夫曼编码的基本原理就介绍到此了，谢谢大家！

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

一、哈夫曼树的介绍
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。
比较下面两棵树
上面的两棵树都是以{10, 20, 50, 100}为叶子节点的树。
左边的树WPL=2*10 + 2*20 + 2*50 + 2*100 = 360 右边的树WPL=290
左边的树WPL > 右边的树的WPL。你也可以计算除上面两种示例之外的情况，但实际上右边的树就是{10,20,50,100}对应的哈夫曼树。至此，应该对哈夫曼树的概念有了一定的了解了，下面看看如何去构造一棵哈夫曼树。
二、哈夫曼树的图文解析
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，哈夫曼树的构造规则为：
1. 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)； 2. 在森林中选出根结点的权值最小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； 3. 从森林中删除选取的两棵树，并将新树加入森林； 4. 重复(02)、(03)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
以{5,6,7,8,15}为例，来构造一棵哈夫曼树。
第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 plain
copy
print
HuffmanNode是哈夫曼树的节点类。
[html]
view plain
copy
print
Huffman是哈夫曼树对应的类，它包含了哈夫曼树的根节点和哈夫曼树的相关操作。
2. 构造哈夫曼树
[html]
view plain
copy
print
首先创建最小堆，然后进入for循环。
每次循环时：
(1) 首先，将最小堆中的最小节点拷贝一份并赋值给left，然后重塑最小堆(将最小节点和后面的节点交换位置，接着将"交换位置后的最小节点"之前的全部元素重新构造成最小堆)； (2) 接着，再将最小堆中的最小节点拷贝一份并将其赋值right，然后再次重塑最小堆； (3) 然后，新建节点parent，并将它作为left和right的父节点； (4) 接着，将parent的数据复制给最小堆中的指定节点。
四、哈夫曼树的完整源码
1. 哈夫曼树的节点类(HuffmanNode.java)
[html]
view plain
copy
print
2. 哈夫曼树的实现文件(Huffman.java)
[html]
view plain
copy
print
3. 哈夫曼树对应的最小堆(MinHeap.java)
[html]
view plain
copy
print
4. 哈夫曼树的测试程序(HuffmanTest.java)
[html]
view plain
copy
print
五个字符：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。 好了，此时哈夫曼树已经构建好了。
我们先看一个应用例子：假如你跟别人聊天，输入了“AFTER DATA EAR ARE ART AREA”，要发给对方，在电脑的世界里，最终都是要将相关的字符转换为0 1来表示的二进制来传输，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}。现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、011、100、101对“A，E，R，T，F，D”进行编码发送，当对方接收报文时再按照三位一分进行译码。然而我们发现不同字符出现的次数是不一样的，显然出现次数多的字符编码短一些，出现字符小的编码长一些，我们可以做到使整天编码长度变小。
为了获得传送报文的最短长度，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，可将每个字符的出现频率作为字符结点的权值赋予该结点上，显然字使用频率越小权值越小，权值越小叶子就越靠下。
于是我们构造这颗二叉树的时候，应该先选择最小权值的点来构造树，新树的权值为左右子树的权值之和，然后新的权值放回到原来的权值序列中，再次选择两个权值最小的点来构造树，如此循环最后只剩下一棵树为止。
我们以字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}为例构造哈夫曼树。
首先选取两个最小权值的点构造树，新的权值放回到序列中，变为
{ 2 , 3, 4 , 5, 8 }为了能快速查看最小的两个点，从小到大排序了一下。
/ \
1 1
再次选择两个权值最小的点构造树，序列变为如下：
{ 4, 5 , 5, 8 }
/ \
2 3
/ \
1 1
按照上面的规则直到只有一颗树为止
{ 5, 8 9 }
/ \ / \
2 3 4 5
/ \
1 1
------------------------
{ 9 , 13 }
/ \ / \
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
哈夫曼树是给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
例子：
1、将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
2、 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
3、从森林中删除选取的两棵树，并将新树加入森林；
4、重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
扩展资料：
按照哈夫曼编码构思程序流程：
1、切割的顺序是从上往下，直至数组中的元素全部出现在叶节点；
2、我们思路正好相反，从数组中找出最小的两个元素作为最下面的叶节点，在向备选数组中存入这两个叶节点的和（这个新的和加入累加运算，这个和也就是所求的最小值的一部分，原因如上图）。
3、以本题为例，备选数组中现有元素为{30，30}，再次取出两个最小元素进行求和，得到新的元素，回归备选数组并记入累加。
4、上述2.3布重复执行直至备选数组中只有一个元素，此时累加结束，返回累加值即可
5、求数组中的最小值，可以用小根堆进行提取最为方便；此题用到了贪心的思路，即用相同的策略重复执行，直至我们得到所需的结果。
参考资料来源:百度百科——哈夫曼树

哈夫曼树的构建过程

哈夫曼树:
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
哈夫曼树的构造：
假设给定的权值如下：3,5,7,8,10,15；
首先取集合中最小的两个数：3+5=8，再删除集合中3和5的值，把8放入原集合,
原集合变成:7,8,8,10,15；
8
/ \
3 5
再从7,8,8,10,15中再取2个最小的数构成一个树
15
/ \
8 7
/ \
3 5
再从8,10,15,15中再取2个最小的数构成一个树:
18
/ \
8 10
再从15,15,18中取两个最小数:15,15,构成树:
30
/ \
15 15
/ \
8 7
/ \
3 5
最后把18,30构成树(此时集合中已经没元素了，就形成了哈夫曼树):
48
/ \
30 18
/ \ / \
15 15 8 10
/ \
8 7
/ \
3 5
希望你能看懂！！

哈夫曼树（理论）

路径长度：从树中一个节点到另一个节点需要经过的分支个数。
树的路径长度：从根节点出发，到每一个叶子节点的路径长度之和。
带权路径长度：从根节点出发，到每一个叶子节点的路径长度乘上叶子节点的权重之和。

哈夫曼树就是带权路径长度最小的二叉树。那么哈夫曼数有什么优点呢？由于哈夫曼树是带权路径长度最小的二叉树，意味着所有权重大的叶子节点一定在树的上层。那么在比较过程中（每一个节点就是一次比较），大部分数据只需要经过几次比较就可以得出结果，只有少数数据需要比较多次，这样可以明显减少比较次数。

那么如果构造出一颗哈夫曼树？
（1）把所有有权值的叶子节点按照从小到大的顺序排列。
（2）将权值最小的两个叶子节点取出来构成一颗二叉树，权值最小的为二叉树的左孩子，将这颗二叉树看成一个新的叶子节点，权值为左右孩子权值相加之和，重新加入队列排序。
（3）不断重复（2）的过程直到队列中的节点个数为1之时，我们便得到了一颗哈夫曼树。

“哈夫曼树”的建立方法是什么？

(1) 将k1、k2、…，kn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。例如，需传送的报文为“AFTER DATA EAR ARE ART AREA”，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}。现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、011、100、101对“A，E，R，T，F，D”进行编码发送，当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符，则固定编码长度为5。然而，传送报文时总是希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。
为使不等长编码为前缀编码(即要求一个字符的编码不能是另一个字符编码的前缀)，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，显然字使用频率越小权值越小，权值越小叶子就越靠下，于是频率小编码长，频率高编码短，这样就保证了此树的最小带权路径长度效果上就是传送报文的最短长度。因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 k1、k2、…、kn，则哈夫曼树的构造规则为：
(1) 将k1、k2、…，kn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
哈夫曼静态编码：它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，（用4Bytes的长度存储频率值，频率值的表示范围为0--2^32-1，这已足够表示大文件中字符出现的频率了）以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。
哈夫曼动态编码：动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。

哈夫曼树及应用

在计算机和互联网技术中，文本压缩就是一个非常重要的技术。玩电脑的人几乎都会应用压缩和解压缩软件来处理文档。因为它除了可以减少文档在磁盘上的空间外，还有重要的一点， 就是我们可以在网络上以压缩的形式传输大量数据，使得保存和传递都更加高效。

那么压缩而不出错是如何做到的呢?简单说，就是把我们要压缩的文本进行重新编码，以减少不必要的空间。尽管现在最新技术在编码上已经很好很强大，但这一切都来自于曾经的技术积累，我们今天就来介绍一下最基本的压缩编码方法-赫夫曼编码。

在介绍赫夫曼编码前，我们必须得介绍赫夫曼树，而介绍赫夫曼树，我们不得不提这样一个人，美国数学家赫夫曼(David Huffman)， 也有的翻译为哈夫曼。他在1952年发明了赫夫曼编码，为了纪念他的成就，于是就把他在编码中用到的特殊的C叉树称之为赫夫曼树，他的编码方法称为赫夫曼编码。也就是说，我们现在介绍的知识全都来自于近60年前这位伟大科学家的研究成果，而我们平时所用的压缩和解压缩技术也都是基于赫夫曼的研究之上发展而来，我们应该要记住他。

设有n个权值{w1,w2,…,wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi，则wpl最小的二叉树叫哈夫曼树。

(1). 初始化：根据给定的n个权值{w1,w2,…,wn}，构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti只有一个带权为wi的根结点，其左右子树均空。

(2). 选取与合并：在 F 中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。

(3). 删除与加入：在 F 中删除这两棵树，同时将新得到的二叉树加入 F 中。

(4). 重复(2)和(3)，直到 F 只含一棵树为止。这棵树便是所求的哈夫曼树。

w={5, 29, 7, 8, 14, 23, 3, 11}的构造过程

一般地， 设需要编码的字符集为{ d1,d2,···,dn }，各个字符在电文中出现的次数或频率集合为{ W1,W2,···,Wn},以d1,d2,···,dn作为叶子结点，以W1,W,···,Wn作为相应叶子结点的权值来构造一棵哈夫曼树。规定哈夫曼树的左分支代表0，右分支代表1,则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，这就是哈夫曼编码。

学习哈夫曼树和哈夫曼编码有助于初步理解数据压缩原理。

数据结构怎样构造三叉哈夫曼树？

哈夫曼树构造是将所有的点看做森林的树，选择两个最小权值的点来构造树，直到森林只有一个树为止，这样推三叉哈夫曼树是选择三个最小权值的点来构造树，作为左中右三个子树，根结点的权值是三个结点的权值的和。

哈夫曼树怎样构造编码？