作業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;
}