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

typedef struct biTreeNode{

    int weight;
    int parent;
    int lchild;
    int rchild;
}HNODE,*Huffumantree;


int  select(Huffumantree &HT,int n,int &s1,int &s2){

    int i;
    for(i = 1; i <n; ++ i){//找到两个父节点不为0的结点编号存储在s1和s2中
        if(0 == HT[i].parent){
            if(0 == s1){
                s1 = i;
            }
            else{
                s2 = i;
                break;
            }
        }
    }
    if(HT[s1].weight > HT[s2].weight){//保证s1所对应的结点权值为两者中的较小值
        int t = s1;
        s1 = s2;
        s2 = t;
    }

    for(int j=i+1; j<n; j++){//保证s1和s2所对应的权值为所有的父节点为0的结点数据中权值对应的最小值和最大值
        if(0 == HT[j].parent){
            if(HT[j].weight < HT[s1].weight){
                s2 = s1;
                s1 = j;
            }else if(HT[j].weight < HT[s2].weight){
                s2 = j;
            }
        }
    }
        return s1,s2;

}

Huffumantree CreatHuffmantree(Huffumantree &HT,int n){
    if(n<=1)
        return 0;
    int m=2*n-1;
    int s1=0;
    int s2=0;
    HT=new HNODE[m+1];  //0号单元没用，所以动态分配m+1个空间HT[m]表示根节点
    for(int i=0;i<m+1;i++)
    {
        HT[i].parent=0;
        HT[i].lchild=0;
        HT[i].rchild=0;
        HT[i].weight=0;
       // printf("%d\n",HT[i].weight);
    }
    for(int j=1;j<=n;j++)
    {
        printf("请输入权值为：");
        scanf("%d",&HT[j].weight);
        //printf("%d\n",HT[j].weight);
    }
    for(int g=n+1;g<=m;g++){
        select(HT,g,s1,s2);
       // printf("%d\n%d\n",s1,s2);
       //HT[g].weight=HT[s1].weight+HT[s2].weight;
       HT[s1].parent=g;
        HT[s2].parent=g;//将权值较小的两个节点的双亲节点赋值为先创建的结点i
        HT[g].lchild=s1;
        HT[g].rchild=s2;
       // printf("%d\n",HT[g].lchild);
        HT[g].weight=HT[s1].weight+HT[s2].weight;
      //printf("%d\n",HT[g].weight);
    }
    return HT;
}

int main()
{
    Huffumantree HT;
    int n=0;
    printf("结点个数为：");
    scanf("%d",&n);
    CreatHuffmantree(HT, n);
    for(int i=1;i<=2*n-1;i++)
       printf("%d\n",HT[i].weight);
    return 0;
}