[toc]
前言
哈夫曼数是而二叉树的一种特殊形式,又称为最优二叉树,主要用于数据解压和编码长度的优化.
重要概念
- 路径和路径长度
在一棵树种,从一个结点往下可以到达孩子或孩子的孩子结点直接的通路,成为路径.通路分支的数目成为路径长度.
如果规定,根节点的层数为1,那么到达L层路径的结点路径长度为L-1.
- 结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积.
- 树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
图二叉树WPL为:
WPL = 5*2+10*2+15*1 = 45
哈夫曼树
定义
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree).
哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近.
叶子结点为A、B、C、D，对应权值分别为7、5、2、4。
左边树的WPL = 7 * 2 + 5 * 2 + 2 * 2 + 4 * 2 = 36
右边树的WPL =7 * 1 + 5 * 2 + 2 * 3 + 4 * 3 = 35
由ABCD构成叶子结点的二叉树形态有许多种，但是WPL最小的树只有左边树所示的形态。则左边树霍夫曼树。
构造哈夫曼树
构造哈夫曼树主要运用于编码，称为哈夫曼编码.
构造哈夫曼树的算法如下：
1）对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,..., Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。
2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
4）重复2）和3），直到集合F中只有一棵二叉树为止。
-
第一步,对结点进行排序
d59f745a2b88b5642087170045902c61 -
第二步,将最小的5和8构造传一棵子树
f79a4ebba755b8b7bd3aa592462276ee -
第三步,5+8等于13,小于15,将13,15构造成一棵子树
28e599a215e8ac6919402f24d843f1c4 -
第四步,由于13+15>15和27,所以将15,27构造成一棵子树
e5291d83746a315b5a4245036fa8eeb5 -
第五步,30是大于28,30和28构造一棵子树,
608fb9885a18a1c0cab82c47516ba66a -
最后连起来就是:
2d0b1ee8b583a77b29c4bf6e23f02dc7
- 哈夫曼编码
编码规则:从根节点出发，向左标记为0，向右标记为1.
代码实现
-
哈夫曼树
8aeb99b546424a41033939ab8c4abfdf -
哈夫曼编码
24a384a87746fac18b989214c0d9c296 构造结构体
const int MaxValue = `10000`;//初始设定的权值最大值
const int MaxBit = `4`;//初始设定的最大编码位数
const int MaxN = `10`;//初始设定的最大结点个数
typedef struct HaffNode{
int weight;
int flag;
int parent;
int leftChild;
int rightChild;
}HaffNode;
typedef struct Code//存放哈夫曼编码的数据元素结构
{
int bit[MaxBit];//数组
int start; //编码的起始下标
int weight;//字符的权值
}Code;
- 哈夫曼树
void Haffman(int weight[],int n,HaffNode *haffTree){
int j,m1,m2,x1,x2;
//1.哈夫曼树初始化
//n个叶子结点. 2n-1
for(int i = 0; i < 2*n-1;i++){
if(I<n)
haffTree[i].weight = weight[I];
else
haffTree[i].weight = 0;
haffTree[i].parent = 0;
haffTree[i].flag = 0;
haffTree[i].leftChild = -1;
haffTree[i].rightChild = -1;
}
//2.构造哈夫曼树haffTree的n-1个非叶结点
for (int i = 0; i< n - 1; i++){
m1 = m2 = MaxValue;
x1 = x2 = 0;
//2,4,5,7
for (j = 0; j< n + i; j++)//循环找出所有权重中，最小的二个值--morgan
{
if (haffTree[j].weight < m1 && haffTree[j].flag == 0)
{
m2 = m1;
x2 = x1;
m1 = haffTree[j].weight;
x1 = j;
} else if(haffTree[j].weight<m2 && haffTree[j].flag == 0)
{
m2 = haffTree[j].weight;
x2 = j;
}
}
//3.将找出的两棵权值最小的子树合并为一棵子树
haffTree[x1].parent = n + I;
haffTree[x2].parent = n + I;
//将2个结点的flag 标记为1,表示已经加入到哈夫曼树中
haffTree[x1].flag = 1;
haffTree[x2].flag = 1;
//修改n+i结点的权值
haffTree[n + i].weight = haffTree[x1].weight + haffTree[x2].weight;
//修改n+i的左右孩子的值
haffTree[n + i].leftChild = x1;
haffTree[n + i].rightChild = x2;
}
}
- 哈夫曼编码
void HaffmanCode(HaffNode haffTree[], int n, Code haffCode[])
{
//1.创建一个结点cd
Code *cd = (Code * )malloc(sizeof(Code));
int child, parent;
//2.求n个叶结点的哈夫曼编码
for (int i = 0; i<n; I++)
{
//从0开始计数
cd->start = 0;
//取得编码对应权值的字符
cd->weight = haffTree[i].weight;
//当叶子结点i 为孩子结点.
child = I;
//找到child 的双亲结点;
parent = haffTree[child].parent;
//由叶结点向上直到根结点
while (parent != 0)
{
if (haffTree[parent].leftChild == child)
cd->bit[cd->start] = 0;//左孩子结点编码0
else
cd->bit[cd->start] = 1;//右孩子结点编码1
//编码自增
cd->start++;
//当前双亲结点成为孩子结点
child = parent;
//找到双亲结点
parent = haffTree[child].parent;
}
int temp = 0;
for (int j = cd->start - 1; j >= 0; j--){
temp = cd->start-j-1;
haffCode[i].bit[temp] = cd->bit[j];
}
//把cd中的数据赋值到haffCode[I]中.
//保存好haffCode 的起始位以及权值;
haffCode[i].start = cd->start;
//保存编码对应的权值
haffCode[i].weight = cd->weight;
}
}
