哈弗曼树

程序员文章站 2022-07-14 19:21:52

...

例子

输入

输入的第一行包含一个正整数n，表示共有n个字符需要编码。其中n不超过100。

第二行中有n个用空格隔开的正整数，分别表示n个字符的权值。

输出

共n行，每行一个字符串，表示对应字符的赫夫曼编码。

样例输入

8
5 29 7 8 14 23 3 11

样例输出

0110
10
1110
1111
110
00
0111
010

建树

思路

建立哈弗曼树的叶子节点数量不会太多，否则哈弗曼编码过长
所以写树的静态写法较简单

数据结构

哈夫曼树的节点需要存储权值和指针域
指针域为左右孩子和父亲，这才能确定一个节点在树中的位置且能向上向下遍历皆可
因为是静态写法，所以指针域的类型为int即可，而每个节点的编号即为它在数组中下标的编号
哈夫曼树（一个2*n-1大小的数组，存放了所有节点，通过有无根节点判断节点在其子树的位置）
设为数组指针好在多点测试中分配和释放空间
哈夫曼编码
设为数组指针好在多点测试中分配和释放空间
权值数组arr,叶子节点数n，节点总数m
每个节点的编号为 1 ~ m 不会重复，方便访问任何一个节点（叶子节点按输入顺序为1 ~ n）

#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct HT {//HFMTree
    int weight;
    int parent, lch, rch;
};
HT *huffTree;//哈夫曼树（一个2*n-1大小的数组，存放了所有数组，通过有无根节点判断节点位置）
string *hfCode;//哈夫曼编码
int arr[105], n,m;//权值数组arr,叶子节点数n，节点总数m

主函数

输入叶子节点数n
依次输入权值数组arr的值
哈弗曼树节点的总数=叶子节点*2 - 1： m=2 * n - 1
分配空间
分配哈弗曼树HT数组（m个节点）
分配哈弗曼编码string数组（n个叶子节点）
HFM建树
HFM编码
输出1 ~ n的叶子节点的HFM编码（1 ~ n就是输入的顺序）
释放空间
释放哈弗曼树HT数组分配的空间
释放哈弗曼编码string数组分配的空间

int main() {
    int i;
    while (scanf("%d",&n)!=EOF) {
        for (i = 1; i <= n; i++)
            scanf("%d",&arr[i]);

        m = 2 * n - 1;//节点总数=2*叶子节点-1
        huffTree = new HT[m + 1];//分配哈弗曼树HT数组（m个节点）
        hfCode = new string[n+1];//分配哈弗曼编码string数组（n个叶子节点）

        HFMCreate();
        HFMCoding();
        for (i = 1; i <= n; i++)
            cout<<hfCode[i]<<endl;

        delete [] huffTree;//释放哈弗曼树HT数组 分配的空间
        delete [] hfCode;//释放哈弗曼编码string数组 分配的空间
    }
    return 0;
}

HFM建树（子函数：初始化+找最小两点，然后在函数内遍历补充树的信息）

如果总结点数<=1那么就没有把节点相连的必要，直接返回：只有一个点或者无点
对所有节点 huffTree[i] 进行初始化（1 ~ m）
叶子节点1 ~ n的权值为arr[i]（i属于1~n，0不存放东西）
所有的节点的指针域一开始都指向0（相当于指向NULL）
建树（对n+1 ~ m的非叶子节点及其左右孩子遍历，进行赋值）
3.1找出当前为根节点的节点中权值最小的两个节点
如何寻找最小权值的两个节点：
（1）写入一个形参high=i-1作为遍历的范围[1,high]，因为当前要写入的是第i个节点，那么前面1~ i-1的节点都是已有权值的节点了
（2）遍历寻找最小值，其编号返回s1，第二次遍历寻找次小值（刨除了最小值后该范围内的最小值）
（3）符合更小的条件
（3.1）parent=0表示其是本身所在子树的根节点所在位置（可以是单独叶子节点为树，或者两个叶子节点相加后的子树的根节点位置）只有没有父亲，其为自己所在子树的根节点的节点才可以选为最小的两个
（3.2）min > huffTree[i].weight比当前最小值还小
（3.3）若是求次小值还要求刨除最小值：i != s1
3.2根据最小权值的两个节点建立huffTree[i]

