将字符串BADCADFEED进行二进制编码， 哈夫曼编码能减少原始编码的大小
A 二进制 27
A - ‘A’ 000 27%占比
对占比进行排序
int weight[] = {5, 8, 15, 15，27，30};
创建哈夫曼树
占比 中找出2个最小值 x1 -> 左子树, 第二小值 x2 -> 右子树, x1 + x2 -> 父结点，
x1 + x2
x1 x2
ABCDEF 作为叶子结点
是一个满二叉树
顺序结构储存哈夫曼树
HaffNode 结点结构体
typedef struct HaffNode{
int weight;
int flag;
int parent;
int leftChild;
int rightChild;
} HaffNode;
储存数组 个数2*n-1，满二叉树
HaffNode *myHaffTree =malloc(sizeof(HaffNode)* (2*n-1));
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;
}
}
哈夫曼树编码
E 11 F 1000
void HaffmanCode(HaffNode haffTree[],int n,Codehaff Code[])
{
//1.创建一个结点cd
Code*cd = (Code* )malloc(sizeof(Code));
intchild, parent;
//2.求n个叶结点的哈夫曼编码
for(inti =0; 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;
}
}
