C语言算法-02哈夫曼树
目录
前导概念
1.结点的路径⻓度
2.树的路径⻓度
3.结点的带权路径⻓度
4.是树的带权路径⻓度（WPL）
5.应用场景
哈夫曼树
编码
定⻓编码
概念：
缺陷：
变长编码
概念：
前缀属性：
前缀码：
实现：
哈夫曼编码
哈夫曼树的特征
实现
树的存储结构：
结点结构体：
合并逻辑：
编码逻辑：
效果演示：
前导概念
1.结点的路径⻓度
从根结点到该结点的路径上的连接。如图：3结点的路径长度为3
2.树的路径⻓度
树的每个叶⼦结点的路径⻓度之和。如图：该树的路径长度
3.结点的带权路径⻓度
结点的路径⻓度与结点权值的乘积。当我们给结点指定权重，就可以计算其带权路径长度。假设上图数据就是其权重，结点11：其带权路径长度为22
4.是树的带权路径⻓度（WPL）
树的所有叶⼦结点的带权路径⻓度之和。如图：该树的带权路径长度：1*2+8*3+1*2=48
5.应用场景
在数据膨胀、信息爆炸的今天，数据压缩的意义不⾔⽽喻。谈到数据压缩，就不能不提赫夫曼（Huffman）编码，赫夫曼编码是⾸个实⽤的压缩编码⽅案，即使在今天的许多知名压缩算法⾥，依然可以⻅到赫夫曼编码的影⼦。
另外，在数据通信中，⽤⼆进制给每个字符进⾏编码时不得不⾯对的⼀个问题是如何使电⽂总⻓最短且不产⽣⼆义性。根据字符出现频率，利⽤赫夫曼编码可以构造出⼀种不等⻓的⼆进制，使编码后的电⽂⻓度最短，且保证不产⽣⼆义性。
当有了以上概念以后，我们就可以⽤WPL去判断⼀颗⼆叉树的性能。WPL的值越⼩，⼆叉树的性能越优。
哈夫曼树
这么使一棵树的WPL最小：让权重大的结点路径短，让权重小的结点路径长。其中一种方案：哈夫曼树
假设有n个节点，各有权重，初始时各自为一棵树。
选取两个结点合并：找到两个权重最小的根结点（两棵树）合并，创建一个新节点作为两个根结点的父结点，新节点的权重为了两个结点的权重和。
不断的将最小的两个根结点相结合，如下一步将结点B与新节点合并，最后将A合
最终实现使一棵树的WPL最小：让权重大的结点路径短，让权重小的结点路径长
总结一下：
目标：给定n个带权值的结点，要求这n个结点全部为一棵树的叶子节点。
实际操作：额外添加n-1个结点，构造一棵结点度只为0或2的树。（如果度为1，就使路径变长了）
编码
定⻓编码
概念：
像ASCII编码、Unicode编码。ASCII编码每⼀个字符使⽤8个bit，能够编码256个字符；Unicode编码每个字符占16个bit，能够编码65536个字符，包含所有ASCII编码的字符。
假设我们要使⽤定⻓编码对由符号A，B，C，D和E构造的消息进⾏编码，对每个字符编码需要多少位呢？⾄少需要3位，2个bit位不够表示五个字符，只能表示4个字符。
如果对DEAACAAAAABA进⾏编码呢？总共12个字符，每个字符需要3bit，总共需要36位。
缺陷：
浪费空间！对于仅包含ASCII字符的纯⽂本消息，Unicode使⽤的空间是ASCII的两倍，两种⽅式都会造成空间浪费；字符“a”和“e”的出现频率⽐“q”和“z”的出现频率⾼，但是他们都占⽤了相同位数的空间。要解决定⻓编码的缺陷，便有了下⾯的变⻓编码。
变长编码
概念：
单个编码的⻓度不⼀样，可以根据整体出现的频率来调节，出现的频率越⾼，编码⻓度越短。
变⻓编码优于定⻓编码的是，变⻓编码可以将短编码赋予平均出现频率较⾼的字符，同⼀消息的编码⻓度⼩于定⻓编码。
这个时候⼜有⼀个问题，字符有⻓有短，我们怎么知道⼀个字符从哪⾥开始，⼜从哪⾥结束呢？如果位数固定，就没这个问题了。
前缀属性：
字符集当中的⼀个字符编码不是其他字符编码的前缀，则这个字符编码具有前缀属性。
所谓前缀，⼀个编码可以被解码为多个字符，表示不唯⼀。⽐如，abcd需要编码表示，设a=0，b=10，c=110，d=11。那么110可以表示c，也可以表示da。
又比如：
| 字符 | 编码 |
|---|---|
| P | 000 |
| Q | 11 |
| R | 01 |
| S | 001 |
| T | 10 |
表中任意一个字符的编码都不是其他字符编码的前缀，故编码唯一。比如：01001101100010，有且仅有唯一翻译为 RSTQPT
前缀码：
没有任何码字是其他码字的前缀的编码
实现：
根据分析，我们可以使用哈夫曼树进行编码实现满足要求的编码。
哈夫曼编码
哈夫曼树的特征
1.哈夫曼编码基于哈夫曼树
每⽚叶⼦结点都代表⼀个字符--需要编码的数据
从结点到其左孩⼦的路径上标记1
从结点到其右孩⼦的路径上标记0
也可以左0右1
2.从根结点到包含字符的叶⼦结点的路径上获得的叶结点的编码
3.编码均具有前缀属性
每⼀个叶结点不能出现在到另⼀个叶结点的路径上
实现
树的存储结构：
需要实现编码，找路径应该是从各个叶子结点往上找，从根结点不好找到指定叶子结点。
同时在编码时的01需要通过结点的父子关系（左还是右）来判断。
所以使用双亲+孩子表示法实现---结构体数组。详见：C语言数据结构-07树_c语言 数据结构 树-CSDN博客
注：这里确定是一棵二叉树，故一个结点最多2个子节点，因此储存子结点也是直接在结构体里添加两个孩子。
结点结构体：
数据--这里省略了，之后翻译时对结构体数组指定位置的数据手动指定数据
左子结点
右子结点
权值
父结点
#include<stdio.h> #include<stdlib.h> #include<string.h> //结点结构体--这里省略了实际字符，翻译时对结构体数组指定位置的数据手动指定数据 typedef struct Node{ int w;//权重 int l,r;//左，右子结点的下标 int fa;//父结点下标 }HuffmanNode,*HuffmanTree;合并逻辑：
首先数组前n个位置对应n个数据，之后n-1个位置进行建造哈夫曼树。
进行n-1次合并。合并时，找到两个权重最小的根结点，创建一个新结点作为这两个的父结点。父该结点的权重为二者之和
//查询前i个位置的权重最小的两个根结点 void find(HuffmanTree t,int n,int* s1,int* s2){ int minn;//权重最小结点的下标 //找最小结点 for(int i=0;i<n;i++){//初始时先找一个根结点，方便后续比较 if(t[i].fa==-1){ minn=i; break; } } for(int i=0;i<n;i++){ if(t[i].fa==-1&&t[i].w<t[minn].w){//为根结点且权重更小 minn=i; } } (*s1)=minn; //找第二小 for(int i=0;i<n;i++){//初始时先找一个根结点，方便后续比较 if(t[i].fa==-1&&i!=(*s1)){ minn=i; break; } } for(int i=0;i<n;i++){ if(t[i].fa==-1&&t[i].w<t[minn].w&&i!=(*s1)){//为根结点且权重更小 minn=i; } } (*s2)=minn; } //构造哈夫曼树--指针表示结构体数组 HuffmanTree initHFMTree(int we[],int n){ int m=2*n-1;//哈夫曼树的结点数 HuffmanTree t=(HuffmanTree)malloc(sizeof(HuffmanNode)*m); //初始化放入n个数据的结点 for(int i=0;i<n;i++){ t[i].w=we[i];//权重 t[i].l=t[i].r=-1;//初始时每个结点都是一棵单独的树 t[i].fa=-1; } int s1,s2; //进行n-1次合并，形成哈夫曼树 for(int i=n;i<2*n-1;i++){ find(t,i,&s1,&s2);//找到前i个位置权重最小的两个根结点 //更新 t[i].fa=-1; t[i].l=s1; t[i].r=s2; t[i].w=t[s1].w+t[s2].w;//当前结点的权重为两个子结点的权重和 t[s1].fa=t[s2].fa=i; } return t; }编码逻辑：
初始情况将各个数据按顺序手动放入数组a。同时每个数据的权重对应放入数组w。w［i］对应的数据就是a［i］。
由于路径是从叶子结点往上找，是反的，所以将读到的编码倒着装入编码数组。
n个数据需要读取编码，一个数据使用一个数组储存，n个数据可以使用一个二维数组储存。但是每个结点的路径长度不一，因此使用二级指针模拟的的二维数组去储存。
//进行编码 char** createCodes(HuffmanTree t,int n){ //编码的临时数组，叶子节点可能的最大路径为n-1 char* temp=(char*)malloc(sizeof(char)*n); //二级指针模拟的二级数组储存所有的编码 char** codes=(char**)malloc(sizeof(char*)*n); memset(codes,0,sizeof(char*)*n);//初始化二级指针 int x,fx;//当前结点以及当前结点的父结点 int start;//存放编码的位置 for(int i=0;i<n;i++){//按顺序读取每个结点编码 start=n-1; temp[start]='\0';//最后加上一个'\0'方便读取 x=i; fx=t[x].fa; while(fx!=-1){//读到根结点结束 start--; if(t[fx].l==x) temp[start]='1';//左子结点 else temp[start]='0';//右子结点 x=fx; fx=t[x].fa; } codes[i]=(char*)malloc(sizeof(char)*(n-start)); strcpy(codes[i],&temp[start]);//从temp复制从start到最后的编码到codes } return codes; }效果演示：
int main(){ int n;//对n个字符编码，指定n<=100 char a[50];//储存字符的数组 int we[50];//对应字符的权重：a[i]的权重是we[i] scanf("%d",&n); getchar(); for(int i=0;i<n;i++){//储存字符 scanf("%c",&a[i]); } for(int i=0;i<n;i++){//储存权重 scanf("%d",&we[i]); } //构造哈夫曼树 HuffmanTree t=initHFMTree(we,n); //进行哈夫曼编码 char** codes=createCodes(t,n); for(int i=0;i<n;i++){ printf("%c %s\n",a[i],codes[i]); } return 0; } /* 9 agmteh is 1 1 1 1 2 2 3 3 5 */结果:可能会有不同，结点的左右可能交换
a 1011 g 1010 m 1001 t 1000 e 111 h 110 001 i 000 s 01