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

#define MAX_INT 99999
//哈夫曼树和哈夫曼编码的存储表示
typedef struct
{
    int weight;
    int parent,lchild,rchild;
} HTNode,*HuffmanTree; // 动态分配数组存储哈夫曼树

typedef char **HuffmanCode; // 动态分配数组存储哈夫曼编码表

int min(HuffmanTree t,int i)
{
    int j,flag;
    int k=MAX_INT; // 取k为不小于可能的值
    for(j=1; j<=i; j++)
        if(t[j].weight<k&&t[j].parent==0)
            k=t[j].weight,flag=j;
    t[flag].parent=1;//保证下一次min()函数选不到它
    //printf("%d ",flag);
    return flag;
}

// s1为最小的两个值中序号小的那个
void select(HuffmanTree t,int i,int &s1,int &s2)
{
    int j;
    s1=min(t,i);
    s2=min(t,i);//不可能出现s1>s2
    //printf("s1:%d s2:%d\n",s1,s2);
    if(t[s1].weight>t[s2].weight)//其实这里完全没有必要
    {
        j=s1;
        s1=s2;
        s2=j;
    }
    //printf("s1:%d s2:%d\n",s1,s2);
}

void PrintHuffmanTree(HuffmanTree &HT,HuffmanCode &HC, int n)
{
    int i, c, cdlen;
    char *cd;
    HC=(HuffmanCode)malloc((n+1)*sizeof(char*));// 分配n个字符编码的头指针向量([0]不用)
    cd=(char*)malloc(n*sizeof(char)); // 分配求编码的工作空间
    c=2*n-1;
    cdlen=0;
    for(i=1; i<=c; ++i) HT[i].weight=0; // 遍历赫夫曼树时用作结点状态标志
    while(c)//c是树根所在点，从树根开始遍历，若是叶子则将编码放在数组HC[叶子]
    {
        if(HT[c].weight==0)   // 向左
        {
            HT[c].weight=1;
            if(HT[c].lchild==0 && HT[c].rchild==0)  // 登记叶子结点字符编码
            {
                HC[c]=(char *)malloc((cdlen+1)*sizeof(char));
                cd[cdlen]='\0';
                strcpy(HC[c],cd); // 复制编码(串)
            }
            if(HT[c].lchild!=0)//想左，给0编码；
            {
                c=HT[c].lchild;
                cd[cdlen++]='0';
            }
        }
        else if(HT[c].weight==1)   // 向右
        {
            HT[c].weight=2;
            if(HT[c].rchild!=0) //初始化是叶子节点的左右孩子为空（0），若有孩子不为空，向右编码1；
            {
                c=HT[c].rchild;
                cd[cdlen++]='1';
            }
        }
        else
        {

            //HT[c].weight=0;//从左向右退，相当于中序遍历，不会再遍历到哪里了，所以这里没有必要
            c=HT[c].parent;
            --cdlen; // 退到父结点,编码长度减1
        }
    }
    free(cd);
}

// w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
    int m,i,s1,s2;

    HuffmanTree p;

    if(n<=1)   return;
    m=2*n-1;//huffman编码字符都在二叉树的叶子上，全树的节点为叶子节点的2倍-1；
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用
    for(p=HT+1,i=1; i<=n; ++i,++p,++w)
    {
        (*p).weight=*w;
        //printf("%d\t%d\n",*w,(*p).weight);
        (*p).parent=0;
        (*p).lchild=0;
        (*p).rchild=0;
    }
    for(; i<=m; ++i,++p)  (*p).parent=0;
    // 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
    for(i=n+1; i<=m; ++i)   // 建哈夫曼树
    {
        select(HT,i-1,s1,s2);//在i之前挑选最小的和次小的
        HT[s1].parent=HT[s2].parent=i;
        HT[i].lchild=s1;
        HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
    //顺序输出哈夫曼树
    PrintHuffmanTree(HT, HC, n);
}

/*
8
5 29 7 8 14 23 3 11
*/
int main()
{
    HuffmanTree HT;
    HuffmanCode HC;
    int *w,n,i;

    printf("Number of weights:");
    scanf("%d",&n);

    w=(int*)malloc(n*sizeof(int));
    printf("Weights: \n");
    for(i=0; i<n; i++)
        scanf("%d",w+i);

    HuffmanCoding(HT,HC,w,n);
    printf("Huffman code:\n");
    for(i=1; i<=n; i++)
    {
        printf("权为%d的编码是： ",*(w+i-1));
        printf("%s\n",HC[i]);
    }

}