※這篇是以前投在CSDN上的，現(xiàn)在搬來(lái)b站。別的寫過(guò)的一些文章也會(huì)陸續(xù)搬過(guò)來(lái)，以后會(huì)主要考慮在b站發(fā)文章

創(chuàng)建哈夫曼樹的描述：

????????數(shù)據(jù)結(jié)構(gòu)：

????????????????數(shù)據(jù)的邏輯結(jié)構(gòu)是樹狀結(jié)構(gòu)；采用靜態(tài)的三叉鏈表存放。

????????算法思想：

????????????????1.先把三叉鏈表中N個(gè)元素進(jìn)行初始化，存放葉子節(jié)點(diǎn)，他們都沒(méi)有孩子和雙親。

????????????????2.再初始化后n-1個(gè)非葉子節(jié)點(diǎn)元素。

????????????????3.從當(dāng)前森林中（在森林中樹的根節(jié)點(diǎn)的雙親為0）選擇兩棵根的權(quán)值最小的樹；刪除合并是將選到的兩棵樹的根權(quán)和存入數(shù)組當(dāng)前最前面的空閑元素中，并置入相應(yīng)的雙親與孩子的位置。

????????????????4.重復(fù)上述步驟直到森林中只含有一棵二叉樹為止。

哈夫曼樹編碼的描述：

????????數(shù)據(jù)結(jié)構(gòu)：

????????????????數(shù)據(jù)的邏輯結(jié)構(gòu)是樹狀結(jié)構(gòu)；采用靜態(tài)的三叉鏈表存放。

????????算法思想：

????????????????1.申請(qǐng)存儲(chǔ)哈夫曼編碼串的指針數(shù)組，申請(qǐng)一個(gè)字符型指針，用來(lái)存放臨時(shí)的編碼串。

????????????????2.從葉子節(jié)點(diǎn)開始向上倒退，若其為它雙親節(jié)點(diǎn)的左孩子則編碼標(biāo)0，否則標(biāo)1；直到根節(jié)點(diǎn)為止，最后把臨時(shí)存儲(chǔ)編碼復(fù)制到對(duì)應(yīng)的指針數(shù)組所指向的內(nèi)存中。

????????????????3.重復(fù)上述步驟，直到所有的葉子節(jié)點(diǎn)都被編碼完。

哈夫曼樹譯碼的描述：

????????數(shù)據(jù)結(jié)構(gòu)：

????????????????數(shù)據(jù)的邏輯結(jié)構(gòu)是樹狀結(jié)構(gòu)；采用靜態(tài)的三叉鏈表存放。

????????算法思想：

????????????????1.從根結(jié)點(diǎn)開始向下遞推，若其編碼當(dāng)前的數(shù)值為0，則到該節(jié)點(diǎn)的左孩子，否則轉(zhuǎn)到其右孩子；重復(fù)上述步驟直到該編碼中全部訪問(wèn)完，則樹中對(duì)應(yīng)的葉子節(jié)點(diǎn)則為所求。

????????????????2.依據(jù)上述步驟，對(duì)編碼數(shù)組中所有編碼全部進(jìn)行譯碼。

算法流程：

????????1.選擇兩個(gè)權(quán)值最小的結(jié)點(diǎn)；

????????2.創(chuàng)建哈夫曼樹；

????????3.打印哈夫曼樹;

????????4.哈夫曼編碼;

????????5.哈夫曼譯碼。

程序代碼：

運(yùn)行結(jié)果：