哈夫曼树的应用—哈夫曼编码
1.哈夫曼编码是一种可以被唯一解读的二进制编码 2.前缀编码保证了解码时不会有多种可能 3.哈夫曼编码有不等长和等长两种编码，为了保证不等长编码的唯一性，使用前缀编码 4.频率低的采用短编码，频率高的采用长编码。
出现次数多的靠近根节点，出现次数少的远离根节点，这样可以得到最小的带权路径长度，这样是最节省空间的
哈夫曼编码方案：从叶子到根逆向求每个字符的哈夫曼编码
第三个参数是所要求的哈夫曼编码的个数，要求几个字母的哈夫曼编码就传入几
哈夫曼编码生成
代码语言：javascript复制//哈夫曼树 存放哈夫曼编码的指针数组 输入节点个数
void huffmanCode(HtnNode*& huffTree,char**& huffCode,int n)
{
//定义工作空间，存放临时编码串
char* temp=new char[n];
temp[n - 1] = ' ';
//遍历哈夫曼数组生成哈夫曼编码
for (int i = 0; i < n; i )
{
int start = n - 1;//记录当前temp数组最后一位‘ ’的位置
int pos = i; //记录当前正在处理的位置
//找到当前位置的父节点
int parent = huffTree[pos].parent;
while (parent != -1)
{
//判断当前父亲节点的左孩子位置是不是当前正在处理的位置
if (huffTree[parent].lchild == pos)
//如果当前位置是左孩子，那么temp数组从最后一位‘ ’前面开始存放一个0
temp[--start] = '0';
else
temp[--start] = '1';
//当前处理位置移动到父亲节点
pos = parent;
//记录当前父亲节点的位置移到自己的父亲节点
parent = huffTree[parent].parent;
}
//while循环结束后，start记录的是哈夫曼编码在temp数组中第一次出现的位置
//当for进行下一次循环的时候，才会更新start值为n-1
//建立哈夫曼编码实际需要的存储空间
huffCode[i] = new char[n - start];
//将temp里面的哈夫曼编码数据存放到哈夫曼编码指针数组里面
strcpy(huffCode[i], &temp[start]);
}
//释放在堆区开辟的空间
delete[] temp;
}哈夫曼编码运行演示
完整代码
代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
//哈夫曼树----静态链表方式存储
struct HtnNode {
int weight;// 权值
int lchild, rchild, parent;
}*Node;
//存放哈夫曼树的静态链表的构建和用户输入权值
void creatNode(HtnNode*& node,int w[],char**& huffCode)
{
int num = 0;
cout << "请输入节点的个数：" << endl;
cin >> num;
node = new HtnNode[2 * num - 1];//在堆区创建一个大小为2*num -1长度的汉夫曼静态链表数组
cout << "数组长度为：" << num << endl;
cout << "请输入4个权值：" << endl;
for (int i = 0; i < 4; i )
cin >> w[i];
//为哈夫曼编码指针数组在堆区开辟空间
huffCode = new char* [num];
}
//寻找parent为-1的最小的和最次小的节点
//哈夫曼静态链表的树的数组 当前进行构建的节点下标 权值最小的节点下标 权值最次小的节点下标
void select(HtnNode*& node,int k,int& i1,int& i2)
{
int min=0;
//找到哈夫曼树中权值最小和最次小的节点的静态链表数组下标
for (int i = 0; i < k; i )
{
//找到第一个parent值为-1的节点，假设该节点权值最小
if (node[i].parent == -1)
{
min = i; //假设数组中第i个节点权值最小
break;
}
}
for (int i = 1; i < k; i )
{
if (node[i].parent == -1)
{
//如果当前节点的权值小于node[min]节点的权值，就把i的值赋值给min
if (node[i].weight < node[min].weight)
min = i;
}
}
//此时min的值为权值最小的节点在静态链表中的下标
//再次对数组进行遍历操作，但是把下标为min的元素排除在比较范围里面
int lessmin=0;
for (int i = 0; i < k; i )
{
if (i != min)
{
if (node[i].parent == -1)
{
lessmin = i;
break;
}
}
}
for (int i = 0; i < k; i )
{
if (node[i].parent == -1)
{
if (i != min)
{
if (node[i].weight < node[lessmin].weight)
{
lessmin = i;
}
}
}
}
i1 = min;//将min赋值给i1,表明i1得到的是权值最小的节点下标
i2 = lessmin;//将lessmin赋值给i2,表明i2得到的是权值次小的节点下标
cout << "最小的节点下标为：" << min << " 次小的节点下标为：" << lessmin << endl;
}
//哈夫曼树的构建:静态链表数组， 存放权值的数组，节点的个数
void HuffMan(HtnNode*& node, int w[], int n)
{
//1.初始化所有节点的项目为-1
for (int i = 0; i < 2*n-1; i )
{
node[i].weight = -1;
node[i].parent = -1;//-1表示没有双亲
node[i].lchild = -1;
node[i].rchild = -1;
}
//2.初始化前n个节点的权值
for (int i = 0; i < n; i )
node[i].weight = w[i];
//3.构建哈夫曼树
int i1=0, i2=0;
for (int k = n; k< 2 * n - 1; k )
{
//先找到parent为-1的最小的和次小的节点
select(node, k, i1, i2);//parent要为-1才可以进行权值的大小比较
node[k].weight = node[i1].weight node[i2].weight;
node[k].lchild = i1;
node[k].rchild = i2;
node[i1].parent = k;
node[i2].parent = k;
}
}
//打印构建好的哈夫曼树的数组内容
void display(HtnNode*& node, int n)
{
//遍历哈夫曼树
cout << "weight parent lchild rchild" << endl;
for (int i = 0; i < 2 * n - 1; i )
{
cout << node[i].weight << " t" << node[i].parent << " t" << node[i].lchild << " t" << node[i].rchild << endl;
}
}
//哈夫曼编码生成
//哈夫曼树 存放哈夫曼编码的指针数组 输入节点个数
void huffmanCode(HtnNode*& huffTree,char**& huffCode,int n)
{
//定义工作空间，存放临时编码串
char* temp=new char[n];
temp[n - 1] = ' ';
//遍历哈夫曼数组生成哈夫曼编码
for (int i = 0; i < n; i )
{
int start = n - 1;//记录当前temp数组最后一位‘ ’的位置
int pos = i; //记录当前正在处理的位置
//找到当前位置的父节点
int parent = huffTree[pos].parent;
while (parent != -1)
{
//判断当前父亲节点的左孩子位置是不是当前正在处理的位置
if (huffTree[parent].lchild == pos)
//如果当前位置是左孩子，那么temp数组从最后一位‘ ’前面开始存放一个0
temp[--start] = '0';
else
temp[--start] = '1';
//当前处理位置移动到父亲节点
pos = parent;
//记录当前父亲节点的位置移到自己的父亲节点
parent = huffTree[parent].parent;
}
//while循环结束后，start记录的是哈夫曼编码在temp数组中第一次出现的位置
//当for进行下一次循环的时候，才会更新start值为n-1
//建立哈夫曼编码实际需要的存储空间
huffCode[i] = new char[n - start];
//将temp里面的哈夫曼编码数据存放到哈夫曼编码指针数组里面
strcpy(huffCode[i], &temp[start]);
}
//释放在堆区开辟的空间
delete[] temp;
}
//打印哈夫曼指针数组
void output(char**& huffcode,int n)
{
cout << "输出哈夫曼编码" << endl;
for (int i = 0; i < n; i )
{
cout << huffcode[i] << endl;
}
}
int main()
{
HtnNode* node = NULL;
char** huffCode = NULL;//存放哈夫曼编码的指针数组
int w[4];//权值数组
creatNode(node, w,huffCode);
HuffMan(node, w, 4);
display(node, 4);
huffmanCode(node, huffCode, 4);
output(huffCode, 4);
system("pause");
return 0;
}
