/*
  Name: 赫夫曼編碼 
  Copyright: 始發(fā)于goal00001111的專(zhuān)欄；允許自由轉(zhuǎn)載，但必須注明作者和出處
  Author: goal00001111
  Date: 16-12-08 21:16
  Description: 赫夫曼編碼
  本程序?qū)崿F(xiàn)了使用赫夫曼編碼壓縮數(shù)據(jù)；輸入一串字符串sourceCode——為方便理解，暫時(shí)要求字符串只包含大寫(xiě)字母和空格，如果你愿意，
  很容易就可以推廣到所有的字符——計(jì)算出字符串中各個(gè)字母的權(quán)重，然后對(duì)其進(jìn)行赫夫曼編碼，輸出赫夫曼樹(shù)。
  將赫夫曼樹(shù)的葉子結(jié)點(diǎn)存儲(chǔ)到有序二叉樹(shù)中，輸出原字符串經(jīng)壓縮后得到的用'0'和'1'表示的新字符串destCode；
  然后利用赫夫曼樹(shù)將字符串destCode進(jìn)行譯碼，得到目標(biāo)字符串objCode，比較objCode和sourceCode，發(fā)現(xiàn)完全一樣！
  編碼譯碼成功！
  最后銷(xiāo)毀有序二叉樹(shù)和赫夫曼樹(shù)。
  本程序的一個(gè)亮點(diǎn)是使用了二叉堆來(lái)存儲(chǔ)需要合并的赫夫曼樹(shù)結(jié)點(diǎn)，這樣在求最小值時(shí)時(shí)間復(fù)雜度可以降低到log(n)。
  另外關(guān)于赫夫曼編碼的詳細(xì)內(nèi)容請(qǐng)參考維基百科： http://zh.wikipedia.org/wiki/%E5%93%88%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81
  和數(shù)據(jù)結(jié)構(gòu)自考網(wǎng)：http://student.zjzk.cn/course_ware/data_structure/web/shu/shu6.6.2.1.htm
  關(guān)于二叉堆的詳細(xì)內(nèi)容請(qǐng)參考百度百科：http://baike.baidu.com/view/668854.html 
*/
#include<iostream>

using namespace std;

typedef char ElemType;

typedef struct sNode
{
    double  weight;
    ElemType data;  
} *Source;

typedef struct hNode
{
    double  weight;
    ElemType data; 
    int     lc, rc;
} *HuffmanTree;

typedef struct cNode
{
    ElemType data;
    string  str;
    struct cNode *lc, *rc;
} *Btree;

HuffmanTree CreateHuffmanTree(const Source w, int n);//創(chuàng)建一棵赫夫曼樹(shù) 
void BuildHeap(HuffmanTree t, int n); //構(gòu)造一個(gè)二叉堆；小頂堆
void PercDown(HuffmanTree t, int pos, int n);//構(gòu)造二叉堆的功能子函數(shù) 
void DeleteMin(HuffmanTree t, int len); //刪除二叉堆的根，并通過(guò)上移使得新得到的序列仍為二叉堆
void InsertHfNode(HuffmanTree t, int len, struct hNode x); //把x插入到原長(zhǎng)度為len的二叉堆
void Preorder(HuffmanTree t, int p);  //先序遍歷赫夫曼樹(shù) 
void Postorder(Btree & t, HuffmanTree a, int n); //后序遍歷赫夫曼樹(shù)，并記錄葉子結(jié)點(diǎn)編碼
bool InsertBtNode(Btree & t, Btree s);  //向一個(gè)二叉排序樹(shù)t中插入一個(gè)結(jié)點(diǎn)s
void Inorder(Btree t);     //中序遍歷二叉排序樹(shù)
Btree Search(Btree p, ElemType data); //查找值為data的結(jié)點(diǎn)的遞歸算法
string Coding(string s, Btree t); //利用記錄了葉子結(jié)點(diǎn)編碼的排序二叉樹(shù)，對(duì)sourceCode進(jìn)行編碼，返回編碼后的字符串 
string Decode(string s, HuffmanTree hT); //利用赫夫曼樹(shù)對(duì)destCode進(jìn)行解碼 
void DestroyBTree(Btree & t); //銷(xiāo)毀一棵二叉排序樹(shù)
void DestroyHfmanTree(HuffmanTree & t, int n);  //銷(xiāo)毀一棵赫夫曼樹(shù)

