/*
**author:?Happig
**time:?2020-5-10
**function:
1、輸入一段報文，例如：?
????CAST??CAST??SAT??AT??A?TASA
????統計字符集合?{?C?A?S?T?}，以及各個字符出現的頻度（次數）?W＝{?2?7?4?5?}。
2、建赫夫曼樹，并輸出各個字符的赫夫曼編碼
3、輸入編碼01100……，能準確翻譯成報文
4、要求有菜單
*/
#include?
#include?
#include?
#include?
#include?
#include?
using?namespace?std;
const?int?maxn=2e5+10;

///采用數組模擬鏈表的方式存節點
struct?node{
????int?wid;??//w是節點權值id是對應數組下標
????char?c;???//葉子節點為字母，其他節點為#
????char?now;??//該節點上一條路徑對應的01字符，0代表左子樹，1代表右子樹
????int?falr;??//該節點的父節點和左右子節點

????node（）{}
????node（int?iint?weightchar?chint?fatherint?lchildint?rchild）{??//初始化函數
????????id=iw=weightc=ch;
????????fa=fatherl=lchildr=rchild;
????}

????bool?operator?????????return?w>=p.w;
????}
}a[maxn];

const?char?dic[]={‘C‘‘A‘‘S‘‘T‘};
const?int?num[]={2745};
priority_queue?p;??//初始化用到的優先隊列
string?s;

int?cnt;??//總的節點數

///初始化函數
void?init（）{
????while（!p.empty（））?p.pop（）;??//優先隊列清空
????for（int?i=0;i<4;i++）{????//根節點入隊
????????a[i]=node（inum[i]dic[i]000）;
????????p.push（a[i]）;
????}
????cnt=4;??//此時隊列的節點數
????while（p.size（）>1）{??//當隊列只剩一個根節點時結束循環
????????node?u=p.top（）;?p.pop（）;
????????node?v=p.top（）;?p.pop（）;
????????node?nd=node（cntu.w+v.w00u.idv.id）;??//得到新的節點
????????a[u.id].fa=cnta[v.id].fa=cnt;???//更新節點數組的兩子節點節點的父親下標
????????a[u.id].now=‘0‘a[v.id].now=‘1‘nd.now=nd.c=‘#‘;???//更新路徑字符
????????a[cnt++]=nd;?//新增節點入字符數組
????????p.push（nd）;??//新增節點入隊
????}
}

///查看哈夫曼樹的結構
void?Test（）{
????for（int?i=0;i????????cout<????????cout<