關(guān)于《數(shù)據(jù)結(jié)構(gòu)》（C語(yǔ)言版）構(gòu)造赫夫曼樹的思考

方利勝

摘? 要：目前構(gòu)造赫夫曼樹的方法有時(shí)會(huì)出現(xiàn)兩種情況，而赫夫曼樹又稱“最優(yōu)二叉樹”，因此應(yīng)該是唯一的。文章通過(guò)比較兩種赫夫曼樹所生成的赫夫曼編碼，闡述了兩種赫夫曼樹何種最優(yōu)，從而實(shí)現(xiàn)了對(duì)現(xiàn)有構(gòu)造赫夫曼樹方法的補(bǔ)充和完善。

關(guān)鍵詞：赫夫曼樹;赫夫曼編碼;最優(yōu)二叉樹;數(shù)據(jù)結(jié)構(gòu)

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)志碼：A? ? ? ? ?文章編號(hào)：2095-2945（2020）26-0065-03

Abstract： At present， there are sometimes two ways to construct Huffman Tree， and Huffman Tree is also called “Optimal Binary Tree”， so it should be unique. In this paper， by comparing the Huffman Codes generated by the two Huffman Trees， the best of the two Huffman Trees is explained， thus realizing the supplement and perfection of the existing method of constructing Huffman Trees.

Keywords： Huffman Tree; Huffman Code; optimal binary tree; data structure

在實(shí)際生活中，我們常常會(huì)遇到考察最佳判斷的問(wèn)題，例如在考察課記分時(shí)，往往把百分制轉(zhuǎn)換成優(yōu)（x≥90）、良（80

又如設(shè)某工廠的某種產(chǎn)品按某種測(cè)度分等級(jí)，如表1所示：

表1 產(chǎn)品測(cè)度等級(jí)表

其中，表中“出現(xiàn)概率”是指對(duì)應(yīng)等級(jí)的產(chǎn)品的出現(xiàn)概率。圖2中給出了對(duì)應(yīng)兩種不同判定方式的二叉樹。表面看，似乎圖2（a）對(duì)應(yīng)的判定方式效率高（每個(gè)判定式都是簡(jiǎn)單的“小于等于”判斷），但分析每種等級(jí)的出現(xiàn)概率，E級(jí)只有2%，在實(shí)際中極少出現(xiàn)，而B級(jí)出現(xiàn)概率最大，在圖2（b）的判定方式中，一次“命中”的機(jī)會(huì)很大，余下的分支很少需要判斷，因此，圖2（b）的判定方式應(yīng)該效率最高[2]。

事實(shí)上，以上兩個(gè)問(wèn)題均可利用構(gòu)造赫夫曼樹的方法進(jìn)行解決。問(wèn)題一中，假設(shè)學(xué)生成績(jī)對(duì)于不及格、及格、中等、良好和優(yōu)秀的分布概率分別為5%，15%，40%，30%，10%，以它們作為葉子的權(quán)值來(lái)構(gòu)造赫夫曼樹，如圖1（b）所示，它可以是大部分的分?jǐn)?shù)值經(jīng)過(guò)較少的比較次數(shù)得到相應(yīng)的等級(jí)。

而在第二個(gè)問(wèn)題中，因?yàn)椴煌呐袆e方式，對(duì)應(yīng)不同的二叉樹，若把等級(jí)出現(xiàn)概率看作葉子的權(quán)值，則圖2（b）判定方式的選擇，實(shí)際上就是構(gòu)造赫夫曼樹的問(wèn)題。……