序言
对于哈夫曼编码，个人的浅薄理解就是在压缩存储空间用很大用处。
用一个很简单例子，存储一篇英文文章时候，可能a出现的概率较大，z出现的记录较小，如果正常存储，可能a与z存储使用的空间一样。但是用哈夫曼编码方式，a经常出现，所用编码长度就短。
构造哈夫曼树，生成哈夫曼编码
一、定义节点类型
struct node {
char c;
long key;
node *left, *right,*parent;
node() { left = right = null; }
};
二、定义树类型（节点数组）
三要素：不定长数组，元素大小，有效元素个数
struct roota {
node *nodea;
const int size;
int n;
roota(int size) :size(size) { n = 0; nodea = new node[size]; }
~roota() { delete[]nodea; }
};
三、创建哈夫曼树
1.将每一个节点都当成一棵树，初始化数组大小，并进行赋值
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.将树按权值大小排序
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]的左右子结点中
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，直到输出所有叶子节点
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<
以上是对构造哈夫曼树以及生成哈夫曼编码的总结，希望对你们有所帮助！
