序言
对于哈夫曼编码，个人的浅薄理解就是在压缩存储空间用很大用处。
用一个很简单例子，存储一篇英文文章时候，可能A出现的概率较大，Z出现的记录较小，如果正常存储，可能A与Z存储使用的空间一样。但是用哈夫曼编码方式，A经常出现，所用编码长度就短。
构造哈夫曼树，生成哈夫曼编码
一、定义节点类型
|
1
2
3
4
5
6
|
struct Node {
char C;
long key;
Node *Left, *Right,*parent;
Node() { Left = Right = NULL; }
};
|
二、定义树类型（节点数组）
三要素：不定长数组，元素大小，有效元素个数
|
1
2
3
4
5
6
7
|
struct RootA {
Node *NodeA;
const int Size;
int n;
RootA(int Size) :Size(Size) { n = 0; NodeA = new Node[Size]; }
~RootA() { delete[]NodeA; }
};
|
三、创建哈夫曼树
1.将每一个节点都当成一棵树，初始化数组大小，并进行赋值
|
1
2
3
4
5
6
7
8
|
RootA RA(4);
//1.在RA.NodeA中存入字母和权值
for (RA.n = 0;RA.n < RA.Size;RA.n++) {
cout << "字母：";
cin >> RA.NodeA[RA.n].C;
cout << "权值：";
cin >> RA.NodeA[RA.n].key;
}
|
2.将树按权值大小排序
|
1
2
3
4
5
6
7
8
9
10
11
12
|
void Sort(RootA *ra) {
for (int i = 0;i < ra->n;i++) {
bool ESC = false;
for (int j = 0;j < ra->n - i - 1;j++) {
if (ra->NodeA[j].key > ra->NodeA[j + 1].key) {
Node T;T = ra->NodeA[j];ra->NodeA[j] = ra->NodeA[j + 1];ra->NodeA[j + 1] = T;
ESC = true;
}
}
if (!ESC) return;
}
}
|
3.(1)遍历数组，将RA.NodeA[0]和RA.Node[1]合并，其余向前移动，重新排序
(2)将RA.NodeA[0]，RA.NodeA[1]分别放在新合并的RA.NodeA[0]的左右子结点中
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
while (RA.n > 1) {
//1.将RA.NodeA[0]和RA.NodeA[1]合并，将其余向前移动
Node *NewNode0 = new Node;
*NewNode0 = RA.NodeA[0];
Node *NewNode1 = new Node;
*NewNode1 = RA.NodeA[1];
RA.NodeA[0].C = ' ';
RA.NodeA[0].key = RA.NodeA[0].key + RA.NodeA[1].key;
RA.NodeA[0].Left = NewNode0;
NewNode0->parent = &RA.NodeA[0];
RA.NodeA[0].Right = NewNode1;
NewNode1->parent = &RA.NodeA[0];
for (int i = 1;i < RA.n-1;i++) {
RA.NodeA[i] = RA.NodeA[i + 1];
}
RA.n = RA.n - 1;
//2.排序
Sort(&RA);
}
|
4.输出哈夫曼编码
递归，找到叶子节点，记录路径，左记录0，右记录1，直到输出所有叶子节点
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void CrateCode(Node *t,string &s) {
//1.遍历节点，遍历左节点编码为0,右节点则为1，递归，直到输出所有叶子节
if (t->Left != NULL && t->Right != NULL) {
s.push_back('0'); CrateCode(t->Left, s);
s.pop_back();
s.push_back('1');CrateCode(t->Right, s);
s.pop_back();
}
else {
cout << "哈夫曼编码：";
cout << t->C << ":" << s<<endl;
}
}
|
以上是对构造哈夫曼树以及生成哈夫曼编码的总结，希望对你们有所帮助！
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/stephenli300203/article/details/105438016