//找出最小的两个权值的节点
//parent=0表示其是该子树的根节点所在位置，可以是单独叶子节点为树，或者两个叶子节点相加后的子树的根节点位置
//只有没有父亲，其为自己所在子树的根节点的节点才可以选为最小的两个
void selectMinTwo(int high, int &s1, int &s2) {
    int min = INF;
    //最小点
    for (int i = 1; i <= high; i++) {
        if (huffTree[i].parent == 0 && min > huffTree[i].weight) {
            min = huffTree[i].weight;
            s1 = i;
        }
    }
    min = INF;
    //同上，找次小点
    for (int i = 1; i <= high; i++) {
        if (huffTree[i].parent == 0 && min > huffTree[i].weight && i != s1) {
            min = huffTree[i].weight;
            s2 = i;
        }
    }
    if (s1 > s2) {
        swap(s1, s2);
    }
}
//对所有节点的初始化
void initnode()
{
    //叶子节点的编号1~n就是按序输入的权值，所以编码时也好找到叶子节点
    //所以编码时较方便，但是找最小两个权值时较不方便，但是因为体量较小所以耗时也短
    for (int i = 1; i <= n; i++) {//初始化叶子节点
        huffTree[i].weight = arr[i];
        huffTree[i].lch = huffTree[i].rch = huffTree[i].parent = 0;
    }
    for (int i = n + 1; i <= m; ++i)//初始化非叶子节点
        huffTree[i].lch = huffTree[i].rch = huffTree[i].parent = 0;
}
//建树
void HFMCreate() {
    if (m <= 1)
        return;
    initnode();

    //建树
    for (int i = n + 1; i <= m; i++) {
        int s1, s2;
        selectMinTwo(i - 1, s1, s2);
        huffTree[i].weight = huffTree[s1].weight + huffTree[s2].weight;
        huffTree[i].lch = s1, huffTree[i].rch = s2;
        huffTree[s1].parent = huffTree[s2].parent = i;
    }
}

HFM编码（在建树的基础上获得编码）

方法一：自底向上

每个叶子节点都定义一个temp=“”暂存编码
从叶子节点往上一直找到根节点：

每次定义有节点本身及其父亲 int child = i,fa = huffTree[i].parent
一直到找到根节点（根节点的父亲=0）fa != 0
所有分支左0右1
如果该节点是其父亲的左孩子，temp+=‘0’;
如果该节点是其父亲的右孩子，temp+=‘1’;
把暂存编码temp赋给HFM编码hfCode[i]

//自底向上的哈夫曼编码
void HFMCoding() {
    for(int i =1; i<=n; ++i) {
        string temp = "";//用字符串最方便，先加的在后头
        for(int child = i,fa = huffTree[i].parent; fa != 0; child = fa,fa = huffTree[fa].parent) {
            if(huffTree[fa].lch == child)
                temp = '0' + temp;
            else
                temp = '1' + temp;
        }
        hfCode[i] = temp;
    }
}

分析的原题：问题 A: 算法6-12：自底向上的赫夫曼编码

参考：https://blog.csdn.net/morizunzhu/article/details/81488677
题目：http://codeup.cn/status.php?user_id=20170613218&cid=100000617
题目描述

在通讯领域，经常需要将需要传送的文字转换成由二进制字符组成的字符串。在实际应用中，由于总是希望被传送的内容总长尽可能的短，如果对每个字符设计长度不等的编码，且让内容中出现次数较多的字符采用尽可能短的编码，则整个内容的总长便可以减少。另外，需要保证任何一个字符的编码都不是另一个字符的编码前缀，这种编码成为前缀编码。

而赫夫曼编码就是一种二进制前缀编码，其从叶子到根（自底向上）逆向求出每个字符的算法可以表示如下：
哈弗曼树
在本题中，读入n个字符所对应的权值，生成赫夫曼编码，并依次输出计算出的每一个赫夫曼编码。

输入

输入的第一行包含一个正整数n，表示共有n个字符需要编码。其中n不超过100。

第二行中有n个用空格隔开的正整数，分别表示n个字符的权值。

输出

共n行，每行一个字符串，表示对应字符的赫夫曼编码。

样例输入

8
5 29 7 8 14 23 3 11

样例输出

0110
10
1110
1111
110
00
0111
010

