【哈夫曼树（哈夫曼编码）】进阶实验4-3.5 哈夫曼编码 + 基础实验4-2.7 修理牧场

欢迎观看我的博客，如有问题交流，欢迎评论区留言，一定尽快回复！（大家可以去看我的专栏，是所有文章的目录）
文章字体风格：
红色文字表示：重难点
蓝色文字表示：思路以及想法

1. 什么是哈夫曼树

若一个二叉树的带权路径长度达到最小，称这样的二叉树为最优二叉树。 （什么是带权路径长度呢？就是一个二叉树的叶子节点上的权值（权值不是叶子结点的所表示的数据，而就是一个值两点之间的路径值，） 乘以 该叶子结点所在的层数）
并且哈夫曼树中，只有叶子结点才是所代表的节点（其余节点，其实是在创建过程中，补充的节点，接下来的哈夫曼树的创建，就明白了。）

2. 哈夫曼树的创建

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，哈夫曼树的构造规则为：

1. 将w1、w2、…，wn看成是有n 棵树的森林（每棵树仅有一个结点）；
2. 在森林中选出根结点的权值最小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
3. 从森林中删除选取的两棵树，并将新树加入森林；
4. 重复（02）、（03）步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

以{5，6，7，8，15}为例，来构造一棵哈夫曼树

由图可以看出，类似于11,15，26都是补充的，而不是原本的节点。所以，哈夫曼树中叶子结点才是最重要的

3. 哈夫曼树的应用（哈夫曼编码）

哈夫曼编码：
哈夫曼树可以直接应用于通信及数据传送中的二进制编码。设： D=｛d1，d2，d3…dn｝为需要编码的字符集合。
W=｛w1，w2，w3，…wn｝为D中各字符出现的频率。 现要对D中的字符进行二进制编码，使得：
（1） 按给出的编码传输文件时，通信编码的总长最短。
（2） 若di不等于dj，则di的编码不可能是dj的编码的开始部分（前缀）。
满足上述要求的二进制编码称为最优前缀编码。 上述要求的第一条是为了提高传输的速度，第二条是为了保证传输的信息在译码时无二性，所以在字符的编码中间不需要添加任意的分割符。
对于这个问题，可以利用哈夫曼树加以解决：用d1，d2，d3…dn作为外部结点，用w1，w2，w3…wn作为外部结点的权，构造哈夫曼树。在哈夫曼树中把从每个结点引向其左子结点的边标上二进制数“0”，把从每个结点引向右子节点的边标上二进制数“1”，从根到每个叶结点的路径上的二进制数连接起来，就是这个叶结点所代表字符的最优前缀编码。通常把这种编码称为哈夫曼编码。例如：
D=｛d1，d2，d3，d4，d5，d6，d7，d8，d9，d10，d11，d12，d13｝ W=｛2，3，5，7，11，13，17，19，23，29，31，37，41｝ 利用哈夫曼算法构造出如下图所示的哈夫曼树：

从而得到各字符的编码为：

d1:1011110 d2:1011111

d3:101110 d4:10110

d5:0100 d6:0101

d7:1010 d8:000

d9:001 d10:011

d11:100 d12:110

d13:111

编码的结果是，出现频率大的字符其编码较短，出现频率较小的字符其编码较长。

4. 哈夫曼编码的例题

1. 进阶实验4-3.5 哈夫曼编码

原题链接

思路：

判断哈夫曼编码有两个条件：

1. WPL最小（由于本题所给的数据是编码，不能求最短带径长度，我们可以通过每个节点出现的总次数，和编码出现的总次数 判断是否相等
   原因是：题中所给信息，比如一个节点出现了6次，那么说明在我们所编码的哈夫曼树中，比如000就是这个出现六次的节点，那么说明在哈夫曼树中，我们需要遍历6次000，那我们怎么统计出现了6次的000呢？我们只需要在创建哈夫曼树中，用6表示一个节点，那么我们就可以统计出现次数，因为这样构建的哈夫曼树的所有数值相加起来，一定就是所有编码出现的总次数！
   （原因如下：
   
2. 一个编码不能是其他编码的前缀

#include 
#include 
#include 
using namespace std;
int sum=0;
bool Check(int *a,string *ss,int n)
{
    int len=0;
    string l,s;
    int c;
    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            c=min(ss[i].length(),ss[j].length());
            if(ss[i].substr(0,c)==ss[j].substr(0,c))//检查是否存在一个编码是另一个编码的前缀
            {
                return false;
            }
        }
        len+=a[i]*ss[i].length();
    }
    if(len!=sum)//如果长度不是最短长度
        return false;
    return true;
}
int main()
{
    priority_queue<int,vector<int>,greater<int> > Q;
    string ss[1001],s,code[1001];
    int n,n2,a[1001],t=0;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>ss[i];
        cin>>a[i];
        Q.push(a[i]);
    }
    while(Q.size()>1)//求最短编码的长度
    {
        t=0;
        t+=Q.top();
        Q.pop();
        t+=Q.top();
        Q.pop();
        sum+=t;
        Q.push(t);
    }
    cin>>n2;
    for(int i=0; i<n2; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin>>s;
            cin>>code[j];
        }
        if(Check(a,code,n)==true)
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

补充：1. 利用优先队列构建 哈夫曼树 priority_queue,greater > Q;

priority_queue<int,vector<int>,greater<int> > Q;
1

补充：2. 判断是否为 前缀 substr

2. 基础实验4-2.7 修理牧场

//哈夫曼树
#include
using namespace std;
int main(){
   priority_queue <int,vector<int>,greater<int> > q;//优先队列 中 升序队列
    int N,i,j,k,a[10000],d[10000],sum=0;
    scanf("%d",&N);
    for(i=0;i<N;i++){
        scanf("%d",&a[i]);
    }
    for(i=0;i<N;i++){
        q.push(a[i]);
    }
    while(!q.empty()&&q.size()!=1){
        int temp1= q.top();//先访问 再弹出 
        q.pop();
        int temp2= q.top();
        q.pop();
        int temp=temp1+temp2;
        sum+=temp;
        q.push(temp);
    }  
    printf("%d",sum);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24