smallfang

哈夫曼树笔记
什么是哈夫曼树?构造一棵二叉树,若带权路径长度达到最小,称为哈夫曼树。哈夫曼树的操作构树:首先,以特定(暂定val...
扫描右侧二维码阅读全文
02
2020/05

哈夫曼树笔记

什么是哈夫曼树?

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

哈夫曼树的操作

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

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

字符的哈夫曼编码:指代这个文本的哈夫曼编码,这个根据不同题目(不同环境)设定。但是得到方法都需要使用到哈夫曼树。例如:。其中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;
}

如果思路上或者有任何疑问可以讨论嘛...

Last modification:May 3rd, 2020 at 03:31 pm
End.

Leave a Comment