#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define  n  5
#define  m  n*2-1

typedef struct Haffman
{
    int weight;
    int lchild, rchild, parent;
}Haffmantree[n];

typedef struct Code
{
    char ch;
    char bits[n];
}Haffmancode[m];

void Create_haffmantree(Haffmantree t);
void Haffman_code(Haffmantree t, Haffmancode h);

int main()
{
    Haffmantree t;
    Haffmancode h;

    Create_haffmantree(t);

    Haffman_code(t, h);

    putchar(10);
    return 0;
}
//构造哈夫曼二叉树
void Create_haffmantree(Haffmantree t)
{
    int i, j, p1, p2;
    int min1 = -1, min2 = -1;

    for(i = 0; i < m; i ++)
    {
        t[i].weight = 0;
        t[i].lchild = t[i].rchild = t[i].parent = 0;
    }

    for(i = 0; i < n; i ++)
    {
        printf("Please input the No.%d weight: ", i + 1);
        scanf("%d", &t[i].weight);
    }

    putchar(getchar());   //解除换行占位的影响

    for(j = 0; j < n - 1; j ++)
    {
        for(i = 0; i < n + j; i ++)
        {
            if(t[i].parent == 0)
            {
                if(t[i].weight < min1 || min1 == -1)
                {
                    if(min1 != -1)
                    {
                        min2 = min1;
                        p2 = p1;
                    }
                    min1 = t[i].weight;
                    p1 = i;
                }
                else if(t[i].weight < min2 || min2 == -1)
                {
                    min2 = t[i].weight;
                    p2 = i;
                }
            }
        }
        t[p1].parent = t[p2].parent = n + j;
        t[n + j].lchild = p1;
        t[n + j].rchild = p2;
        t[n + j].weight = t[p1].weight + t[p2].weight;
    }
}
//构造哈夫曼编码
void Haffman_code(Haffmantree t, Haffmancode h)
{
    int i;
    int p, c;
    int start;
    char cd[n + 1];

    cd[n] = '\0';
    printf("Please int the character:");
    for(i = 0; i < n; i ++)
    {
        start = n;
        h[i].ch = getchar();
        c = i;
        p = t[i].parent;
        while(p != 0)
        {
            -- start;
            if(t[p].lchild == c)
                cd[start] = '0';
            else
                cd[start] = '1';
            c = p;
            p = t[c].parent;
        }
        strcpy(h[i].bits, &cd[start]);
    }

    putchar(10);
    for(i = 0; i < n; i ++)
        printf("No.%d character %c's coding is %s \n", i + 1, h[i].ch, h[i].bits);
}