数据结构 哈夫曼树
1.节点i的路径长度:从根节点到节点i的路径上所经过边数
2.树的路径长度:所有节点的路径长度之和
内部路径长度:所有内部节点路径长度之和
外部路径长度(有时会把树的路径长度当作外部路径长度):所有叶子节点路径长度之和
3.节点i的带权路径长度:节点i的路径长度*节点i权值
4.树的带权路径长度(WPL):所有叶子节点的带权路径长度之和
给出n个节点(都带有权值),可以再自行加入若干节点(不确定),用这n个节点全部做叶子节点,自行加入的节点做内部节点去建立一棵二叉树,其中WPL最小的一棵二叉树称为哈夫曼树(最优二叉树)
注:哈夫曼树WPL的值唯一
但WPL的值最小的哈夫曼树不唯一
如何构建哈夫曼树?
给定n个节点(带权值且只做叶子节点)
1.一开始认为n个节点为n棵树
2.每次找根节点权值最小的两棵树(x,y),再新加入一个节点z做x和y的父亲,新的根节点权值为(x,y),此时将x,y两棵树合并出一棵新树,这棵树的根节点为z
哈夫曼树应用:通过编码进行数据压缩
哈夫曼编码—>变长编码,压缩空间
定长编码:ASCII编码(8bit),Unicode编码(16bit)
缺陷:浪费空间
变长编码:比定长编码省空间
可以使用哈夫曼树来构造变长编码—>哈夫曼编码
1.先统计一条消息中n个字符分别出现频率—>节点权值
2.构造哈夫曼树
3.标上1和0
注:哈夫曼树WPL值即为信息编码所占bit位数
注:变长编码中遵循前缀属性原则(短的编码不能是长编码的前缀,避免二义性)
哈夫曼编码树实现:
1.建立哈夫曼树:把每个字符的频率看作节点的权值,建立哈夫曼树,通过结构体数组模拟存储
节点:权值,父亲的下标,左右孩子节点的下标
(1)查找最小的两个根节点
(2)合并,加入一个新的根节点
注:n个叶子节点,总共有2*n-1个节点
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
using namespace std;
class Node
{
public:
int w;//权值
int fi;//父亲节点坐标
int left;//左右孩子节点下标
int right;
};
class HFM_Tree
{
public:
int size;//节点个数
Node* tree;//指针模拟开数组
public:
HFM_Tree(int w_arr[], int sz) :size(2 * sz - 1)
{
tree = new Node[size];
if (tree == nullptr)
{
cout << "开辟失败" << endl;
}
else
{
//初始化哈夫曼树(从下标为零开始存储)
for (int i = 0; i < size; ++i)
{
tree[i].w = 0;
tree[i].fi = 0;
tree[i].left = tree[i].right = 0;
}
//构建哈夫曼树
for (int i = 0; i < sz; ++i)
{
tree[i].fi = i;
tree[i].w = w_arr[i];
}
int w1(0);
int w2(0);//查找最小权值的两个下标
//放入新节点
for (int i = sz; i < size; ++i)
{
//i位置放新的节点,所以范围最大为i - 1
Find_Min_w(i, w1, w2);
//将最小权值的两个根节点连接起来,作为孩子
tree[w1].fi = tree[w2].fi = i;
tree[i].w = tree[w1].w + tree[w2].w;
tree[i].fi = i;//别忘了给新节点加上父亲
tree[i].left = w1;
tree[i].right = w2;
}
}
}
//查找的范围和两个权值,传引用直接修改
void Find_Min_w(int range, int& w_1, int& w_2)
{
//先找最小权值下标
int min(0);
for (int i = 0; i < range; ++i)
{
if (tree[i].fi == i)
{
//找第一个根节点
min = i;
break;
}
}
//找出最小权值下标
for (int i = 0; i < range; ++i)
{
if (tree[i].fi == i)
{
if (tree[i].w < tree[min].w)
{
min = i;
}
}
}
w_1 = min;
//再找第二小根节点下标
for (int i = 0; i < range; ++i)
{
if (tree[i].fi == i && i != w_1)
{
//找第二个根节点
min = i;
break;
}
}
for (int i = 0; i < range; ++i)
{
if (tree[i].fi == i && i != w_1)
{
if (tree[i].w < tree[min].w)
{
min = i;
}
}
}
w_2 = min;
}
//进行哈夫曼编码,左为0,右为1,从下往上找(找出来是倒序的)
//利用二维数组存储编码,使用一维数组暂存每一个字符编码,将一维数组拷贝到二维数组中
//叶子节点个数
char** Create_HFM_code(int n)
{
char *temp = new char[n];//树理论最高为n,但实际存不满
char** code = new char*[n];
int start(0);//一开始存放编码的位置
int p(0);//存放节点下标
int p_f(0);//存放节点父亲下标(用于判断是左孩子还是右孩子)
for (int i = 0; i < n; ++i)
{
start = n - 1;
temp[start] = '\0';//因为存放的是0,1字符
p = i;
p_f = tree[i].fi;
while (tree[p].fi != p)//一路找到根节点
{
start--;
if (tree[p_f].left == p)
{
temp[start] = '0';
}
else
{
temp[start] = '1';
}
p = p_f;
p_f = tree[p].fi;
}
code[i] = new char[n - start];
strcpy(code[i], &temp[start]);//拷贝哈夫曼编码
}
delete temp;
temp = nullptr;
return code;
}
};
int main()
{
char s[8] = { 'A', 'B', 'C', 'D','E', 'F', 'G', 'H' };
int w[8] = { 5, 29, 7, 8,14, 23, 3, 11 };
HFM_Tree tr(w, 8);
char** code = tr.Create_HFM_code(8);
for (int i = 0; i < 8; ++i)
{
cout << s[i] << ' ' << code[i] << endl;
}
return 0;
}