21 哈夫曼（Huffman）树：将数据压缩后再传输更省带宽
你好，我是王健伟。
前面我们已经讲过了很多种二叉树，这节我想再和你分享一种特殊的二叉树——哈夫曼树（Huffman Tree）。
哈夫曼树也有人称为霍夫曼树或最优二叉树。先说点有趣的，哈夫曼（David Huffman）是美国的一位数学家。他在1952年发明了哈夫曼编码（一种二进制编码），该编码中用到了一种特殊的二叉树，人们为了纪念他的成就，将所用到的特殊二叉树称为哈夫曼树。
当然，知道这个可不算真正了解哈夫曼树，在了解哈夫曼树之前，首先要学习几个基本概念。
基本术语、概念
首先，节点的权。它指的是给树中的各个节点一个数值，用来表示某种现实含义。比如用1-10之间的数字表示某个节点的重要性或者表示该节点出现的频率等，这个数字就叫做节点的权（权值）。
如图1所示：
再来，什么是从根节点到某节点的路径长度？这个指的是从根节点到该节点所经过的路径段数。比如对于权值为5的节点（是个叶子节点），从根节点到该节点的路径长度为3。换句话说，从权值为5的节点向根节点回溯要经过3个前辈节点，所以从根节点到权值为5的节点的路径长度为3。
如图2所示：
接下来就是2个重要概念的铺垫了。
一个是节点的带权路径长度。它的英文是Weighted Path Length（缩写WPL）。节点的带权路径长度表示从根节点到该节点的路径长度与该节点权值的乘积。比如对于权值为5的叶子节点，从根节点到该节点的路径长度为3，所以该节点的带权路径长度为3*5 = 15。
另一个是树的带权路径长度。树的带权路径长度是树中所有叶子节点的带权路径长度之和。图2这棵树的带权路径长度是(1*3)+(3*3)+(5*3)+(10*3)=57。
看一看图3中的4棵树的带权路径长度，在图3中：
- 第1棵树的WPL为(1*2)+(3*2)+(5*2)+(10*2)=38
- 第2棵树的WPL为(5*2)+(1*3)+(3*3)+(10*1)=32
- 第3棵树的WPL为(5*3)+(10*3)+(1*2)+(3*1)=50
- 第4棵树的WPL为(1*2)+(3*3)+(5*2)+(10*3)=51
基础概念了解之后，我们来看看它们和哈夫曼树的关系。通过前面的计算发现，图3中的第2棵树的WPL值最小。无论是什么形状的二叉树，只要叶子节点是1、3、5、10，那么WPL值最小也不会低于32。所以WPL值为32的这棵二叉树就是哈夫曼树（带权路径长度最小）。
现在，我们可以给出哈夫曼树的正式定义：在含有n个带权叶节点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称为最优二叉树。当然，哈夫曼树也不唯一，比如图3的第2棵树是一棵哈夫曼树，假如把该树的权值为1和3的节点互换后得到的二叉树WPL依旧为32，也是一棵哈夫曼树。所以包含相同叶子节点的哈夫曼树也许会有多种形态。
哈夫曼树的构造及相关的代码实现
如果给定n个叶子节点，如何构造包含这n个叶子节点的哈夫曼树呢？我们说下几个步骤。
- 将这n个节点分别作为n棵仅含一个节点（根节点）的二叉树，这样就构成了一个二叉树集合F。
- 构造一个新节点，在集合F中选取两棵根节点权值最小的树作为这个新节点的左右子树，这里谁左谁右顺序任意，以此构造一棵新二叉树。这个新节点的权值是左右两棵子树根节点的权值之和。
- 从集合F中删除刚刚选取的两棵树，并将新得到的树加入到集合F中。
- 重复上面的2个步骤，直到集合F中只剩下一棵树为止，这棵树就是哈夫曼树。
我们通过图片理解一下整个步骤。如图4，有权值分别为1、2、2、4、8的节点a、b、c、d、e，构成了一个二叉树集合F：
在集合F中，选取两棵根节点权值最小的树a和b，当然，a和c也行，因为b和c权值相同。然后构造一棵新二叉树，新二叉树根节点的权值是1+2=3，如图5所示：
接着选取根节点权值为2和3的二叉树构造一棵新二叉树，其根节点的权值是2+3=5，如图6所示：
接着选取根节点权值为4和5的二叉树构造一棵新二叉树，其根节点的权值是4+5=9，如图7所示：
接着选取根节点权值为8和9的树构造一棵新二叉树，其根节点的权值是8+9=17，如图8所示：
目前集合F中只剩下一棵树了，所以这棵树就是哈夫曼树。这棵哈夫曼树的WPL为(8*1)+(4*2)+(2*3)+(2*4)+(1*4)=34。
观察图8，我们不难发现哈夫曼树的一些特性。
- 初始给出的节点都是哈夫曼树的叶子节点。
- 权值越大的叶子节点（比如节点e）到根节点的路径长度越小，权值越小的叶子节点（比如节点a、b）到根节点的路径长度越大。
- 因为有n个叶子节点，并且一共进行了n-1次的两两合并最终得到哈夫曼树，而每合并一次多出一个节点（n-1次合并就会多出n-1个节点），所以哈夫曼树的节点总数是n+(n-1)=2n-1，这个数据在编程的时候会用到。
- 哈夫曼树中没有度为1的节点。注意这里，节点拥有的子树数目，叫做节点的度。因为构造哈夫曼树的过程中，每个新节点都是有左右子树的。
- 哈夫曼树的子树仍旧是哈夫曼树。
- 哈夫曼树并不是唯一的，但相同叶子节点的哈夫曼树的WPL值一定是相等的。
哈夫曼树的代码实现并不复杂，因为给定叶子节点权值以及叶子节点数量后，整个哈夫曼树的节点数量是可以确定的（2n-1），因此，可以创建动态数组来保存哈夫曼树。你可以参考下面的代码。
//哈夫曼树的节点
struct HFMTreeNode
{
int weight; //权值
int parent; //父亲（数组下标值）
int lchild; //左孩子（数组下标值）
int rchild; //右孩子（数组下标值）
};
//哈夫曼树：用一个数组来保存哈夫曼树
class HFMTree
{
public:
HFMTree(int nodecount, int* pweight) //构造函数
//参数nodecount代表要创建的哈夫曼树的叶子节点的数量
//pWeight代表叶子节点的权重数组
{
m_length = nodecount;
int iMaxNodeCount = 2 * m_length - 1;
m_data = new HFMTreeNode[iMaxNodeCount]; //哈夫曼树的节点总数是2n-1（n代表哈夫曼树的叶子节点数量）
for (int i = 0; i < iMaxNodeCount; ++i)
{
m_data[i].parent = -1; //-1标记未被使用
m_data[i].lchild = -1;
m_data[i].rchild = -1;
}
for (int i = 0; i < m_length; ++i)
{
m_data[i].weight = pweight[i];
}
}
~HFMTree() //析构函数
{
delete [] m_data;
}
public:
//真正的开始创建哈夫曼树
void CreateHFMTree()
{
int idx1 = 0;
int idx2 = 0;
int iMaxNodeCount = 2 * m_length - 1; //2n-1是整个哈夫曼树的节点数量
int initlength = m_length;
for (int i = initlength; i < iMaxNodeCount; ++i)
{
SelectTwoMinValue(idx1, idx2);
m_data[i].weight = m_data[idx1].weight + m_data[idx2].weight; //新节点的权值等于左右孩子
m_data[i].lchild = idx1;
m_data[i].rchild = idx2;
m_data[idx1].parent = i;
m_data[idx2].parent = i;
m_length++; //SelectTwoMinValue()函数要用到该值
} //end for i
return;
}
//前序遍历二叉树(根左右)
void preOrder(int idx)
{
if (idx != -1)
{
cout << m_data[idx].weight <<" ";
preOrder(m_data[idx].lchild);
preOrder(m_data[idx].rchild);
}
}
//获取树中节点数量
int GetLength()
{
return m_length;
}
private:
//选择两个根权重最小的节点，通过引用返回这个节点所在的下标
void SelectTwoMinValue(int& rtnIdx1, int& rtnIdx2)
{
int minval1 = INT_MAX;
int minval2 = INT_MAX;
//找最小值
for (int i = 0; i < m_length; ++i)
{
if (m_data[i].parent == -1) //父标记未被使用
{
if (minval1 > m_data[i].weight)
{
minval1 = m_data[i].weight; //记录最小值
rtnIdx1 = i; //记录下标
}
}
} //end for i
//找第二个最小的值
for (int i = 0; i < m_length; ++i)
{
if (m_data[i].parent == -1 && i != rtnIdx1) //注意&&后的条件，目的是把第一个找到的最小权值的节点排除
{
if (minval2 > m_data[i].weight)
{
minval2 = m_data[i].weight; //记录最小值
rtnIdx2 = i; //记录下标
}
}
} //end for i
return;
}
private:
HFMTreeNode* m_data;
int m_length; //记录当前树有多少个节点【数组中多少个节点被使用了】
};
在main主函数中，增加下面的测试代码。
int weighLst[] = { 1,2,2,4,8}; //权值列表（数组），数组中的数据顺序无所谓
HFMTree hfmtobj(
sizeof(weighLst) / sizeof(weighLst[0]), //权值列表中元素个数
weighLst //权值列表首地址
);
hfmtobj.CreateHFMTree(); //创建哈夫曼树
hfmtobj.preOrder(hfmtobj.GetLength()-1); //遍历哈夫曼树，参数其实就是根节点的下标（数组最后一个有效位置的下标）
执行结果如下。这个结果是对生成的哈夫曼树进行前序遍历（根左右）的结果。
通过对上述代码的阅读和分析不难发现，利用1、2、2、4、8这5个权值作为叶子节点创建的哈夫曼树，用数组保存后，数组内容应该如图9所示。有兴趣的话，你也可以增加一些代码来输出数组中的内容方便观察，当然通过跟踪调试查看也是可以的。
把图9从上到下排列观察可能更加明显，如图10所示：
根据图9或图10，也很容易知道哈夫曼树的构造过程直至最后得到所需的哈夫曼树，结果如图11所示：
利用前序遍历（根左右）对图11的最后一幅图中显示的树进行遍历，得到的结果（权值）的顺序正是17、8、9、4、5、2、3、1、2。
哈夫曼编码及相关的代码实现
哈夫曼树有什么用途呢——和我们最开始说的故事一样，用来创建哈夫曼编码（Huffman Coding——一种二进制编码）。哈夫曼编码是一种可以用于数据压缩的编码方式，比如你可以想象在winrar或winzip等压缩软件中采用这种压缩方式。而哈夫曼编码的构造过程是需要用到哈夫曼树的。
哈夫曼编码主要解决通信双方传输信息时针对信息压缩问题，通过传输最少量的信息来表达一段相同的内容。
设想有一段文字内容“AFDBCFBDEFDF”要通过网络传给别人。一般来说，传输一段信息时，往往采用二进制的0和1（分别代表两种信号）来进行信息传输最便捷，所以考虑把要传输的这段文字内容进行编码。因为这段文字内容只涉及了A、B、C、D、E、F共6个字母。而用3位二进制数表示（编码）一个字母，则足可以表示8个字母（从二进制的000到二进制的111），所以用3位二进制数（字符）表达这段文字内容涉及的6个字母绰绰有余，如图12所示，注意，这属于固定长度编码：
在传输文字内容“AFDBCFBDEFDF”时，传输的数据就是编码后的“000101011001010101001011100101011101”。接收方可以按照双方事先的约定，也就是3位一划分来将二进制编码译码还原为真正的文字内容。但是如果传输的文字内容特别多，那么编码后的内容也将非常的长，这意味着传输的内容也会非常多。
事实上，在真正的数据传输中，不管传输的是英文字母、汉字等等，字母或者汉字出现的频率并不相同，比如在英文的26个字母中“E、A、T、I、N、O”出现的频率就会明显高于其他字母，而在汉字中“有、人、的、工、在、一、是”等出现的频率也会比其他汉字更高。
针对前面传输的文字内容“AFDBCFBDEFDF”中所包含的6个字母，可以粗略估算也可以假设它们出现的频率，按照出现频率一共100%计算，大略估计这6个字母的出现频率为A：12%、B：15%、C：9%、D：24%、E：8%、F：32%。有了这种估计，就可以按照哈夫曼树来重新进行编码规划——将A、B、C、D、E、F这6个字母分别看做叶子节点，将这6个字母的百分比（去掉百分号）12、15、9、24、8、32分别看做叶子节点的权值，这样就可以构造出一棵哈夫曼树。
如图13所示：
针对图13所展示的哈夫曼树，如果左分支路径中的各个段用0标示，右分支路径的各个段用1标示，换句话说，从根节点出发，向左走表示二进制的0，向右走表示二进制1，那么这种用二进制字符表示字母的方案就可以映射为树的表示形式。如图14：
从图14可以看到，从根节点出发，访问节点D需要经过的路径所包含的二进制数为00，节点E经过的路径所包含的二进制数为010……，这意味着D的编码是00，E的编码是010……。那么哈夫曼树的叶子节点所对应的二进制编码如图15所示（这些字母对应的二进制字符编码就是哈夫曼编码）。
从图15中可以看到，出现频率最高的字母，尽可能用最短的编码以节省数据通信量，所以这是一种可变长度编码，也就是不同的字母编码后对应的二进制字符长度不同。最终，要传输的文字内容是“AFDBCFBDEFDF”，而实际传输的内容是编码后的“11010001110111011100010100010”。可以看到，与原来需要传输的二进制字符对比一下。
- 原二进制字符串：000101011001010101001011100101011101（36个字符）
- 新二进制字符串：11010001110111011100010100010（29个字符）
这意味着需要传输的数据变少了，也就是数据被压缩了。节省了大概19%的保存或传输成本。显然，如果要传输的文字内容更多，所节省的成本也将更加可观。
那么如何从新的二进制字符串中把真正的文字内容解码出来呢？因为编码中只有0和1，而且是一种可变长度的编码，在解码时其实是容易因混淆而导致解码错误的，所以，对于可变长度的编码，设计时必须保证任何一个字母的编码都不可以是另一个字母编码的前缀。比如字母F的二进制编码是10，那么其他字母在编码时绝对不可以以10开头，观察图15，字母A、B、C、D、E的二进制字符都不是以10开头。
这里涉及一个概念——前缀编码：如果在一个编码方案中，任何一个编码都不是其他任何编码的前缀（最左子串），则称该编码是前缀编码。哈夫曼编码就属于一种前缀编码。
举个例子，假设字母C的二进制编码不是011而是101，因为以10开头了是不被允许的，那么如果传输的内容是10110110，接收方在解码时可能会解码为CCF，也可能会解码为FAA，这样就产生了歧义和混乱。而按照图15这样编码，在收到新二进制字符串时，解码出来的内容只能是“AFDBCFBDEFDF”，绝不会解码成其他内容。当然，为了保证发送方发送的内容接收方能够成功解码，接收方手中也必须有一份图15所示的编码表。
好了，我们总结一下，哈夫曼编码是用构造哈夫曼树的方法来确定字符集的一种编码方案，属于一种前缀编码，在解码时可以保证解出的内容的唯一性。
- 字符集中的每一个字符作为叶子节点，将各个字符出现的频率作为该节点的权值，构造出哈夫曼树。
- 将哈夫曼树左分支路径中的各个段用0标示，右分支路径中的各个段用1标示。当然，左分支用1标示，右分支用0标示也可以，只要通信双方在编码和解码时做好一致的约定就可以。
- 从哈夫曼树的根节点到叶子节点所经过的各段路径所对应的0或者1连接起来就构成了字符的哈夫曼编码。
因为哈夫曼树具有不唯一性，因此哈夫曼编码也是不唯一的。构建哈夫曼树时，有些资料上会建议左孩子节点的权值应该不大于右孩子节点的权值，或者要求左孩子与右孩子节点权值大小关系应该保持一致。换句话说，就是要么保证所有左孩子节点权值小于或等于右孩子节点权值，要么保证所有右孩子节点权值小于或者等于左孩子节点权值。但我认为这并没有关系，也不需要保持左右孩子节点权值大小关系的一致性。
哈夫曼编码的实现代码可以直接放在前面介绍的HFMTree类中实现，增加public修饰的成员函数即可。
//生成哈夫曼编码
bool CreateHFMCode(int idx) //参数idx是用于保存哈夫曼树的数组某个节点的下标
{
//调用这个函数时，m_length应该已经等于整个哈夫曼树的节点数量，那么哈夫曼树的叶子节点数量应该这样求
int leafNodeCount = (m_length + 1) / 2;
if (idx < 0 || idx >= leafNodeCount)
{
//只允许对叶子节点求其哈夫曼编码
return false;
}
string result=""; //保存最终生成的哈夫曼编码
int curridx = idx;
int tmpparent = m_data[curridx].parent;
while (tmpparent != -1) //沿着叶子向上回溯
{
if (m_data[tmpparent].lchild == curridx)
{
//前插0
result = "0" + result;
}
else
{
//前插1
result = "1" + result;
}
curridx = tmpparent;
tmpparent = m_data[curridx].parent;
} //end while
cout <<"下标为【"<< idx <<"】，权值为"<< m_data[idx].weight <<"的节点的哈夫曼编码是"<< result << endl;
return true;
}
在main主函数中，修改一下权值列表，完整的main主函数代码就是下面的样子。
int weighLst[] = { 12,15,9,24,8,32 };
HFMTree hfmtobj(
sizeof(weighLst) / sizeof(weighLst[0]), //权值列表中元素个数
weighLst //权值列表首地址
);
hfmtobj.CreateHFMTree(); //创建哈夫曼树
hfmtobj.preOrder(hfmtobj.GetLength()-1); //遍历哈夫曼树，参数其实就是根节点的下标（数组最后一个有效位置的下标）
//求哈夫曼编码
cout <<"--------------"<< endl;
for(int i = 0; i < sizeof(weighLst) / sizeof(weighLst[0]); ++i)
hfmtobj.CreateHFMCode(i);
执行结果如下：
请注意，该结果与图13所展示的哈夫曼树以及图15所展示的哈夫曼编码结果不完全一样，这是因为程序编码中哈夫曼树的构建规则完全遵照“哈夫曼树左孩子节点的权值不大于右孩子节点的权值”，而13的哈夫曼树并没有遵照这个规则构建，例如节点24和17结合的时候，还有节点32和27结合的时候。
小结
这节课，我们先铺垫了几个概念，包括节点的权、从根节点到某节点的路径长度、节点的带权路径长度、树的带权路径长度，注意，这里要懂得怎么计算。由此，我们得出了哈夫曼树的概念：在含有n个带权叶节点的二叉树中，其中带权路径长度（WPL）最小的二叉树，也叫做最优二叉树。想要根据给定的n个叶子节点来构造哈夫曼树，要经历4个步骤：
- 将这n个节点分别作为n棵仅含一个节点（根节点）的二叉树，这样就构成了一个二叉树集合F。
- 构造一个新节点，在集合F中选取两棵根节点权值最小的树作为这个新节点的左右子树（谁左谁右顺序任意）构造一棵新二叉树。这个新节点的权值是左右两棵子树根节点的权值之和。
- 从集合F中删除刚刚选取的两棵树，并将新得到的树加入到集合F中。
- 重复上面的2个步骤，直到集合F中只剩下一棵树为止，这棵树就是哈夫曼树。
理清了思路，也就能理解我们这节课用数组来保存哈夫曼树的详细代码案例了。
在学习了哈夫曼树之后，就该了解哈夫曼树有什么用途了。哈夫曼树是用来创建哈夫曼编码的。哈夫曼编码是一种可以用于数据压缩的编码方式，哈夫曼编码的构造过程需要用到哈夫曼树。
最后，我们详细讲解了对一段通信双方要传输的数据通过哈夫曼树进行哈夫曼编码的过程，同时给出了实现代码，希望通过这些代码能够帮你更深刻地理解哈夫曼树和哈夫曼编码的实现细节。
归纳思考
英文的26个字母使用的频率是不一样的，这26个字母的使用频率数据可以通过搜索引擎来搜索。如果要对这26个字母进行哈夫曼编码，计算一下使用哈夫曼编码可以对数据压缩多少。
欢迎你在留言区和我互动交流，如果觉得有所收获，也可以把课程分享给更多的朋友一起学习进步。我们下节课见！
- 鲁米 👍（0） 💬（2）
Huffman 树，可以归类于二叉搜索树吗？与 AVL R-B 树属于不同的演化方向了
2023-07-17