#include
#include
using?namespace?std;
//哈夫曼樹的存儲表示
typedef?char?ElemType;
typedef?struct
{
????ElemType?data;??????????????//結點存的數據
????int?weight;?????????????????//結點的權值
????int?parentlchildrchild;???//結點的雙親、左孩子、右孩子的下標
}?HTNode*HuffmanTree;??????????//動態分配數組存儲哈夫曼樹
void?Select（HuffmanTree?HTint?nint?&s1int?&s2）;
//構造哈夫曼樹
/*算法步驟：
1.初始化：首先動態申請2n個單元，然后循環2n-1次，從1號單元開始，依次將1至2n-1所有單元中的雙親、左孩子、右孩子
的下標都初始化為0；最后再循環n次，輸入前n個單元中葉子節點的權值
2.創建樹：循環n-1次，通過n-1次的選擇、刪除與合并來創建哈夫曼樹。
選擇是從當前森林中選擇雙親為0且權值最小的兩個樹根結點s1和s2；
刪除是指將結點s1和s2的雙親改為非0；合并就是將s1和s2的權值和作為一個新結點的權值依次存入到數組的第n+1之后的單元中，
同時記錄這個新結點左孩子的下標為s1，右孩子的下標為s2*/
void?CreateHuffmanTree（HuffmanTree?&HTint?n）
{
????//構造哈夫曼樹HT
????if（n<=1）
????{
????????cout<<“HuffmanTree節點數輸入錯誤！“<????????return;
????}
????int?m=2*n-1;
????int?s1=1s2=1;
????HT=new?HTNode[m+1];?????????//0號單元未用，所以需要動態分配m+1個單元，HT[m]表示根結點
????for（int?i=1;?i<=m;?++i）?????//將1~m號單元中的雙親、左孩子、右孩子的下標都初始化為0
????{
????????HT[i].parent=0;
????????HT[i].lchild=0;
????????HT[i].rchild=0;
????}
????for（int?i=1;?i<=n;?++i）?????//輸入前n個單元中葉子結點的權值（包括空格）
????{

????????cout<<“請輸入第“<????????char?c;//用來保存之前鍵入的回車鍵
????????c=cin.get（）;
????????HT[i].data=cin.get（）;
????????cout<<“請輸入第“<????????cin>>HT[i].weight;
????}
????//--------------------------初始化工作結束，下面開始創建完整哈夫曼樹
????for（int?i=n+1;?i<=m;?++i）
????{
????????//通過n-1次的選擇、刪除、合并來創建哈夫曼樹
????????Select（HTi-1s1s2）;???????????????????????//在HT[k]（1<=k<=i-1）中選擇兩個其雙親域為0且權值最小的結點，并返回它們在HT中的序號s1和s2
????????HT[s1].parent=i;
????????HT[s2].parent=i;????????????//得到新結點i，從森林中刪除s1，s2，將s1和s2的雙親域由0改為i
????????HT[i].lchild=s1;
????????HT[i].rchild=s2;????????????//s1，s2分別作為i的左右孩子
????????HT[i].weight=HT[s1].weight+HT[s2].weight;???//i的權值為左右孩子權值之和
????}
}
//在HT中選擇兩個其雙親域為0且權值最小的結點，返回它們在HT中的序號s1和s2
void?Select（HuffmanTree?HTint?nint?&s1int?&s2）
{
????int?i=1;//開始初始化wetmin1wetmin2，使用一個i往后找，HT[i].parent==0的結點
????int?temp;
????int?wetmin1wetmin2;
????//開始尋找前兩個HT[i].parent==0的結點，給wetmin1wetmin2初始化
????while（HT[i].parent!=0）
????????i++;
????wetmin1=HT[i].weight;
????s1=i;
????i++;
????while（HT[i].parent!=0）
????????i++;
????wetmin2=HT[i].weight;
????s2=i;
????i++;//從初始值后面的結點開始遍歷
????//初始化wetmin1wetmin2，將小的賦值給wetmin1
????if（wetmin1>wetmin2）
????{
????????temp=wetmin2;
????????wetmin2=wetmin1;
????????wetmin1=temp;
????????temp=s2;
????????s2=s1;
????????s1=temp;
????}
????for（i;?i<=n;?i++）
????{
????????if（HT[i].parent==0&&HT[i].weight????????{
????????????wetmin2=wetmin1;
????????????wetmin1=HT[i].weight;
????????????s2=s1;
????????????s1=i;
????????}
????????else?if（HT[i].parent==0&&HT[i].weight????????{
????????????wetmin2=HT[i].weight;
????????????s2=i;
????????}
????}
}
//哈夫曼編碼表的的存儲表示
typedef?char?**HuffmanCode;//動態分配數組存儲哈夫曼編碼表
//根據哈夫曼樹求哈夫曼編碼
void?CreateHuffmanCode（HuffmanTree?HTHuffmanCode?&HCint?&n）
{
????//從葉子到根逆向求每個字符的哈夫曼編碼，存儲

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

????.CA....??????9940??2019-06-01?01:35??C++實現哈夫曼樹及哈夫曼編碼\HuffmanTree.cpp

????.CA....???1053276??2019-06-01?01:18??C++實現哈夫曼樹及哈夫曼編碼\HuffmanTree.exe

????.CA....??????9025??2019-06-01?01:18??C++實現哈夫曼樹及哈夫曼編碼\HuffmanTree.o

????.C.D...?????????0??2019-06-02?09:51??C++實現哈夫曼樹及哈夫曼編碼

-----------?---------??----------?-----??----

??????????????1072241????????????????????4