#include <iostream>
using namespace std;

struct HuffNode
{
    float weight;
    int parent;
    int lchild;
    int rchild;
};

//实现哈夫曼编码, 返回根节点
int Huffman(const float w[], int n, HuffNode hn[])
{
    for (int i = 2 * n - 1; i--;){
        if (i < n)
            hn[i].weight = w[i];
        else
            hn[i].weight = 0;
        hn[i].parent = -1;
        hn[i].lchild = -1;
        hn[i].rchild = -1;
    }

    for (int i = 0; i < n - 1; i++)
    {
        float m1 = 10000;
        float m2 = 10000;
        int x1 = 0; int x2 = 0;
        for (int j = 0; j < n + i; j++){
            if ((hn[j].weight < m1) && (hn[j].parent == -1))
            {
                m2 = m1;
                m1 = hn[j].weight;
                x2 = x1;
                x1 = j;
            }
            else if ((hn[j].weight < m2) && (hn[j].parent == -1))
            {
                m2 = hn[j].weight;
                x2 = j;
            }
        }
        hn[n + i].weight = hn[x1].weight + hn[x2].weight;
        hn[x1].parent = n + i;
        hn[x2].parent = n + i;
        hn[n + i].lchild = x1;
        hn[n + i].rchild = x2;
    }

    int parent = 0;
    while (hn[parent].parent != -1){
        parent = hn[parent].parent;
    }
    return parent;
}

const char* rescc(int n, const char* chTbl, HuffNode hn[], const char* code, char& ch)
{
    char cc = *code;
    if (cc == '0'){
        if (hn[n].lchild != -1){
            return rescc(hn[n].lchild, chTbl, hn, code + 1, ch);
        }
    }
    else{
        if (hn[n].rchild != -1){
            return rescc(hn[n].rchild, chTbl, hn, code + 1, ch);
        }
    }
    ch = chTbl[n];
    return code;
}

int HuffmanDecode(int n, const char* chTbl,  HuffNode hn[], const char* code, char res[])
{
    int cnt = 0;
    while (*code){
        code = rescc(n, chTbl, hn, code, res[cnt++]);
    }
    return cnt;
}

int main()
{
    const int n = 8;
    const char* str = "abcdefgh";
    const float w[] = { 0.07f, 0.19f, 0.02f, 0.06f, 0.32f, 0.03f, 0.21f, 0.10f, };
    HuffNode hn[2 * n - 1];

    char inp[120];// = "10111010100001000110011110110100";
    cin >> inp;
    char res[60] = {};
    HuffmanDecode(Huffman(w, n, hn), str, hn, inp, res);

    cout << "哈夫曼解码如下:" <<res<< endl;
    return 0;
}