一．背景介紹：
給定n個(gè)權(quán)值作為n個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點(diǎn)離根較近。
二．實(shí)現(xiàn)步驟：
1.構(gòu)造一棵哈夫曼樹
2.根據(jù)創(chuàng)建好的哈夫曼樹創(chuàng)建一張哈夫曼編碼表
3.輸入一串哈夫曼序列，輸出原始字符
三．設(shè)計(jì)思想：
1.首先要構(gòu)造一棵哈夫曼樹，哈夫曼樹的結(jié)點(diǎn)結(jié)構(gòu)包括權(quán)值，雙親，左右孩子；假如由n個(gè)字符來構(gòu)造一棵哈夫曼樹，則共有結(jié)點(diǎn)2n-1個(gè)；在構(gòu)造前，先初始化，初始化操作是把雙親，左右孩子的下標(biāo)值都賦為0；然后依次輸入每個(gè)結(jié)點(diǎn)的權(quán)值
2.第二步是通過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）.就這樣通過n-1循環(huán)下、操作，創(chuàng)建了一棵哈夫曼樹，其中，前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)，把編碼存在編碼表中，然后開始編碼下一個(gè)字符（葉子）
4．譯碼的思想是循環(huán)讀入一串哈夫曼序列，讀到“0”從根結(jié)點(diǎn)的左孩子繼續(xù)讀，讀到“1”從右孩子繼續(xù)，如果讀到一個(gè)結(jié)點(diǎn)的左孩子和右孩子是否都為0，如果是說明已經(jīng)讀到了一個(gè)葉子（字符），翻譯一個(gè)字符成功，把該葉子結(jié)點(diǎn)代表的字符存在一個(gè)存儲翻譯字符的數(shù)組中，然后繼續(xù)從根結(jié)點(diǎn)開始讀，直到讀完這串哈夫曼序列，遇到結(jié)束符便退出翻譯循環(huán)
四．源代碼：
哈夫曼編碼譯碼
五．運(yùn)行截圖：
