[C/C++]Huffman Tree

Huffman Tree，中文霍夫曼樹，常用來做資料壓縮的一種技巧，使得出現機率高的字母使用較短的編碼，反之出現機率低的則使用較長的編碼，這便使編碼之後的字串的平均長度、期望值降低，從而達到無失真壓縮資料的目的。

相關的介紹請看維基百科

以下使用動態Link List實作Create Huffman Tree 以及設定樹葉節點(Leaf node)的編碼

(網路上另一版本的寫法請參閱:http://www.sharejs.com/codes/cpp/5464)

實作上的一些小細節:

Struct是可以使用建構子的，Struct與Class的差異請參閱:http://genwoxuec.blog.51cto.com/1852764/503334
在動態新增node時，要注意link list是以point去做操作的，而一連串的資料又必須先存起來，所以要動態新增二維的空間，可以想成一開始先新增(資料個數)列，”但是之後每一列必須再新增一個節點空間(每列的第一個)”。
實作作法是: 每次做前先排序過。每次都找最小的兩個權值(current_position、current_position+1)，新增一個點去儲存相加的權值，並使得這兩個最小點分別為左子、右子點，再存回陣列current_position+1的位置中。

由於已經設定好左右子點了，所以把新點存回陣列把原本的資料覆蓋掉也沒關係，下一次從current_position+1的地方繼續找兩個最小值，直到(個數-1)為止。

編碼的創立則是利用樹的走訪，先走完左邊再走右邊，同時更新子節點的編碼內容，走到樹葉則輸出結果。

#pragma warning(disable:4996)
using namespace std;
struct node
{
    node()
    {
        this->weight = 0;
        this->msg = '?';
        this->encode = "";
        this->left = this->right = NULL;
    }
    node(int weight,node* left,node* right)//insert new node
    {
        this->weight = weight;
        this->msg = '?';
        this->encode = "";
        this->left = left;
        this->right = right;
    }
    char msg;
    string encode;
    int weight;
    node *left;
    node *right;
};
bool cmp(node* n1, node* n2)
{
    return n1->weight weight;
}
void Create_HuffmanTree(int size,node** data,node*& root)
{
    int current_position = 0;
    node* min1;
    node* min2;
    while (current_position != size -1)
    {
        min1 = data[current_position];
        min2 = data[current_position+1];
        node* newnode = new node(min1->weight+min2->weight,min1,min2);
        root = newnode;
        current_position++;
        data[current_position] = newnode;
        sort(data+current_position,data+size,cmp);
    }
}
void Huffman_Encoding(node* ptr)
{
    if(ptr->left == NULL && ptr->right == NULL)
    {
        printf("%c %d %s\n",ptr->msg,ptr->weight,ptr->encode.c_str());
        return;
    }
    if(ptr->left != NULL)
    {
        ptr->left->encode = ptr->encode +"0";
        Huffman_Encoding(ptr->left);
    }
    if(ptr->right != NULL)
    {
        ptr->right->encode = ptr->encode + "1";
        Huffman_Encoding(ptr->right);
    }
}
void Inorder_traversal(node* ptr)
{
    if(ptr != NULL)
    {
        Inorder_traversal(ptr->left);
        printf("%c %d\n",ptr->msg,ptr->weight);
        Inorder_traversal(ptr->right);
    }
}
int main()
{
    freopen("in.txt","r",stdin);
    int size = 0;
    char msg;
    int frequency;
    node* root = new node;
    scanf("%d",&size);
    node** data = new node* [size];
    for(int i = 0 ; i msg,&data[i]->weight);
    }
    sort(data+0,data+size,cmp);
    /*for(int i = 0 ; i msg,data[i]->weight);
    }*/
    Create_HuffmanTree(size,data,root);
    Inorder_traversal(root);
    Huffman_Encoding(root);
    return 0;
}