哈夫曼树的基本概念是什么？

（1）结点路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。

（2）路径长度：从一个结点到另一个结点所经过的分支数目。

（2）树的路径长度：从根结点到树中每一结点的路径长度之和。

（4）结点的权：赋予树中某结点的一个有某种意义的数量值。

（5）结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。

（6）树的带权路径长度：树中所有叶子结点的带权路径长度之和，记为WPL＝w1？l1＋w2？l2＋…＋wn？ln＝∑wi？li（i＝1，2，…，n），其中，n为叶子结点的个数；wi为第i个结点的权值；li为第i个结点的路径长度。

（7）哈夫曼树（最优二叉树）：在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树（最优二叉树）。

如图6－40所示，各树权值都由2，2，4，11组成，但构成的二叉树的带权路径长度WPL不同，图1所示的树的带权路径长度WPL＝11？1＋4？2＋2？2＋2？2＝24；图1（b）所示的树的带权路径长度WPL＝2？1＋2？2＋4？2＋11？2＝52；图1所示的树的带权路径长度WPL＝2？2＋11？2＋2？2＋4？2＝40。在这三棵二叉树中，图6－40（a）所示的树的带权路径长度WPL最小，因此它是最优二叉树。

具有不同带权路径长度的二叉树

哈夫曼树是给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

例子：

1、将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

2、 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

3、从森林中删除选取的两棵树，并将新树加入森林；

4、重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

扩展资料：

按照哈夫曼编码构思程序流程：

1、切割的顺序是从上往下，直至数组中的元素全部出现在叶节点；

2、我们思路正好相反，从数组中找出最小的两个元素作为最下面的叶节点，在向备选数组中存入这两个叶节点的和（这个新的和加入累加运算，这个和也就是所求的最小值的一部分，原因如上图）。

3、以本题为例，备选数组中现有元素为{30，30}，再次取出两个最小元素进行求和，得到新的元素，回归备选数组并记入累加。

4、上述2.3布重复执行直至备选数组中只有一个元素，此时累加结束，返回累加值即可

5、求数组中的最小值，可以用小根堆进行提取最为方便；此题用到了贪心的思路，即用相同的策略重复执行，直至我们得到所需的结果。

参考资料来源:百度百科——哈夫曼树

一、 一些基本概念

1、 路径长度

树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目为路径长度

上图中，从1到4的路径长度为2，从7 到3的路径长度为4

2、 树的路径长度

从树根到每一个结点的路径长度之和，这种路径长度最短的树是完全二叉树

上图中，树的路径长度为：1 + 1 + 2 + 2 + 3 + 3 = 12

3、 权

若将树中结点赋一个有某种含义的数值，则这个数值称为该结点的权

4、 结点的带权路径长度

从根结点到该结点间的路径长度与该结点的权的乘积

2、 树的路径长度

从树根到每一个结点的路径长度之和，这种路径长度最短的树是完全二叉树

上图中，树的路径长度为：1 + 1 + 2 + 2 + 3 + 3 = 12

3、 权

若将树中结点赋一个有某种含义的数值，则这个数值称为该结点的权

4、 结点的带权路径长度

从根结点到该结点间的路径长度与该结点的权的乘积

2、 树的路径长度

从树根到每一个结点的路径长度之和，这种路径长度最短的树是完全二叉树

上图中，树的路径长度为：1 + 1 + 2 + 2 + 3 + 3 = 12

3、 权

若将树中结点赋一个有某种含义的数值，则这个数值称为该结点的权

4、 结点的带权路径长度

从根结点到该结点间的路径长度与该结点的权的乘积

上图中，结点d的带权路径长度为：4 X 3 = 12

5、 树的带权路径长度WPL

树中所有带权结点的路径长度之和

上图中，树的带权路径长度WPL为：7 X 1 + 5 X 2 + 2 X 3 + 4 X 3 = 35

6、 哈夫曼树（最优二叉树）

有n个叶子结点的二叉树，每个叶子结点均带权，带权路径长度WPL最小的二叉树即为哈夫曼树

二、 哈夫曼树的构造

1、 给定n个权值{w1, w2, w3 …… wn}构成 n棵二叉树的集合F = {T1, T2, T3 …… Tn}, 其中每棵树只有权值为Wi的根节点，其左右子树均为空。

例如，给定结点的权值为7 5 2 4，构造出树如下：

2、 在二叉树集合F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且新的二叉树的根节点的权值为其左右子树结点的权值之和。

3、 在F中删除这两棵树，并将新的二叉树加入到F中

三、 哈夫曼树的应用--得到最佳判定算法

例如，编制一个将百分制转换成五分制的程序，判定过程可用判定树来表示

如果分数小于60，我们做1次判断即可；如果分数为60～70，需要判断2次；如果分数为70～80，需要判断3次；如果分数为80～90，需要判断4次；如果分数为90～100，需要判断5次。

在实际中，学生成绩在五个等级上的分布上不均匀的，假设分布规律如下：

这样对100个数据进行判断，次数为：100 X 5% X 4 + 100 X 15% X 3 + 100 X 40% X 1 + 100 X 30% X 2 + 100 X 10% X 4 = 205

这样可以使大部分数据经过教少的比较次数得出结果。把每个判定框内的两次比较分开，得到最终的判定树，如下：

哈夫曼编码的基本思想是以字符的使用频率作为权，构造一棵哈夫曼树，然后利用哈夫曼树对字符进行编码。这棵哈夫曼树，是将所要编码的字符作为叶子结点，该字符在文件中的使用频率作为叶子结点的权，以自底向上的方式，通过n-1次合并运算后构造出一棵树，权值越大的叶子离根越近。

4、 哈夫曼树的数据结构

哈夫曼树中没有度为1的结点，则一棵有n个叶子结点的哈夫曼树共有2n – 1个结点（n – 1次合并，每次产生一个新结点），对每个结点而言，需要知道双亲和孩子的信息，因此设定的存储结构如下

5、 构造哈夫曼树

举例：

有一些字符和他们的使用频率，如下图：

初始化哈夫曼树

对应的树

i=0时，j=0；j<6；找双亲为−1，权值最小的两个数：

第一次循环后

对应的哈夫曼树

对应的哈夫曼树

参考 http://blog.csdn.net/rainchxy/article/details/78647182

---