//构建哈夫曼树

#include<iostream>
#include<string.h>

using namespace std;
#define N 5
#define M 2*N-1
typedef struct{
    int parent;
    int lchild;
    int rchild;
    int weight;
}hfmnode;
typedef struct{
    char code[N];
    int start;//起始位置
}Hcode;

void select(hfmnode hfm[],int &t1,int &t2,int n){
    hfm[0].weight=100;
    for(int i=1;i<=n;i++){
        if(hfm[i].parent==0)
        {
            if(hfm[i].weight<hfm[t1].weight)
            t1=i;
        }
    }
    for(int i=1;i<=n;i++){
        if(hfm[i].parent==0&&i!=t1)
        {
            if(hfm[i].weight<hfm[t2].weight)
            t2=i;
        }
    }
}

void create_hfm(hfmnode hfm[],int w[],int n){
    for(int i=1;i<=n;i++){
        hfm[i]={0,0,0,w[i-1]};
    }//初始化叶子结点
    int m=2*n-1;
    for(int i=n+1;i<=m;i++){
        hfm[i]={0,0,0,0};
    }
    for(int i=n+1;i<=m;i++){
        int n1=0,n2=0;
        int &t1=n1,&t2=n2;
        select(hfm,t1,t2,i-1);
        //select函数的功能是从前n个结点中选择权值最小的两个根结点（parent=0）
        //并将这两个节点的下标赋予t1和t2
        hfm[i].weight=hfm[t1].weight+hfm[t2].weight;
        hfm[i].lchild=t1;
        hfm[i].rchild=t2;
        hfm[t1].parent=i;
        hfm[t2].parent=i;
    }
}

void code_hfm(hfmnode hfm[],Hcode hfmcode[],int n){
    char cd[n];
    for(int i=1;i<=n;i++){
        int start=n;
        int child=i,parent=hfm[i].parent;
        while(parent!=0){
            if(hfm[parent].lchild==child){
                cd[start--]='1';
            }
            else cd[start--]='0';
            child=parent;
            parent=hfm[child].parent;
        }
        hfmcode[i].start=start+1;
        for(int j=start+1;j<=n;j++){
            hfmcode[i].code[j]=cd[j];
        }
    }
}//10.13更新

// 旧版哈夫曼编码，非常不好记
// char* hfmcodes[N+1];//一个数组，保存的是N个字符数组头指针
// //对应的就是N个叶子结点的哈夫曼编码
// void hfm_code(hfmnode hfm[],char * hfmcodes[],int n){
//     char * cd;
//     cd = (char *)malloc(sizeof(char)*(n+1));
//     //char cd[n];
//     cd[n]='\0';
//     for(int i=1;i<=n;i++){//一共n个叶子结点
//         int top=n-1;//当前可插入位置
//         int child=i,parent=hfm[child].parent;
//         while(parent!=0)
//         {
//           if(child==hfm[parent].lchild) cd[top--]='1';
//         else cd[top--]='0';
//         child=parent;
//         parent=hfm[child].parent;
//         }
//         hfmcodes[i]=(char *)malloc(sizeof(char)*(n-top));
//         strcpy(hfmcodes[i],&cd[top+1]);
//         //cd是一个指针，我们要从cd的头开始
//         //这里strcpy函数注意一下
//     }
// }

int main(){
    int w[]={5,7,3,2,8};
    hfmnode hfm[M+1];//下标从1开始
    Hcode hfmcode[N];
    create_hfm(hfm,w,5);
    code_hfm(hfm,hfmcode,5);
    for(int i=1;i<=5;i++){
        for(int j=hfmcode[i].start;j<=5;j++){
            cout<<hfmcode[i].code[j];
        }
        cout<<endl;
    }
}