提示
赫夫曼树又名最优二叉树，它是一类带权路径长度最小的二叉树。通过构造赫夫曼树，我们可以得到赫夫曼编码，从而使得通信能够得到更高的效率。在本题中，构造赫夫曼树的过程使用了从叶子到根的逆向顺序，另外，还有一种从根出发直到叶子的赫夫曼编码构造算法，这将在下一题中进行讨论。

思路

建立哈弗曼树的叶子节点数量不会太多，否则哈弗曼编码过长
所以写树的静态写法较简单

数据结构

哈夫曼树的节点需要存储权值和指针域
指针域为左右孩子和父亲，这才能确定一个节点在树中的位置且能向上向下遍历皆可
因为是静态写法，所以指针域的类型为int即可，而每个节点的编号即为它在数组中下标的编号
哈夫曼树（一个2*n-1大小的数组，存放了所有节点，通过有无根节点判断节点在其子树的位置）
设为数组指针好在多点测试中分配和释放空间
哈夫曼编码
设为数组指针好在多点测试中分配和释放空间
权值数组arr,叶子节点数n，节点总数m
每个节点的编号为 1 ~ m 不会重复，方便访问任何一个节点（叶子节点按输入顺序为1 ~ n）

#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct HT {//HFMTree
    int weight;
    int parent, lch, rch;
};
HT *huffTree;//哈夫曼树（一个2*n-1大小的数组，存放了所有数组，通过有无根节点判断节点位置）
string *hfCode;//哈夫曼编码
int arr[105], n,m;//权值数组arr,叶子节点数n，节点总数m

主函数

输入叶子节点数n
依次输入权值数组arr的值
哈弗曼树节点的总数=叶子节点*2 - 1： m=2 * n - 1
分配空间
分配哈弗曼树HT数组（m个节点）
分配哈弗曼编码string数组（n个叶子节点）
HFM建树
HFM编码
输出1 ~ n的叶子节点的HFM编码（1 ~ n就是输入的顺序）
释放空间
释放哈弗曼树HT数组分配的空间
释放哈弗曼编码string数组分配的空间

int main() {
    int i;
    while (scanf("%d",&n)!=EOF) {
        for (i = 1; i <= n; i++)
            scanf("%d",&arr[i]);

        m = 2 * n - 1;//节点总数=2*叶子节点-1
        huffTree = new HT[m + 1];//分配哈弗曼树HT数组（m个节点）
        hfCode = new string[n+1];//分配哈弗曼编码string数组（n个叶子节点）

        HFMCreate();
        HFMCoding();
        for (i = 1; i <= n; i++)
            cout<<hfCode[i]<<endl;

        delete [] huffTree;//释放哈弗曼树HT数组 分配的空间
        delete [] hfCode;//释放哈弗曼编码string数组 分配的空间
    }
    return 0;
}

HFM建树（子函数：初始化+找最小两点，然后在函数内遍历补充树的信息）

如果总结点数<=1那么就没有把节点相连的必要，直接返回：只有一个点或者无点
对所有节点 huffTree[i] 进行初始化（1 ~ m）
叶子节点1 ~ n的权值为arr[i]（i属于1~n，0不存放东西）
所有的节点的指针域一开始都指向0（相当于指向NULL）
建树（对n+1 ~ m的非叶子节点及其左右孩子遍历，进行赋值）
3.1找出当前为根节点的节点中权值最小的两个节点
如何寻找最小权值的两个节点：
（1）写入一个形参high=i-1作为遍历的范围[1,high]，因为当前要写入的是第i个节点，那么前面1~ i-1的节点都是已有权值的节点了
（2）遍历寻找最小值，其编号返回s1，第二次遍历寻找次小值（刨除了最小值后该范围内的最小值）
（3）符合更小的条件
（3.1）parent=0表示其是本身所在子树的根节点所在位置（可以是单独叶子节点为树，或者两个叶子节点相加后的子树的根节点位置）只有没有父亲，其为自己所在子树的根节点的节点才可以选为最小的两个
（3.2）min > huffTree[i].weight比当前最小值还小
（3.3）若是求次小值还要求刨除最小值：i != s1
3.2根据最小权值的两个节点建立huffTree[i]

