Huffman编码STL版     CSDN Blog推出文章指数概念，文章指数是对Blog文章综合评分后推算出的，综合评分项分别是该文章的点击量，回复次数，被网摘收录数量，文章长度和文章类型；满分100，每月更新一次。
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

struct TreeNode
{
    double Weight;//权值
    char flag;//代表符号如a,b,c，如果为非叶子节点flag=='-'
    struct TreeNode* left; //左子树
    struct TreeNode* right;//右子树
};

///全局变量///
vector<char> g_Path; //路径栈
vector<TreeNode> g_Heap; //用于构造树的堆
/////////////


bool UDGreater(TreeNode &a,TreeNode &b)
{ //为TreeNode定义一种比较大小的函数，以便后面构造小根堆
    if(a.Weight>b.Weight){
        return true;
    }
    else{
        return false;
    }
}

void printPath()
{//打印从根节点到当前叶子节点的路径，即huffman编码
    vector<char>::iterator it;
    for(it=g_Path.begin();it!=g_Path.end();it++){
        cout<<*it;
    }
}

void CreateHuffmanTree()
{//构造Huffman树
    TreeNode *left,*right,parent;
    make_heap(g_Heap.begin(),g_Heap.end(),UDGreater);//构造小根堆
    while(g_Heap.size()>1){
        left=new TreeNode();
        right=new TreeNode();
        pop_heap(g_Heap.begin(),g_Heap.end(),UDGreater);
        *left=g_Heap.back(); //取出最小的节点
        g_Heap.pop_back();

        pop_heap(g_Heap.begin(),g_Heap.end(),UDGreater);
        *right=g_Heap.back(); //取出第二小的节点
        g_Heap.pop_back();
        
        parent.left=left; //根据这两个节点生成一个新的节点
        parent.right=right;
        parent.Weight=left->Weight+right->Weight;
        parent.flag='-';

        g_Heap.push_back(parent);
        push_heap(g_Heap.begin(),g_Heap.end(),UDGreater);//在堆中添加进去新生成的节点 
        
    }
}

void TravelHuffmanTree(TreeNode parent)
{//遍历huffman树，在此过程中输出叶节点的编码
    if(parent.left==NULL && parent.right==NULL){//如果是叶子节点
        cout<<parent.flag<<":";
        printPath(); //打印路径即huffman编码
        cout<<endl;
        
    }
    else{
        g_Path.push_back('0'); 
        TravelHuffmanTree(*parent.left); //遍历左子树
        g_Path.pop_back();
        g_Path.push_back('1');
        TravelHuffmanTree(*parent.right); //遍历右子树
        g_Path.pop_back();
    }
}

int main(){
    int count=0;
    TreeNode temp;
    cout<<"请输入字符的个数"<<endl;
    cin>>count;
    cout<<"请输入要编码的字符和它的权值，用空格隔开，如：a 12.5"<<endl;
    while(count--){
        cin>>temp.flag>>temp.Weight;
        temp.left=NULL;
        temp.right=NULL;
        g_Heap.push_back(temp);
    }
    CreateHuffmanTree();  //创建huffman树
    TreeNode root=g_Heap.front();
    TravelHuffmanTree(root); //遍历huffman树
}