哈夫曼树笔记

smallfang

2020 年 05 月 02 日

1103 次浏览

暂无评论

3311字数

算法笔记

什么是哈夫曼树？

构造一棵二叉树，若带权路径长度达到最小，称为哈夫曼树。

哈夫曼树的操作

构树:首先，以特定（暂定val）的方式排序（从小到大）放入数组a，每次执行以下步骤直至正a只剩下一个元素。

拿到a的前两个数值
将两个节点连接到一棵树。父节点即为$s1.val + s2.val$
将其父节点放入数组
重新排序数组

字符的哈夫曼编码:指代这个文本的哈夫曼编码，这个根据不同题目（不同环境）设定。但是得到方法都需要使用到哈夫曼树。例如：。其中5的哈夫曼编码就是000，6就是001，3就是1。（我们当然可以设定左子树为1，右子树为0，那么5就是111，6就是110，3就是0）.

这段文本的哈夫曼编码:即整个字符串从头至尾，每个字符的哈夫曼编码，将他们连在一起，就是这段文本的哈夫曼编码。

哈夫曼树的代码

给定一段由小写字母构成的文本，求这段文本的哈夫曼编码和每个字符的哈夫曼编码。
输入：
第一行输入n和m，分别表示文本长度和字符种类数。第二行n个字符，表示文本，保证只包含前m个小写字母。
输出：
先输出每个字符的哈夫曼编码，一行一个，再输出这段文字的哈夫曼编码。


#include <iostream>
#include <cstring>
#include <stack>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

char s[10001];
string str;
int h[229];
char b[10001];
int len, n;

struct node
{
    int lc = -1, rc = -1;
    int val, level;
    char st[1001];
    bool operator<(const node &b) const
    {
        if (level != b.level)
            return level > b.level;
        return val > b.val;
    }
    bool yz = true;
} tree[10000];

int maketree()
{
    priority_queue<node> q;
    for (int i = 'a'; i < 'a' + n; i++)
    {
        if (h[i] == 0)
        {
            continue;
        }
        node ne;
        ne.lc = -1;
        ne.rc = -1;
        ne.val = i;
        ne.level = h[i];
        q.push(ne);
    }
    while (q.size() > 1)
    {
        node s1 = q.top();
        q.pop();
        node s2 = q.top();
        q.pop();
        node ne;
        ne.lc = s1.val;
        ne.rc = s2.val;
        ne.val = s1.val + s2.val;
        ne.yz = false;
        ne.level = s1.level + s2.level;
        tree[ne.val] = ne;
        tree[s1.val] = s1;
        tree[s2.val] = s2;
        q.push(ne);
    }
    return q.top().val;
}

void dfs(int x, char *s1)
{
    if (tree[x].lc != -1)
    {
        tree[x].yz = false;
        for (int i = 0; i < strlen(s1); i++)
        {
            tree[tree[x].lc].st[i] = s1[i];
        }
        tree[tree[x].lc].st[strlen(s1)] = '0';
        dfs(tree[x].lc, tree[tree[x].lc].st);
    }
    if (tree[x].rc != -1)
    {
        tree[x].yz = false;
        for (int i = 0; i < strlen(s1); i++)
        {
            tree[tree[x].rc].st[i] = s1[i];
        }
        tree[tree[x].rc].st[strlen(s1)] = '1';
        dfs(tree[x].rc, tree[tree[x].rc].st);
    }
    tree[x].yz = true;
}

int main()
{

    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    scanf("%d%d", &len, &n);
    int i = 0, con = 0;
    getline(cin, str);
    getline(cin, str);
    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] != ' ')
        {
            h[str[i]]++;
            s[con] = str[i];
            con++;
        }
    }
    int t = maketree();
    dfs(t, "");
    for (int i = 'a'; i < 'a' + n; i++)
    {
        if (h[i] && tree[i].yz)
        {
            if (tree[i].st[strlen(tree[i].st) - 1] == '\x05')
            {
                tree[i].st[strlen(tree[i].st) - 1] = NULL;
            }
            printf("%s \n", tree[i].st);
        }
    }
    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] == ' ')
        {
            printf(" ");
            continue;
        }
        printf("%s", tree[str[i]].st);
    }
    return 0;
}