#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define OK 1
#define ERROR 0
#define OVERFLOW 0
typedef struct
{
     int weight;
     int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;

void Select(HuffmanTree HT,int n, int &s1, int &s2)
{
    //在HT[1...n]选择parent为0且weight最小的两个节点,分别赋给s1,s2
    //s1最小，s2次小
    int min=0,mun=0;
    HT[0].weight = 30000;
    for(int i=1;i<=n;i++)
    {
        if(HT[i].parent==0)
        {
            if(HT[i].weight<HT[min].weight)  
            {
                mun = min;
                min=i;
            }
            else if    (HT[i].weight<HT[mun].weight)
                mun=i;
        }        
    }
    s1=min;
    s2= mun;
    
}

int HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
    int i,m,s1,s2;
    HuffmanTree p;
    if(n<=1)
        return 0;
    m=2*n-1;
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
    for(p=HT+1,i=1;i<=n;++i,++p)
    {
        
        p->weight=w[i-1];
        p->parent=0;
        p->lchild=0;
        p->rchild=0;
    }
    for(;i<=m;++i,++p)
    {
        p->weight=0;
        p->parent=0;
        p->lchild=0;
        p->rchild=0;
    }
    for(i=n+1;i<=m;++i)
    {
        Select(HT,i-1,s1,s2);
        HT[s1].parent=i;
        HT[s2].parent=i;
        HT[i].lchild=s1;
        HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
    }

    HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
    char* cd;
    cd=(char*)malloc(n*sizeof(char));
    cd[n-1]='\0';
    for( i=1;i<=n;++i)
    {
        int start=n-1;
        int c,f;
        for( c=i, f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
            if(HT[f].lchild==c)
                cd[--start]='0';
            else
                cd[--start]='1';
            HC[i]=(char*)malloc((n-start)*sizeof(char));
            strcpy(HC[i],&cd[start]);
            puts(HC[i]);
    }
    free(cd);    
    return OK;
}

void main()
{
    HuffmanTree HT;
    HuffmanCode HC;
    int n=3;        
    int w[3];
    cout<<"please input the weight for each tree by order:";
    for(int i=0;i<3;i++)
    {
        cin>>w[i];
    }
    HuffmanCoding( HT, HC, w, 3);
}