哈夫曼树详细讲解（带例题和C语⾔代码实现——全注释）
**
哈夫曼树详细讲解（带例题和C语⾔代码实现——全注释）
**
1. 定义
哈夫曼树⼜称最优⼆叉树，是⼀种带权路径长度最短的⼆叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的 路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）
1. 计算公式
树的带权路径长度记为WPL=(W1L1+W2L2+W3L3+…+Wn Ln) ，N个权值Wi(i=1,2,…n)构成⼀棵有N个叶结点的⼆叉树，相应的叶结点的路径长度为Li(i=1,2,…n)。 可以证明哈夫曼树的WPL是最⼩的
2. 运算过程
⼀、对给定的n个权值{W1,W2,W3,…,Wi,…,Wn}构成n棵⼆叉树的初始集合F= {T1,T2,T3,…,Ti,…,Tn}，其中每棵⼆叉树Ti中只有⼀个权值为Wi的根结点，它的左右⼦树均为空。（为⽅便在计算机上实现算 法，⼀般还要求以Ti的权值Wi的升序排列。）
⼆、在F中选取两棵根结点权值最⼩的树作为新构造的⼆叉树的左右⼦树，新⼆叉树的根结点的权值为其左右⼦树的根结点的权值之和。
三、从F中删除这两棵树，并把这棵新的⼆叉树同样以升序排列加⼊到集合F中。
四、重复⼆和三两步，直到集合F中只有⼀棵⼆叉树为⽌
3. 图解过程
4. 例题讲解（重点）
如例：已知某通讯系统在通讯联络中只可能出现8中字符，其概率分别别是0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11, 试设计赫夫曼编码
根据所占⽐例列出权值解答
注：A是0111
⼀共有⼋个节点，则数组中需要构建的节点 m = 2*n – 1 则为15个 给⼋⾏⽣成树，余下的记录过程
最终结果：
C语⾔实现代码
（记录⼈的姓名，成绩，按照成绩作为权值编码将上⽂中字母作为名字，⽐例作为成绩（权值））
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define n  6//叶⼦结点数⽬
#define m  (2*n-1) //总结点数⽬，可证明
#define m  (2*n-1) //总结点数⽬，可证明
#define MAXVALUE 10000 //最⼤权值
#define MAXBIT 20 //哈夫曼编码最⼤长度
typedef struct{
char name[5];
int weight;
int parent;
int Lchild,Rchild;
}Htreetype;
typedef struct{
int bit[n];//保存位串
int start;//编码起始位置
char name[5];
}Hcodetype;
void select(Htreetype tree[],int position,int *node1,int *node2);//选择两个权值最⼩的点（代价最⼩）
void HuffmanTree(Htreetype t[]);//构造哈夫曼树，⽤到了select选择节点
void HuffmanCode(Hcodetype code[],Htreetype tree[]);//开始编码
void show(Htreetype tree[],Hcodetype code[]);//显⽰编码
c语言和c++区别int main(){
Htreetype tree[m];//有m个位置的空树
Hcodetype code[n];//n个编码位置
HuffmanCode(code,tree);//编码完成
show(tree,code);//输出
return 0;
}
void select(Htreetype tree[],int position,int *node1,int *node2){
//tree是哈夫曼树 position是到第⼏个节点之前的都要检索 node1 和node2 保存两个权值最⼩的节点的位置
//⼀共n个待记录点，n -- m⾥⾯的是⽣成树的时候新根节点，⾥⾯放的是权值，当⽣成了新根节点，查最⼩就要从头到新构成的位置
*node1 = *node2 = 0;
int min1,min2;
min1 = min2 = MAXVALUE;
int i;
for(i = 0; i < position; i++){
if(tree[i].parent == -1){//如果没有⽗节点说明还没有成为树的⼀部分
if(tree[i].weight < min1){//维护min1 < min2 也就是 node1的权值⼩
min2 = min1;//min2记录min1的权值
min1 = tree[i].weight;//min1的值更新
*node2 = *node1;//抛弃当前两个节点中⼤的那个重新记录
*node1 = i;
}else if(tree[i].weight < min2){//前⾯的min1没有这个⼩但是min2⽐这个⼩所以直接⽤min2记录，这样就不⽤对两个节点都⽐较之后才换节点    min2 = tree[i].weight;
*node2 = i;
}
}
}
}
void HuffmanTree(Htreetype tree[]){
int i;//for循环的计数器
int node1,node2;//权值最⼩的两个节点位置
node1 = node2 = 0;
char name[5];//暂存姓名
int now_weight;//暂存权值
for(i = 0; i < m; i++){//⼀共n个节点，则需要构建m个点存储信息 m = (2*n - 1)
tree[i].weight = 0;//没有权值
tree[i].parent = -1;
tree[i].Lchild = -1;
tree[i].Rchild = -1;
}
printf("⼀共有%d个⼈\n",n);//构造节点信息
for(i = 0; i < n; i++){//输⼊基本信息
printf("请输⼊姓名：");
scanf("%s",&name);
printf("请输⼊成绩：");
scanf("%d",&now_weight);
strcpy(tree[i].name,name);
tree[i].weight = now_weight;
}
for(i = n; i < m; i++){//构造哈夫曼树
select(tree,i,&node1,&node2);//选好两个节点
tree[node1].parent = i;//选好的两个节点形成了树
tree[node2].parent = i;//⽣成的节点放在当前位置
tree[i].Lchild = node1;//node1权值⼩，也就是左⼦树权值都⼩
tree[i].Rchild = node2;
tree[i].weight = tree[node1].weight + tree[node2].weight;//⽣成新树完成
}
}
void HuffmanCode(Hcodetype code[],Htreetype tree[]){//code存放每个节点的编码对应0 --- (n - 1)个节点编码 int i;//计数器
int parent_position,now_position;
Hcodetype cd;//暂时存放编码
HuffmanTree(tree);//构造好霍夫曼树了在 tree⾥⾯
for(i = 0; i < n; i++){//给n个节点编码
cd.start = n;//最长为n
strcpy(cd.name,tree[i].name);//将名字也放进⾥⾯，可省略换其余⽅式输出
now_position = i;//从每个节点向上
parent_position = tree[i].parent;//到对应的⽗节点看⾃⼰当前编码为0还是1
while(parent_position != -1){//没有到最底层的树
cd.start--;
if(tree[parent_position].Lchild == now_position){//当前位置的是⽗节点的左孩⼦则为0
cd.bit[cd.start] = '0';
}else
cd.bit[cd.start] = '1';
now_position = parent_position;//向上移动⼀定要移动
parent_position = tree[now_position].parent;
}
code[i] = cd;//对第i个节点编码完成后放进code中
}
}
void show(Htreetype tree[],Hcodetype code[]){//显⽰编码
int i,j;//计数器
for(i = 0; i < n; i++){
printf("%s          ",code[i].name);
for(j = code[i].start; j < n; j++)
printf("%c ",code[i].bit[j]);
printf("\n");
}
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。