算法 哈夫曼树和哈夫曼编码

目录

前言

一，二进制转码

二，哈夫曼编码和哈夫曼树

 三，蓝桥杯 16 哈夫曼树

总结

---

前言

这个文章需要有一定的树的基础，没学过树的伙伴可以去看我博客树的文章

当我们要编码一个字符串转成二进制的时候，我们要怎么操作呢？今天我们就来踏进哈夫曼编码的大门学习怎么高效编码和转码，还有学习这个思想的算法题目

---

一，二进制转码

方法一：二进制编码

编码字符串：ABAACDC

利用二进制：A：0     B：1     C：10     D：11

那么我们就把这个字符串编码形式：0100101110

我们来分析一下这样子编码

这样转码就会有歧义。我们不难来分析一泼，其实你分析不难发现，这个前面是有相同的前缀的
我们上面圈出来就是有前缀相同的，所以我们就会出现这种歧义的情况

方法二：等长编码

利用等长编码：A：00     B：01     C：10     D：11

然后我们就把这个字符串编码形式：00010000101110

我们每次取走两个的话这样就不会有任何的错误，但是这个长度很长，不是最优的解 

 

二，哈夫曼编码和哈夫曼树

字符串：ABAACDC

A：3次     B：1次     C：2次     D：1次

我们就有了四个节点

然后我们就需要每次合并两个最下的节点

然后我们再在3，2，2里面寻找两个最小的节点进行合并，这里面有一个2是我们B和D合并的结果，然后就是寻找两个进行合并。那么就是下面这样的情况

然后我们就剩下了4和3了

以上的树的就构造好了，这也叫哈夫曼树，然后我们在这个图上面加上0和1就好了，就可以进行编码了

然后我们就可以编码
A：1     C：01     D：001     B：000
这个编码的值就是你从根部到对应的子叶节点，然后这个边的数字组合

我们编码就是1000110100101

这个是最短且没有歧义的

前缀问题：

ABCD都是为叶子节点，所以不会再A，B，C，D，这个对应的路上，所以就不会有前缀的情况

最短问题：

出现次数越多的字符，编码越短，因为在越上面
出现次数越少的字符，编码越长，因为在越下面

在权路径：

节点值*所经过的边数（表示走了多少趟数的总路径）

哈夫曼编码不唯一，但是最终的总长是一样的

 

 三，蓝桥杯 16 哈夫曼树

问题描述
　　Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。
　　给出一列数{pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：
　　1. 找到{pi}中最小的两个数，设为pa和pb，将pa和pb从{pi}中删除掉，然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。
　　2. 重复步骤1，直到{pi}中只剩下一个数。
　　在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。
　　本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。
　　例如，对于数列{pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：
　　1. 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。
　　2. 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8, 9, 10}，费用为10。
　　3. 找到{8, 9, 10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10, 17}，费用为17。
　　4. 找到{10, 17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和27加入，得到{27}，费用为27。
　　5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。
输入格式
　　输入的第一行包含一个正整数n（n<=100）。
　　接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。
输出格式
　　输出用这些数构造Huffman树的总费用。

输入样例:

在这里给出一组输入。例如：

5
5 3 8 2 9

输出样例:

在这里给出相应的输出。例如：

59

代码：

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;int main(){vector<int>number;vector<int>temp;int n=0;cin>>n;//添加元素到容器里面for(int i=0;i<n;i++){int num=0;cin>>num;number.push_back(num);}//进行排序while(!number.empty()){sort(number.begin(),number.end());int operand1=*number.begin();int operand2=0;number.erase(number.begin());//弹出对应元素if(!number.empty()){operand2=*number.begin();number.erase(number.begin());}int sumoperand=operand1+operand2;temp.push_back(sumoperand);if(!number.empty()){number.push_back(sumoperand);}}int sum=0;for(int i=0;i<temp.size();i++){sum=sum+temp[i];}cout<<sum<<endl;
}

 这个是自己写的，如果有更好地过程，可以在评论区指教

思路：

1，先创建两个容器，一个用来存放数字，一个用来存放两个数字相加和

2，先把数字放到容器里面

3，利用sort()函数进行排序，升序

4，然后不断地抽取这个容器前面两个元素进行相加

5，把相加地元素放到第二个元素里面，然后如果第一个容器为空，说明第一个容器没有可以加地了，就不放了，如果有就继续放

6，最后不断地加这个容器里面地每一个元素就好了，这个循环的次数为这个容器的大小就好了

---

总结

哈夫曼树的构造就是不断地把最小地合并得出一个数字，然后再从这些数字寻找两个最小的数字求和，不断地把数弄没有为止，注意每次求和要带上那个两个地求和地数字，编码就是再边上赋予0和1就好了