//找出最小的两个权值的节点
//parent=0表示其是该子树的根节点所在位置，可以是单独叶子节点为树，或者两个叶子节点相加后的子树的根节点位置
//只有没有父亲，其为自己所在子树的根节点的节点才可以选为最小的两个
void selectMinTwo(int high, int &s1, int &s2) {
    int min = INF;
    //最小点
    for (int i = 1; i <= high; i++) {
        if (huffTree[i].parent == 0 && min > huffTree[i].weight) {
            min = huffTree[i].weight;
            s1 = i;
        }
    }
    min = INF;
    //同上，找次小点
    for (int i = 1; i <= high; i++) {
        if (huffTree[i].parent == 0 && min > huffTree[i].weight && i != s1) {
            min = huffTree[i].weight;
            s2 = i;
        }
    }
    if (s1 > s2) {
        swap(s1, s2);
    }
}
//对所有节点的初始化
void initnode()
{
    //叶子节点的编号1~n就是按序输入的权值，所以编码时也好找到叶子节点
    //所以编码时较方便，但是找最小两个权值时较不方便，但是因为体量较小所以耗时也短
    for (int i = 1; i <= n; i++) {//初始化叶子节点
        huffTree[i].weight = arr[i];
        huffTree[i].lch = huffTree[i].rch = huffTree[i].parent = 0;
    }
    for (int i = n + 1; i <= m; ++i)//初始化非叶子节点
        huffTree[i].lch = huffTree[i].rch = huffTree[i].parent = 0;
}
//建树
void HFMCreate() {
    if (m <= 1)
        return;
    initnode();

    //建树
    for (int i = n + 1; i <= m; i++) {
        int s1, s2;
        selectMinTwo(i - 1, s1, s2);
        huffTree[i].weight = huffTree[s1].weight + huffTree[s2].weight;
        huffTree[i].lch = s1, huffTree[i].rch = s2;
        huffTree[s1].parent = huffTree[s2].parent = i;
    }
}

HFM编码（自底向上）

每个叶子节点都定义一个temp=“”暂存编码
从叶子节点往上一直找到根节点：

每次定义有节点本身及其父亲 int child = i,fa = huffTree[i].parent
一直到找到根节点（根节点的父亲=0）fa != 0
所有分支左0右1
如果该节点是其父亲的左孩子，temp+=‘0’;
如果该节点是其父亲的右孩子，temp+=‘1’;
把暂存编码temp赋给HFM编码hfCode[i]

//自底向上的哈夫曼编码
void HFMCoding() {
    for(int i =1; i<=n; ++i) {
        string temp = "";//用字符串最方便，先加的在后头
        for(int child = i,fa = huffTree[i].parent; fa != 0; child = fa,fa = huffTree[fa].parent) {
            if(huffTree[fa].lch == child)
                temp = '0' + temp;
            else
                temp = '1' + temp;
        }
        hfCode[i] = temp;
    }
}

AC代码

//建立哈弗曼树的叶子节点数量不会太多，否则哈弗曼编码过长
//所以写树的静态写法较简单
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct HT {//HFMTree
    int weight;
    int parent, lch, rch;
};
HT *huffTree;//哈夫曼树（一个2*n-1大小的数组，存放了所有节点，通过有无根节点判断节点在其子树的位置）
string *hfCode;//哈夫曼编码
int arr[105], n,m;//权值数组arr,叶子节点数n，节点总数m

//找出最小的两个权值的节点
//parent=0表示其是该子树的根节点所在位置，可以是单独叶子节点为树，或者两个叶子节点相加后的子树的根节点位置
//只有没有父亲，其为自己所在子树的根节点的节点才可以选为最小的两个
void selectMinTwo(int high, int &s1, int &s2) {
    int min = INF;
    //最小点
    for (int i = 1; i <= high; i++) {
        if (huffTree[i].parent == 0 && min > huffTree[i].weight) {
            min = huffTree[i].weight;
            s1 = i;
        }
    }
    min = INF;
    //同上，找次小点
    for (int i = 1; i <= high; i++) {
        if (huffTree[i].parent == 0 && min > huffTree[i].weight && i != s1) {
            min = huffTree[i].weight;
            s2 = i;
        }
    }
    if (s1 > s2) {
        swap(s1, s2);
    }
}
//对所有节点的初始化
void initnode()
{
    //叶子节点的编号1~n就是按序输入的权值，所以编码时也好找到叶子节点
    //所以编码时较方便，但是找最小两个权值时较不方便，但是因为体量较小所以耗时也短
    for (int i = 1; i <= n; i++) {//初始化叶子节点
        huffTree[i].weight = arr[i];
        huffTree[i].lch = huffTree[i].rch = huffTree[i].parent = 0;
    }
    for (int i = n + 1; i <= m; ++i)//初始化非叶子节点
        huffTree[i].lch = huffTree[i].rch = huffTree[i].parent = 0;
}
//建树
void HFMCreate() {
    if (m <= 1)
        return;
    initnode();

    //建树
    for (int i = n + 1; i <= m; i++) {
        int s1, s2;
        selectMinTwo(i - 1, s1, s2);
        huffTree[i].weight = huffTree[s1].weight + huffTree[s2].weight;
        huffTree[i].lch = s1, huffTree[i].rch = s2;
        huffTree[s1].parent = huffTree[s2].parent = i;
    }
}

