7_30 英语流利说的霍夫曼编码题

• 基本思路

（1）unordered_map统计每个字符出现的个数
（2）将所有的节点放到一个优先队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。
（3）如此循环，直到队列中只剩一个节点（树根）。

//定义哈夫曼树的节点
struct Node{
    char key; //代表的值
    int freq; //出现的频率
    Node* left;
    Node* right; //既然是树中的节点，左右子节点
    Node(int k='\0',int f=0):key(k),freq(f),left(NULL),right(NULL){} //默认构造函数
};
//用到优先队列的话，根据freq从小到大排序，但是pq中定义的应该是相反的，a.freq>b.freq
struct cmp{
    bool operator()(const Node *a,const Node *b){
        return a->freq > b->freq;
    }
};
Node* huffman(unordered_map<char>& mymap){
    //总共多少个点先统计
    int n=mymap.size();
    //先来构建顶点
    priority_queue<node>,cmp> pq; //一个优先队列
    for(auto it=mymap.begin();it!=mymap.end();it++){
        //生成节点，插入优先队列中
        Node* cur=new Node(); //生成节点
        cur->freq=it->second;
        cur->key=it->first;
        pq.push(cur); //进队列
    }
    //直到最后剩下的一个就是root
    while(pq.size()>1){
        auto sub1=pq.top();
        pq.pop();
        auto sub2=pq.top();
        pq.pop();
        //取两个进行合并后放回去
        Node* cur=new Node();
        cur->freq=sub1->freq+sub2->freq; //当前节点的freq为两者之和
        cur->left=sub1;
        cur->right=sub2; //两个节点分别作为当前的左右子节点进行相连
        pq.push(cur); //将当前的节点放回去
    }
    //最终剩下的就是root
    return pq.top();
}
//考虑LDR进行遍历，打印叶子节点的信息
void print_leaf(Node* root,string s){
    if(!root){ //遍历到空
        return;
    }
    if(!root->left && !root->right){ //如果是叶子节点了，打印信息
        cout<<"current leaf is: "<key<<"-----";
        //输出编码值
        cout<<"the code is: "<<<endl>left,s+"0"); //左边标记0
    print_leaf(root->right,s+"1"); //右边标记1
}
int main(){
    //string s;
    //cin>>s; //输入的字符串
    unordered_map<char> mymap; //统计每个字符出现的个数
    //for(auto ch:s){
     //   mymap[ch]++;
    //}
    mymap['a']=45;
    mymap['b']=13;
    mymap['c']=12;
    mymap['d']=16;
    mymap['e']=9;
    mymap['f']=5;
    //进行霍夫曼编码
    Node* root=huffman(mymap);
    //左0右1进行打印编码，每一个输入的所需都应该在叶子节点上，考虑LDR输出
    string res="";
    print_leaf(root,res);
    system("pause");
    return 0;
}

• 运行结果如下所示：

而题中如果要求长度，可以考虑记录每个节点的标记是多少，最终来累加长度