C++哈夫曼树的原理是什么及怎么实现
这篇文章主要讲解了“C++哈夫曼树的原理是什么及怎么实现”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“C++哈夫曼树的原理是什么及怎么实现”吧！
1. 前言
什么是哈夫曼树？
把权值不同的
n此 n 个结点为二叉树的叶结点 。
权值较大的结点离根结点较近，权值较小的结点离根结点较远。
该树的带权路径长度是所有可能构建的二叉树中最小的。
则称符合上述条件的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。
构建哈夫曼树的目的是什么？
用来解决在通信系统中如何使用最少的二进制位编码字符信息。
2. 设计思路
哈夫曼树产生的背景：
在通信系统中传递一串字符串文本时，需要对这一串字符串文本信息进行二进制编码。编码时如何保证所用到的
bit现假设字符串由
ABCD 42bit| 字符 | 编码 |
|---|---|
| A | 00 |
| B | 01 |
| C | 10 |
| D | 11 |
传输
ABCDbit2nn*210002000bit使用等长编码时，如果传输的报文中有
265bit但在实际应用中，各个字符的出现频率或使用次数是不相同的，如
A、B、CX、Y、Zbit哈夫曼的设计思想：
对字符串信息进行编码设计时，让使用频率高的字符使用
，使用频率低的用短码
，以优化整个信息编码的长度。长码基于这种简单、朴素的想法设计出来的编码也称为
。不等长编码
哈夫曼不等长编码的具体思路如下：
如现在要发送仅由
A、B、C、D 4A50%B20%C15%D10%不等长编码的朴实思想是
字符bitbitbit
使用A
位1
编码。bit
使用B
位2
编码。bit
使用C
位3
编码。bit
使用D
位3
编码。bit
具体编码如下表格所示：
| 字符 | 占比 | 编码 |
|---|---|---|
| A | 0.5 | 0 |
| B | 0.2 | 10 |
| C | 0.15 | 110 |
| D | 0.1 | 111 |
如此编码后，是否真的比前面的等长编码所使用的总
bit计算结果=
0.5*1+0.2*2+0.15*3+0.1*3=1.65先计算每一个字符在报文信息中的占比乘以字符所使用的
bit然后对上述每一个字符计算后的结果进行相加。
显然，编码
ABCD1.65bit2 个 bit1000bit1.65*1000=1650 bit哈夫曼编码和哈夫曼树有什么关系？
因为字符的编码是通过构建一棵自下向上的二叉树推导出来的，如下图所示：
哈夫曼树的特点：
信息结点都是叶子结点。
叶子结点具有权值。如上二叉树，
结点权值为A
，0.5
结点权值为B
，0.2
结点权值为C
，0.15
结点权值为D
。0.1哈夫曼编码为不等长前缀编码（即要求一个字符的编码不能是另一个字符编码的前缀）。
从根结点开始，为左右分支分别编号
和0
，然后顺序连接从根结点到叶结点所有分支上的编号得到字符的编码。1
相信大家对哈夫曼树有了一个大概了解，至于如何通过构建哈夫曼树，咱们继续再聊。
3. 构建思路
在构建哈夫曼树之前，先了解几个相关概念：
路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为
，则从根结点到第1
层结点的路径长度为L
。L-1结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为
。WPL
如有权值为
{3,4,9,15}43B
哈夫曼树树的带权路径长度那么，如何构建二叉树，才能保证构建出来的二叉树的带权路径长度最小？
如有一字符串信息由 ABCDEFGH 8个字符组成，每一个字符的权值分别为
{3,6,12,9,4,8,21,22}1.以每一个结点为根结点构建一个单根二叉树，二叉树的左右子结点为空，根结点的权值为每个结点的权值。并存储到一个树集合中。
2.从树集合中选择根结点的权值最小的
2222如下图所示。权值为
347
3.重复第二步，直到树集合中只有一个根结点为止。
当集合中只存在一个根结点时，停止构建，并且为最后生成树的每一个非叶子结点的左结点分支标注
01
通过上述
从下向上WPL=(3+4)*5+6*4+(8+9+12)*3+(21+22)*2=232上述的构建思想即为哈夫曼树设计思想，不同权值的字符编码就是结点路径上
01| 字符 | 权值 | 编码 |
|---|---|---|
| A | 3 | 11110 |
| B | 6 | 1110 |
| C | 12 | 110 |
| D | 9 | 001 |
| E | 4 | 11111 |
| F | 8 | 000 |
| G | 21 | 01 |
| H | 22 | 10 |
4. 编码实现
4.1 使用优先队列
可以把权值不同的结点分别存储在优先队列（Priority Queue）中，并且给与权重较低的结点较高的优先级（Priority）。
具体实现哈夫曼树算法如下：
1.把
nnPi2.如果队列内的节点数
>1从队列中移除两个最小的结点。
产生一个新节点，此节点为队列中移除节点的父节点，且此节点的权重值为两节点之权值之和，把新结点加入队列中。
重复上述过程，最后留在优先队列里的结点为哈夫曼树的根节点（
）。root
完整代码：
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
//树结点
struct TreeNode {
//结点权值
float weight;
//左结点
TreeNode *lelfChild;
//右结点
TreeNode *rightChild;
//初始化
TreeNode(float w) {
weight=w;
lelfChild=NULL;
rightChild=NULL;
}
};
//为优先队列提供比较函数
struct comp {
bool operator() (TreeNode * a, TreeNode * b) {
//由大到小排列
return a->weight > b->weight;
}
};
//哈夫曼树类
class HfmTree {
private:
//优先队列容器
priority_queue<TreeNode *,vector<TreeNode *>,comp> hfmQueue;
public:
//构造函数，构建单根结点树
HfmTree(int weights[8]) {
for(int i=0; i<8; i++) {
//创建不同权值的单根树
TreeNode *tn=new TreeNode(weights[i]);
hfmQueue.push(tn);
}
}
//显示队列中的最一个结点
TreeNode* showHfmRoot() {
TreeNode *tn;
while(!hfmQueue.empty()) {
tn= hfmQueue.top();
hfmQueue.pop();
}
return tn;
}
//构建哈夫曼树
void create() {
//重复直到队列中只有一个结点
while(hfmQueue.size()!=1) {
//从优先队列中找到权值最小的 2 个单根树
TreeNode *minFirst=hfmQueue.top();
hfmQueue.pop();
TreeNode *minSecond=hfmQueue.top();
hfmQueue.pop();
//创建新的二叉树
TreeNode *newRoot=new TreeNode(minFirst->weight+minSecond->weight);
newRoot->lelfChild=minFirst;
newRoot->rightChild=minSecond;
//新二叉树放入队列中
hfmQueue.push(newRoot);
}
}
//按前序遍历哈夫曼树的所有结点
void showHfmTree(TreeNode *root) {
if(root!=NULL) {
cout<<root->weight<<endl;
showHfmTree(root->lelfChild);
showHfmTree(root->rightChild);
}
}
//析构函数
~HfmTree() {
//省略
}
};
//测试
int main(int argc, char** argv) {
//不同权值的结点
int weights[8]= {3,6,12,9,4,8,21,22};
//调用构造函数
HfmTree hfmTree(weights);
//创建哈夫曼树
hfmTree.create();
//前序方式显示哈夫曼树
TreeNode *root= hfmTree.showHfmRoot();
hfmTree.showHfmTree(root);
return 0;
}显示结果：
上述输出结果，和前文的演示结果是一样的。
此算法的时间复杂度为
O（nlogn）n2n-1O（log n）4.2 使用一维数组
除了上文的使用优先队列之外，还可以使用一维数组的存储方式实现。
在哈夫曼树中，叶子结点有
nn-12n-1#include <iostream>
using namespace std;
//叶结点数量
const unsigned int n=8;
//一维数组长度
const unsigned int m= 2*n -1;
//树结点
struct TreeNode {
//权值
float weight;
//父结点
int parent;
//左结点
int leftChild;
//右结点
int rightChild;
};
class HuffmanTree {
public:
//创建一维数组
TreeNode hfmNodes[m+1];
public:
//构造函数
HuffmanTree(int weights[8]);
~HuffmanTree( ) {
}
void findMinNode(int k, int &s1, int &s2);
void showInfo() {
for(int i=0; i<m; i++) {
cout<<hfmNodes[i].weight<<endl;
}
}
};
HuffmanTree::HuffmanTree(int weights[8]) {
//前2 个权值最小的结点
int firstMin;
int secondMin;
//初始化数组中的结点
for(int i = 1; i <= m; i++) {
hfmNodes[i].weight = 0;
hfmNodes[i].parent = -1;
hfmNodes[i].leftChild = -1;
hfmNodes[i].rightChild = -1;
}
//前 n 个是叶结点
for(int i = 1; i <= n; i++)
hfmNodes[i].weight=weights[i-1];
for(int i = n + 1; i <=m; i++) {
this->findMinNode(i-1, firstMin, secondMin);
hfmNodes[firstMin].parent = i;
hfmNodes[secondMin].parent = i;
hfmNodes[i].leftChild = firstMin;
hfmNodes[i].rightChild = secondMin;
hfmNodes[i].weight = hfmNodes[firstMin].weight + hfmNodes[secondMin].weight;
}
}
void HuffmanTree::findMinNode(int k, int & firstMin, int & secondMin) {
hfmNodes[0].weight = 32767;
firstMin=secondMin=0;
for(int i=1; i<=k; i++) {
if(hfmNodes[i].weight!=0 && hfmNodes[i].parent==-1) {
if(hfmNodes[i].weight < hfmNodes[firstMin].weight) {
//如果有比第一小还要小的，则原来的第一小变成第二小
secondMin = firstMin;
//新的第一小
firstMin = i;
} else if(hfmNodes[i].weight < hfmNodes[secondMin].weight)
//如果仅比第二小的小
secondMin = i;
}
}
}
int main() {
int weights[8]= {3,6,12,9,4,8,21,22};
HuffmanTree huffmanTree(weights);
huffmanTree.showInfo();
return 1;
}测试结果：