//自底向上的哈夫曼编码
void HFMCoding() {
    for(int i =1; i<=n; ++i) {
        string temp = "";//用字符串最方便，先加的在后头
        for(int child = i,fa = huffTree[i].parent; fa != 0; child = fa,fa = huffTree[fa].parent) {
            if(huffTree[fa].lch == child)
                temp = '0' + temp;
            else
                temp = '1' + temp;
        }
        hfCode[i] = temp;
    }
}
int main() {
    int i;
    while (scanf("%d",&n)!=EOF) {
        for (i = 1; i <= n; i++)
            scanf("%d",&arr[i]);

        m = 2 * n - 1;//节点总数=2*叶子节点-1
        huffTree = new HT[m + 1];//分配哈弗曼树HT数组（m个节点）
        hfCode = new string[n+1];//分配哈弗曼编码string数组（n个叶子节点）

        HFMCreate();
        HFMCoding();
        for (i = 1; i <= n; i++)
            cout<<hfCode[i]<<endl;

        delete [] huffTree;//释放哈弗曼树HT数组 分配的空间
        delete [] hfCode;//释放哈弗曼编码string数组 分配的空间
    }
    return 0;
}

方法二：自顶向下

从根出发，遍历整棵赫夫曼树从而求得各个叶子结点所表示的字符串。
有两种，一种是递归，一种是递推

1.递归

递归边界为到达叶子节点：左右孩子都为0
递归式就是不断向其左右孩子遍历，左0右1
若向左孩子遍历则暂存编码code+‘0’
若向右孩子遍历则暂存编码code+‘1’

//HFM编码,递归
void HFMCode(int index,string code){
    if(huffTree[index].lch==0&&huffTree[index].rch==0){
        hfCode[index]=code;
    }
    else{
        if(huffTree[index].lch!=0)
            HFMCode(huffTree[index].lch,code+'0');
        if(huffTree[index].rch!=0)
            HFMCode(huffTree[index].rch,code+'1');
    }
}

AC代码

#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct HT {//HFMTree
    int weight;
    int parent, lch, rch;
};
HT *huffTree;//哈夫曼树（一个2*n-1大小的数组，存放了所有节点，通过有无根节点判断节点在其子树的位置）
string *hfCode;//哈夫曼编码
int arr[105], n,m;//权值数组arr,叶子节点数n，节点总数m

//找出最小的两个权值的节点
//parent=0表示其是该子树的根节点所在位置，可以是单独叶子节点为树，或者两个叶子节点相加后的子树的根节点位置
//只有没有父亲，其为自己所在子树的根节点的节点才可以选为最小的两个
void selectMinTwo(int high, int &s1, int &s2) {
    int min = INF;
    //最小点
    for (int i = 1; i <= high; i++) {
        if (huffTree[i].parent == 0 && min > huffTree[i].weight) {
            min = huffTree[i].weight;
            s1 = i;
        }
    }
    min = INF;
    //同上，找次小点
    for (int i = 1; i <= high; i++) {
        if (huffTree[i].parent == 0 && min > huffTree[i].weight && i != s1) {
            min = huffTree[i].weight;
            s2 = i;
        }
    }
    if (s1 > s2) {
        swap(s1, s2);
    }
}
//对所有节点的初始化
void initnode() {
    //叶子节点的编号1~n就是按序输入的权值，所以编码时也好找到叶子节点
    //所以编码时较方便，但是找最小两个权值时较不方便，但是因为体量较小所以耗时也短
    for (int i = 1; i <= n; i++) {//初始化叶子节点
        huffTree[i].weight = arr[i];
        huffTree[i].lch = huffTree[i].rch = huffTree[i].parent = 0;
    }
    for (int i = n + 1; i <= m; ++i)//初始化非叶子节点
        huffTree[i].lch = huffTree[i].rch = huffTree[i].parent = 0;
}
//建树
void HFMCreate() {
    if (m <= 1)
        return;
    initnode();

    //建树
    for (int i = n + 1; i <= m; i++) {
        int s1, s2;
        selectMinTwo(i - 1, s1, s2);
        huffTree[i].weight = huffTree[s1].weight + huffTree[s2].weight;
        huffTree[i].lch = s1, huffTree[i].rch = s2;
        huffTree[s1].parent = huffTree[s2].parent = i;
    }
}

