数据结构-非线性结构-树形结构：有序树 -＞二叉树 -＞哈夫曼树 / 霍夫曼树（Huffman Tree）【根据所有叶子节点的权值构造出的 -＞带权值路径长度最短的二叉树，权值较大的结点离根较近】

本文主要是介绍数据结构-非线性结构-树形结构：有序树 -＞二叉树 -＞哈夫曼树 / 霍夫曼树（Huffman Tree）【根据所有叶子节点的权值构造出的 -＞带权值路径长度最短的二叉树，权值较大的结点离根较近】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述
哈夫曼树概念：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。

哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

一、相关概念

二叉树：每个节点最多有2个子树的有序树，两个子树分别称为左子树、右子树。有序的意思是：树有左右之分，不能颠倒

叶子节点：一棵树当中没有子结点的结点称为叶子结点，简称“叶子”

路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和

树的高度：树中结点的最大层次。包含n个结点的二叉树的高度至少为log2 (n+1)。

二、哈夫曼树的构造算法

把 $\{W_1,W_2,W_3 \dots W_n\}$ 看成n棵树的森林
在森林中选择两个根节点权值最小的树进行合并，作为一颗新树的左右子树，新树的根节点权值为左右子树的和
删除之前选择出的子树，把新树加入森林
重复2-3步骤，直到森林只有一棵树为止，概树就是所求的哈夫曼树

注意：哈夫曼树并不唯一，但带权路径长度一定是相同的。

三、哈夫曼树的构造过程

8个结点的权值大小如下：
从19，21，2，3，6，7，10，32中选择两个权小结点。选中2，3。同时算出这两个结点的和5。

在这里插入图片描述

从19，21，6，7，10，32，5中选出两个权小结点。选中5，6。同时计算出它们的和11。

在这里插入图片描述

从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。
【这时选出的两个数字都不是已经构造好的二叉树里面的结点，所以要另外开一棵二叉树；或者说，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。】
从19，21，32，11，17中选出两个权小结点。选中11，17。同时计算出它们的和28。
从19，21，32，28中选出两个权小结点。选中19，21。同时计算出它们的和40。另起一颗二叉树。
从32，28， 40中选出两个权小结点。选中28，32。同时计算出它们的和60。

在这里插入图片描述

从 40， 60中选出两个权小结点。选中40，60。同时计算出它们的和100。好了，此时哈夫曼树已经构建好了。

可见：

权重越大，距离根节点越近
叶子的个数为n，构造哈夫曼树中新增的节点的个数为n-1

四、哈夫曼编码

在数据通信中，需要将传送的文字转换成二进制的字符串，用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进行编码发送

但是很明显，上述的编码的方式并不是最优的，即整理传送的字节数量并不是最少的。

为了提高数据传送的效率，同时为了保证【前缀编码】,可以使用哈夫曼树生成哈夫曼编码解决问题。【任一字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码】

可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，显然字使用频率越小权值越小，权值越小叶子就越靠下，于是频率小编码长，频率高编码短，这样就保证了此树的最小带权路径长度效果上就是传送报文的最短长度

因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。

利用哈夫曼树来设计二进制的前缀编码，