作业14-Huffman树及其应用(防止标题重复)

1-1

对N（≥2）个权值均不相同的字符构造哈夫曼树，

则树中任一非叶结点的权值一定不小于下一层任一结点的权值。(T)

[解析]我会想到 {1,1,3,5}这个序列 , 第一次构造的结点的权值确实小于{3,5}但是

之后是 2和3 构造结点,之后是 5和5 构造结点,所以还是符合条件的

2-1

对N（N≥2）个权值均不相同的字符构造哈夫曼树。

下列关于该哈夫曼树的叙述中，错误的是：(D)

A.树中一定没有度为1的结点

B.树中两个权值最小的结点一定是兄弟结点

C.树中任一非叶结点的权值一定不小于下一层任一结点的权值

D.该树一定是一棵完全二叉树

2-2

设一段文本中包含字符{a, b, c, d, e}，其出现频率相应为{3, 2, 5, 1, 1}。

则经过哈夫曼编码后，文本所占字节数为：()

A.40

B.36

C.25

D.12

[解析]求得huffman编码后,所占字节数 = ∑(频率 * 其编码长度)

2-3

设一段文本中包含4个对象{a,b,c,d}，其出现次数相应为{4,2,5,1}，

则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？(B)

A.0

B.2

C.4

D.5

[解析]求huffman编码后占的位数,与等长的做差

2-4

由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树，该树的带权路径长度为：©

A.23

B.37

C.44

D.46

[解析]这里推荐用一下:WPL = 分支结点的和

2-5

已知字符集{ a, b, c, d, e, f, g, h }。若各字符的哈夫曼编码依次是

0100, 10, 0000, 0101, 001, 011, 11, 0001，则编码序列 0100011001001011110101

的译码结果是：(D)

A.acgabfh

B.adbagbb

C.afbeagd

D.afeefgd

[解析]huffman编码是前缀码,可以唯一确定序列

2-6

若以｛4，5，6，3，8｝作为叶子节点的权值构造哈夫曼树，则带权路径长度是()。(D)

A.28

B.68

C.55

D.59

2-7

下列叙述错误的是()。(B)

A.一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和

B.当一棵具有n 个叶子结点的二叉树的WPL 值为最小时，称其树为哈夫曼树，其二叉树的形状是唯一的

C.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近

D.哈夫曼树的结点个数不能是偶数

[解析]之前的博客有相关的解释

https://blog.csdn.net/qq_45591813/article/details/109142285

2-8

哈夫曼树是n个带权叶子结点构成的所有二叉树中()最小的二叉树。©

A.权值

B.高度

C.带权路径长度

D.度

[解析]最优编码就是为了求带权路径最小的二叉树

2-9

(neuDS)在哈夫曼树中，任何一个结点它的度都是()。©

A.0或1

B.1或2

C.0或2

D.0或1或2

[解析]结点包括 需要编码的结点(叶子结点) 以及由两个结点组成的结点

7-3 哈夫曼编码 (30分)

给定一段文字，如果我们统计出字母出现的频率，是可以根据哈夫曼算法给出一套编码，

使得用此编码压缩原文可以得到最短的编码总长。然而哈夫曼编码并不是唯一的。

例如对字符串"aaaxuaxz"，容易得到字母 ‘a’、‘x’、‘u’、‘z’ 的出现频率对应为

4、2、1、1。我们可以设计编码 {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}，也可以用另一套

{‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}，还可以用 {‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101}，

三套编码都可以把原文压缩到 14 个字节。但是 {‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001}

就不是哈夫曼编码，因为用这套编码压缩得到 00001011001001 后，解码的结果不唯一，

“aaaxuaxz” 和 “aazuaxax” 都可以对应解码的结果。本题就请你判断任一套编码是否

哈夫曼编码。

输入格式：

首先第一行给出一个正整数 N（2≤N≤63），随后第二行给出 N 个不重复的字符及其出现频率，格式如下：

c[1] f[1] c[2] f[2] … c[N] f[N]

其中c[i]是集合{‘0’ - ‘9’, ‘a’ - ‘z’, ‘A’ - ‘Z’, ‘_’}中的字符；f[i]是c[i]的出现频率，为不超过 1000 的整数。再下一行给出一个正整数 M（≤1000），随后是 M 套待检的编码。每套编码占 N 行，格式为：

c[i] code[i]

其中c[i]是第i个字符；code[i]是不超过63个’0’和’1’的非空字符串。

输出格式：

对每套待检编码，如果是正确的哈夫曼编码，就在一行中输出"Yes"，否则输出"No"。

注意：最优编码并不一定通过哈夫曼算法得到。任何能压缩到最优长度的前缀编码

都应被判为正确。

int main()
{
	//先求得一套huffman编码
	//输入是否是huffman编码的判断条件:
	//1. 是前缀码
	//2. WPL = 自己求得的huffman的WPL
    //两条都满足才是huffman编码   
    
    //ios::sync_with_stdio(false);
    string codes[MAXN];
    int N, M;
    int f[MAXN], c[MAXN];
    //一会改一下输入，别人不人鬼不鬼的
    cin >> N;
    getchar();
    for (int i = 1; i <= N; i++)
    {
        scanf("%c %d", &c[i], &f[i]);
        getchar();
        //printf("%c %d\n", c[i], f[i]);
    }
    //getchar();
    HuffmanTree HT;
    HuffmanCoding(HT, f, N);
    
    //得到这个huffman树的带权路径长度
    int WPL = 0;
    for (int i = 1; i <= 2 * N - 1; i++)
    {
        if (HT[i].lchild != 0 && HT[i].rchild != 0)
            WPL += HT[i].weight;
    }
    //cout << WPL << endl;
    
    //
    string code[65];
    int m;
    cin >> m;
    getchar();
    while (m--)
    {
        int This_solution_weight = 0;
        for (int i = 1; i <= N; i++)
        {
            char c;
            cin >> c >> code[i];
            //cout << code[i] << endl;
            This_solution_weight += code[i].length() * f[i];
        }
        
        //最短路径大于WPL
        if (This_solution_weight > WPL)
        {
            cout << "No" << endl;
            continue;
        }

        //判断是否是前缀编码
        int flag = 0;
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (i == j) continue;

                if (code[i].length() < code[j].length()) 
                {
                    if (code[i] == code[j].substr(0, code[i].length()))
                    {
                        flag = 1;
                        break;
                    }
                }
                else if (code[i] == code[j])
                {
                    flag = 1;
                    break;
                }
            }
        }

        if (flag == 1) 
            cout << "No" << endl;
        else 
            cout << "Yes" << endl;
    }
    
    //system("pause");
    return 0;
}