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