int main()
{
    string sourceCode;
    getline(cin, sourceCode, '\n');
    
    int n = sourceCode.size();
    const int MAX = 27; //原碼由26個(gè)大寫(xiě)字母加空格組成 
    Source w = new struct sNode[MAX];
    
    //讀取各個(gè)字母并初始化權(quán)重 
    w[MAX-1].data = ' ';
    w[MAX-1].weight = 0;
    for (int i=MAX-2; i>=0; i--) 
    {
        w[i].data = 'A' + i;
        w[i].weight = 0;
    }
    
    //讀取各個(gè)字母的權(quán)重
    for (int i=0; i<n; i++)  
    {
        if (sourceCode[i] == ' ')
            w[26].weight++;
        else
            w[sourceCode[i]-'A'].weight++;
    }
    
    //獲取出現(xiàn)了的大寫(xiě)字母和空格
    n = 0;
    for (int i=0; i<MAX; i++)  
    {
        if (w[i].weight > 0)
            w[n++] = w[i];
    } 
    
//    //直接輸入原碼和權(quán)重 
//    for (int i=0; i<n; i++)
//    {
//        cin >> w[i].weight >> w[i].data;
//    }
    
    for (int i=0; i<n; i++)
    {
        cout << w[i].weight << "  " << w[i].data << endl;
    }
    
    HuffmanTree hT = CreateHuffmanTree(w, n);//構(gòu)造赫夫曼樹(shù) 
    
//    for (int i=1; i<2*n; i++)
//        cout << hT[i].weight << "   ";
//    cout << endl;
    
    //先序遍歷赫夫曼樹(shù)，并輸出結(jié)點(diǎn)權(quán)重和葉子結(jié)點(diǎn)的data 
    Preorder(hT, 1);
    cout << endl;
    
    //后序遍歷赫夫曼樹(shù)，并記錄葉子結(jié)點(diǎn)編碼 
    Btree bT = NULL;
    Postorder(bT, hT, n);
    
    //中序遍歷記錄了葉子結(jié)點(diǎn)編碼的排序二叉樹(shù) 
    Inorder(bT);
    
    //利用記錄了葉子結(jié)點(diǎn)編碼的排序二叉樹(shù)，對(duì)sourceCode進(jìn)行編碼
    string destCode = Coding(sourceCode, bT);
    cout << destCode << endl; 
    
    //利用赫夫曼樹(shù)對(duì)destCode進(jìn)行解碼 
    string objCode = Decode(destCode, hT);
    cout << objCode << endl; 
    
    DestroyBTree(bT); //銷(xiāo)毀二叉排序樹(shù)
    //Inorder(bT);  //再輸出試試看 
    
    DestroyHfmanTree(hT, n); //銷(xiāo)毀赫夫曼樹(shù)
    //Preorder(hT, 1); //再輸出試試看 
    
    system("pause");
    return 0;
}

//創(chuàng)建一棵赫夫曼樹(shù) 
HuffmanTree CreateHuffmanTree(const Source w, int n)
{
    HuffmanTree hT = new struct hNode[2*n]; //第一個(gè)結(jié)點(diǎn)不用 
    
    for (int i=0; i<n; i++)
    {
        hT[i+1].data = w[i].data;
        hT[i+1].weight = w[i].weight;
        hT[i+1].lc = hT[i+1].rc = 0;
    }
    BuildHeap(hT, n);//構(gòu)造一個(gè)二叉堆；小頂堆
    
    struct hNode add;
    int left = n;
    int right = n;
    while (left > 1)
    {
        hT[++right] = hT[1];
        add.weight = hT[1].weight;
        add.lc = right; //存儲(chǔ)左孩子下標(biāo) 
        
        DeleteMin(hT, left--);  
         
        hT[left+1] = hT[1];
        add.weight += hT[1].weight;
        add.rc = left+1; //存儲(chǔ)右孩子下標(biāo)  
        
        DeleteMin(hT, left--);  
        
        InsertHfNode(hT, ++left, add);
        
        //for (int i=1; i<=right; i++)
//            cout << hT[i].weight << "   ";
//        cout << endl;
//        system("pause");
    }
    
    return hT;
}