//HFM编码,递归
void HFMCode(int index,string code){
    if(huffTree[index].lch==0&&huffTree[index].rch==0){
        hfCode[index]=code;
    }
    else{
        if(huffTree[index].lch!=0)
            HFMCode(huffTree[index].lch,code+'0');
        if(huffTree[index].rch!=0)
            HFMCode(huffTree[index].rch,code+'1');
    }
}
int main() {
    int i;
    while (scanf("%d",&n)!=EOF) {
        for (i = 1; i <= n; i++)
            scanf("%d",&arr[i]);

        m = 2 * n - 1;//节点总数=2*叶子节点-1
        huffTree = new HT[m + 1];//分配哈弗曼树HT数组（m个节点）
        hfCode = new string[n+1];//分配哈弗曼编码string数组（n个叶子节点）

        HFMCreate();
        string codet = "";
        HFMCode(m,codet);

        for (i = 1; i <= n; i++)
            cout<<hfCode[i]<<endl;

        delete [] huffTree;//释放哈弗曼树HT数组 分配的空间
        delete [] hfCode;//释放哈弗曼编码string数组 分配的空间
    }
    return 0;
}

2.递推

类似先序遍历：左右根

先遍历左孩子直到某一点无下级，每次暂存编码codet = codet + ‘0’;

哈夫曼树是扩充二叉树：无孩子为1的节点；无左孩子就无右孩子
遍历到无下级然后把暂存编码code赋给HFM编码hfCode[i]（赋值可在无左孩子/右孩子中做，因为无左孩子就无右孩子）

先遍历左孩子直到某一点无下级（同上），每次暂存编码codet = codet + ‘1’;
左右孩子都已经遍历过了，返回父亲节点，暂存编码回退一位（赋值为和原来相比少一位的编码：codet = codet.substr(0, codet.length() - 1);）
比如说该点为父亲的左孩子，返回父亲再去遍历其右孩子
比如说该点为父亲的右孩子，说明父亲的左右孩子都已遍历过了，再返回父亲的父亲

//HFM编码
void HFMCode() {
	for (int i = 1; i <= m; i++) {
		huffTree[i].weight = 0;
	}
	int index = m;
	string codet = "";

	while (index) {//有点像BFS
		if (huffTree[index].weight == 0) {//未判断过是否有左孩子
			huffTree[index].weight = 1;
			if (huffTree[index].lch != 0) {
				codet = codet + '0';
				index = huffTree[index].lch;
			}
			else//在无下级左孩子时，即无下级 
				hfCode[index] = codet;
		}
		else if (huffTree[index].weight == 1) {//未判断过是否有右孩子
			huffTree[index].weight = 2;
			if (huffTree[index].rch != 0) {
				codet = codet + '1';
				index = huffTree[index].rch;
			}
//			else//在无下级右孩子时，即无下级 
//				hfCode[index] = codet;
		}
		else {//左右孩子都已经遍历过了，返回父亲节点
			//（比如说该点为父亲的左孩子，返回父亲再去遍历其右孩子）
			//（比如说该点为父亲的右孩子，说明父亲的左右孩子都已遍历过了，再返回父亲的父亲）
			
			index = huffTree[index].parent;
			codet = codet.substr(0, codet.length() - 1);
			//huffTree[index].weight = 0;
		}
	}
}

