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樹
}