//構(gòu)造一個(gè)二叉堆；小頂堆 
void BuildHeap(HuffmanTree t, int len)
{
    for (int i=len/2; i>0; i--)
    {
        PercDown(t, i, len);
    }
}

//構(gòu)造二叉堆的功能子函數(shù) 
void PercDown(HuffmanTree t, int pos, int len)
{
    int child;
    struct hNode min = t[pos];
    
    while (pos * 2 <= len)
    {
        child = pos * 2;
        if (child != len && t[child+1].weight < t[child].weight)
            child++;
            
        if (min.weight > t[child].weight)
            t[pos] = t[child];
        else
            break;
        
        pos = child;
    }
    t[pos] = min;
}

//刪除二叉堆的根，并通過(guò)上移使得新得到的序列仍為二叉堆
void DeleteMin(HuffmanTree t, int len)
{
    struct hNode last = t[len--];//二叉堆的最后一個(gè)元素
    int child, pos = 1;
    
    while (pos * 2 <= len) //把二叉堆的某些元素往前移，使得新得到的序列仍為二叉堆
    {
        child = pos * 2;
        if (child != len && t[child+1].weight < t[child].weight) //若i有右兒子，且右兒子小于左兒子，c指向右兒子
            child++;
            
        if (last.weight > t[child].weight) //若i的小兒子小于二叉堆的最后一個(gè)元素，把其移到i的位置
            t[pos] = t[child];
        else
            break;
        
        pos = child;
    }
    t[pos] = last; //把二叉堆的最后一個(gè)元素放到適當(dāng)?shù)目瘴唬藭r(shí)得到的序列仍為二叉堆
}

//把x插入到原長(zhǎng)度為len的二叉堆
void InsertHfNode(HuffmanTree t, int len, struct hNode x)
{
      int i;
      for (i=len; i/2>0 && t[i/2].weight>x.weight; i/=2)
            t[i] = t[i/2];
      t[i] = x;
}

//后序遍歷赫夫曼樹(shù)，并記錄葉子結(jié)點(diǎn)編碼 
void Postorder(Btree & t, HuffmanTree a, int n)
{
    int *stack = new int[n];
    int *tag = new int[n];
    char *buf = new char[n];
    bool flag = true;
    int top = -1;
    int p = 1;
    while (a[p].lc > 0 || top >= 0) 
    {
        while (a[p].lc > 0) //先一直尋找左孩子
        {
            flag = true;   //此時(shí)p指向的是新葉子（未輸出過(guò)的葉子）
            stack[++top] = p;  //結(jié)點(diǎn)入棧
            p = a[p].lc;
            tag[top] = 0; //表示右孩子沒(méi)有被訪問(wèn)
            buf[top] = '0'; //左孩子標(biāo)記'0' 
        }
        
        if (flag) //如果p指向的是新葉子 
        {
            //cout << a[p].data << " : "; //輸出葉子結(jié)點(diǎn) 
//            for (int i=0; i<=top; i++)
//                cout << buf[i];
//            cout << endl;
            
            Btree s = new struct cNode;
            s->data = a[p].data;
            for (int i=0; i<=top; i++)
                s->str += buf[i];
            s->lc = s->rc = NULL;
            if (!(InsertBtNode(t, s))) //插入一個(gè)結(jié)點(diǎn)s
                delete s;
        }
        
        if (top >= 0) //所有左孩子處理完畢后
        {
            if (tag[top] == 0) //如果右孩子沒(méi)有被訪問(wèn)
            {
                flag = true;  //此時(shí)p指向的是新葉子（未輸出過(guò)的葉子）
                p = stack[top]; //讀取棧頂元素，但不退棧 ，因?yàn)橐容敵銎溆液⒆咏Y(jié)點(diǎn)
                p = a[p].rc;    
                tag[top] = 1; //表示右孩子被訪問(wèn)，下次直接退棧 
                buf[top] = '1'; //右孩子標(biāo)記'1' 
            }
            else   //棧頂元素出棧
            {
                flag = false; //此時(shí)p指向的是舊葉子（已輸出過(guò)的葉子），不再輸出 
                top--;
            }
        }
    }
}

