C++哈夫曼樹(shù)編碼和譯碼的實(shí)現(xiàn)

一．背景介紹：

給定n個(gè)權(quán)值作為n個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹(shù)，若帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱(chēng)這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱(chēng)為哈夫曼樹(shù)(Huffman Tree)。哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，權(quán)值較大的結(jié)點(diǎn)離根較近。

二．實(shí)現(xiàn)步驟：

1.構(gòu)造一棵哈夫曼樹(shù)

2.根據(jù)創(chuàng)建好的哈夫曼樹(shù)創(chuàng)建一張哈夫曼編碼表

3.輸入一串哈夫曼序列，輸出原始字符

三．設(shè)計(jì)思想：

1.首先要構(gòu)造一棵哈夫曼樹(shù)，哈夫曼樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)包括權(quán)值，雙親，左右孩子；假如由n個(gè)字符來(lái)構(gòu)造一棵哈夫曼樹(shù)，則共有結(jié)點(diǎn)2n-1個(gè)；在構(gòu)造前，先初始化，初始化操作是把雙親，左右孩子的下標(biāo)值都賦為0；然后依次輸入每個(gè)結(jié)點(diǎn)的權(quán)值

    2.第二步是通過(guò)n-1次循環(huán)，每次先找輸入的權(quán)值中最小的兩個(gè)結(jié)點(diǎn)，把這兩個(gè)結(jié)點(diǎn)的權(quán)值相加賦給一個(gè)新結(jié)點(diǎn)，，并且這個(gè)新結(jié)點(diǎn)的左孩子是權(quán)值最小的結(jié)點(diǎn)，右孩子是權(quán)值第二小的結(jié)點(diǎn)；鑒于上述找到的結(jié)點(diǎn)都是雙親為0的結(jié)點(diǎn)，為了下次能正確尋找到剩下結(jié)點(diǎn)中權(quán)值最小的兩個(gè)結(jié)點(diǎn)，每次循環(huán)要把找的權(quán)值最小的兩個(gè)結(jié)點(diǎn)的雙親賦值不為0（i）.就這樣通過(guò)n-1循環(huán)下、操作，創(chuàng)建了一棵哈夫曼樹(shù)，其中，前n個(gè)結(jié)點(diǎn)是葉子（輸入的字符結(jié)點(diǎn)）后n-1個(gè)是度為2的結(jié)點(diǎn)

    3.編碼的思想是逆序編碼，從葉子結(jié)點(diǎn)出發(fā)，向上回溯，如果該結(jié)點(diǎn)是回溯到上一個(gè)結(jié)點(diǎn)的左孩子，則在記錄編碼的數(shù)組里存“0”，否則存“1”，注意是倒著存；直到遇到根結(jié)點(diǎn)（結(jié)點(diǎn)雙親為0），每一次循環(huán)編碼到根結(jié)點(diǎn)，把編碼存在編碼表中，然后開(kāi)始編碼下一個(gè)字符（葉子）

    4．譯碼的思想是循環(huán)讀入一串哈夫曼序列，讀到“0”從根結(jié)點(diǎn)的左孩子繼續(xù)讀，讀到“1”從右孩子繼續(xù)，如果讀到一個(gè)結(jié)點(diǎn)的左孩子和右孩子是否都為0，如果是說(shuō)明已經(jīng)讀到了一個(gè)葉子（字符），翻譯一個(gè)字符成功，把該葉子結(jié)點(diǎn)代表的字符存在一個(gè)存儲(chǔ)翻譯字符的數(shù)組中，然后繼續(xù)從根結(jié)點(diǎn)開(kāi)始讀，直到讀完這串哈夫曼序列，遇到結(jié)束符便退出翻譯循環(huán)

四．源代碼：

 

五．運(yùn)行截圖：