AC代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int arr[105], n, m;
struct HT {
	int weight;
	int parent, lch, rch;
};
HT *huffTree;
string *hfCode;
//找最小两个值
void selectMinTwo(int high, int &s1, int &s2) {
	int min = INF;
	for (int i = 1; i <= high; i++) {
		if (huffTree[i].parent == 0 && min > huffTree[i].weight) {
			min = huffTree[i].weight;
			s1 = i;
		}
	}
	min = INF;
	for (int i = 1; i <= high; i++) {
		if (huffTree[i].parent == 0 && min > huffTree[i].weight && i != s1) {
			min = huffTree[i].weight;
			s2 = i;
		}
	}
	if (s1 > s2) {
		swap(s1, s2);
	}
}
//建树
void HFMCreate() {
	if (n <= 1)
		return;

	for (int i = 1; i <= n; i++) {
		huffTree[i].weight = arr[i];
		huffTree[i].lch = huffTree[i].rch = huffTree[i].parent = 0;
	}
	for (int i = n + 1; i <= m; ++i) {
		huffTree[i].lch = huffTree[i].rch = huffTree[i].parent = 0;
	}
	for (int i = n + 1; i <= m; i++) {
		int s1, s2;
		selectMinTwo(i - 1, s1, s2);
		huffTree[i].weight = huffTree[s1].weight + huffTree[s2].weight;
		huffTree[i].lch = s1, huffTree[i].rch = s2;
		huffTree[s1].parent = huffTree[s2].parent = i;
	}
}
//HFM编码
void HFMCode() {
	for (int i = 1; i <= m; i++) {
		huffTree[i].weight = 0;
	}
	int index = m;
	string codet = "";

	while (index) {//有点像BFS
		if (huffTree[index].weight == 0) {//未判断过是否有左孩子
			huffTree[index].weight = 1;
			if (huffTree[index].lch != 0) {
				codet = codet + '0';
				index = huffTree[index].lch;
			}
			else//在无下级左孩子时，即无下级 
				hfCode[index] = codet;
		}
		else if (huffTree[index].weight == 1) {//未判断过是否有右孩子
			huffTree[index].weight = 2;
			if (huffTree[index].rch != 0) {
				codet = codet + '1';
				index = huffTree[index].rch;
			}
//			else//在无下级右孩子时，即无下级 
//				hfCode[index] = codet;
		}
		else {//左右孩子都已经遍历过了，返回父亲节点
			//（比如说该点为父亲的左孩子，返回父亲再去遍历其右孩子）
			//（比如说该点为父亲的右孩子，说明父亲的左右孩子都已遍历过了，再返回父亲的父亲）
			
			index = huffTree[index].parent;
			codet = codet.substr(0, codet.length() - 1);
			//huffTree[index].weight = 0;
		}
	}
}
int main() {
	int i;
	while (cin >> n) {
		for (i = 1; i <= n; i++) {
			cin >> arr[i];
		}
		m = 2 * n - 1;
		huffTree = new HT[m + 1];
		hfCode = new string[n + 1];
		fill(hfCode, hfCode + n + 1, "");

		HFMCreate();
		HFMCode();
		for (i = 1; i <= n; i++) {
			cout << hfCode[i] << endl;
		}
		delete[] huffTree;
		delete[] hfCode;
	}
	return 0;
}

上一篇： Codeup 21142: 合并果子（贪心哈弗曼编码）

下一篇： Samba中文乱码解决方法

哈弗曼树

文章目录

例子

建树

思路

数据结构

主函数

HFM建树（子函数：初始化+找最小两点，然后在函数内遍历补充树的信息）

HFM编码（在建树的基础上获得编码）

方法一：自底向上

分析的原题：问题 A: 算法6-12：自底向上的赫夫曼编码

思路

数据结构

主函数

HFM建树（子函数：初始化+找最小两点，然后在函数内遍历补充树的信息）

HFM编码（自底向上）

AC代码

方法二：自顶向下

1.递归

AC代码

2.递推

AC代码

java实现哈夫曼压缩的实例

哈曼在华推定制车联网方案，满足市场需求

哈弗h2最新报价是多少，哈弗h2有哪些优缺点！

哈弗h2最新报价是多少，哈弗h2有哪些优缺点！

三星牌哈曼卡顿条形音响发布：7.1.4杜比全景声

国五促销季，购车正当时，实力派哈弗H9千万不容错过！

【数据结构与算法】二叉树——哈夫曼编码

哈夫曼树的构建（C语言）

哈夫曼编码的理解(Huffman Coding)

BZOJ4198: [Noi2015]荷马史诗(哈夫曼树)