//先序遍歷赫夫曼樹(shù) 
void Preorder(HuffmanTree t, int p)
{
    if (t == NULL)
        return;
        
    if (t[p].lc > 0)
    {
        cout << t[p].weight << endl;
        Preorder(t, t[p].lc); //遍歷左子樹(shù)
        Preorder(t, t[p].rc); //遍歷右子樹(shù)
    }
    else
        cout << t[p].weight << "  " << t[p].data << endl;
}

//向一個(gè)二叉排序樹(shù)t中插入一個(gè)結(jié)點(diǎn)s
bool InsertBtNode(Btree & t, Btree s)  
{
    if (t == NULL)
    {
        t = s;
        return true;
    }
    else if (t->data > s->data) //把s所指結(jié)點(diǎn)插入到左子樹(shù)中
        return InsertBtNode(t->lc, s);
    else if (t->data < s->data) //把s所指結(jié)點(diǎn)插入到右子樹(shù)中
        return InsertBtNode(t->rc, s);
    else //若s->data等于b的根結(jié)點(diǎn)的數(shù)據(jù)域之值，則什么也不做
        return false;
}

//中序遍歷二叉排序樹(shù)
void Inorder(Btree t)
{
    if (t)
    {
        Inorder(t->lc); //遍歷左子樹(shù)
           cout << t->data << " : " << t->str << endl; //輸出該結(jié)點(diǎn)
           Inorder(t->rc); //遍歷右子樹(shù)
    }
}

//查找值為data的結(jié)點(diǎn)的遞歸算法
Btree Search(Btree p, ElemType data)
{
    if (p == NULL || p->data == data) //空樹(shù)或找到結(jié)點(diǎn) 
        return p;
    
    if (p->data > data) 
        return Search(p->lc, data); //在左孩子中尋找
    else 
        return Search(p->rc, data); //在右孩子中尋找
}

//利用記錄了葉子結(jié)點(diǎn)編碼的排序二叉樹(shù)，對(duì)sourceCode進(jìn)行編碼，返回編碼后的字符串 
string Coding(string s, Btree t)
{
    Btree p = NULL;
    string dest;
    for (int i=0; i<s.size(); i++)
    {
        p = Search(t, s[i]);
        if (p != NULL)
        {
            dest += p->str;  
            //dest += ' ';
        } 
    }
    return dest;
}

//利用赫夫曼樹(shù)對(duì)destCode進(jìn)行解碼 
string Decode(string s, HuffmanTree hT)
{
    string dest;
    int p = 1;
    int i = 0;
    while (i < s.size())
    {
        while (hT[p].lc > 0)//非葉子結(jié)點(diǎn) 
        {
            if (s[i++] == '0')
                p = hT[p].lc; //向左結(jié)點(diǎn)前進(jìn) 
            else
                p = hT[p].rc; //向右結(jié)點(diǎn)前進(jìn) 
        }
        dest += hT[p].data; //存儲(chǔ)葉子結(jié)點(diǎn) 
        p = 1;
    }   
    return dest;  
}

//銷(xiāo)毀一棵二叉排序樹(shù)
void DestroyBTree(Btree & t)
{
    if (t != NULL)
    {
        DestroyBTree(t->lc);
        DestroyBTree(t->rc);
        delete t;
        t = NULL;
    }
}

//銷(xiāo)毀一棵赫夫曼樹(shù) 
void DestroyHfmanTree(HuffmanTree & t, int n)
{
    for (int i=n-1; i>=0; i--)
    {
        delete &t[i];
    } 
    t = NULL;
}