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

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

????node（）{}
????node（int?iint?weightchar?chint?fatherint?lchildint?rchild）{??//初始化函數(shù)
????????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;??//初始化用到的優(yōu)先隊列
string?s;

int?cnt;??//總的節(jié)點數(shù)

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

///查看哈夫曼樹的結(jié)構(gòu)
void?Test（）{
????for（int?i=0;i????????cout<????????cout<