哈夫曼树type
status
date
slug
summary
tags
category
icon
password
Property
哈夫曼树是一种最基本的压缩编码方法。对于如图所示的两棵二叉树，每个叶子节点都带有权值:
从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称作路径长度。例如，树 a 中根节点到结点 D 的路径长度为 4，树 b 中根节点到结点 D 的路径长度为 2。树的路径长度就是从树根到每一结点的路径长度之和。因此，树 a 的路径长度就为 20，树 b 的路径长度为 16。
如果考虑到带权的结点，结点的带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。
例如，树a的，树b的。
其中，【带权路径长度(WPL)】最小的二叉树称作【哈夫曼树】，也称作最优二叉树。
将树 a 转化为哈夫曼树的步骤如下：
- 首先把带有权值的叶子结点按照从小到大的顺序排列成一个有序序列，即：A5，E10，B15，D30，C40。
- 然后取头两个最小权值的结点作为一个新结点 N1 的两个孩子结点，注意相对较小的是左孩子，这里 A 是 N1 的左孩子，E 为 N1 的右孩子。则新节点的权值为两个叶子结点的权值的和，即 5+10=15。
- 然后将 N1 替换 A 与 E，插入有序序列中，保持从小到大的顺序排列。即 N115，B15，D30，C40。
- 重复步骤 2。将 N1 与 B 作为一个新的结点 N2 的两个子结点。N2 的权值为 15+15=30。
- 重复上述步骤，直到排列完成。
此时哈夫曼树的
哈夫曼树最早应用于电文编码。一般地，设需要编码的字符集为，各个字符在电文中出现的次数或者频率集合为，以 作为叶子结点，以作为相应叶子结点的权值来构造一棵哈夫曼树。规定哈夫曼树的左分支代表 0，右分支代表 1，则从根结点到叶子结点所经过的路径分支组成的 0 和 1 的序列为该结点对应字符的编码，这就是哈夫曼编码。
其编码过程如下图所示：
哈夫曼编码不同于 ASCII 和 Unicode 这些字符编码，这些字符集中的码长都采用的是长度相同的编码方案，而哈夫曼编码使用的是变长编码，而且哈夫曼编码满足立刻可解码性（就是说任一字符的编码都不会是另一个更长字符编码的前缀），这样当一个字符的编码中的位被接收时，可以立即进行解码而无须等待之后的位来决定是否存在另一个合法的更长的编码。例如，下面两个表中，表 1 不满足立刻可解码性，而表 2 则满足：
因为哈夫曼编码中每一个字符都位于哈夫曼树的叶子节点中，所以不会存在路径包含问题，这也就是立刻可解码性的原因。
代码实现
哈夫曼树的节点定义如下：
在构建哈夫曼树的过程中，不断取出序列中权值最小的两个节点，因此，可以使用小根堆来进行构建，其定义如下：
构建哈夫曼树的代码如下：
构建哈夫曼编码的过程可以采用前序遍历的方式进行实现，其代码如下：
编码的代码如下：
解码的代码如下：