#include <stdio.h>
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE 59
#define MAXBIT 10

//哈夫曼树结构
typedef struct
{
    int data;   //结点值
    int Weight; //权重
    int Flag;   //标识是否待构节点，是的话用0表示，否则用1表示
    int Parent; //父结点
    int LChild; //左结点
    int RChild; //右结点
}hnodetype;

typedef struct
{
    int Bit[MAXBIT];
    int Start;
}hcodetype;

/****--------------------------------------------*****/
//函数名： InitHaffman(hnodetype HuffNode[], hcodetypde HuffNode[], int n)
//参数：  (传入) hnodetype HuffNode[] 哈夫曼树结点
//        (传入) hcodetype HuffCode[] 哈夫曼编码树结点
//        (传入) int n 结点数量
//功能:   哈夫曼结点初始化
/****--------------------------------------------*****/

void InitHaffman(hnodetype HuffNode[], hcodetype HuffCode[], int n)
{
    int i;
    //把生成的结点初始化,把指向父亲的指针,左孩子,右孩子的指针都先置空
     for(i = 0; i < 2*n-1; i++) {
        HuffNode[i].Weight = 0;
        HuffNode[i].Parent = 0;
        HuffNode[i].Flag = 0;
        HuffNode[i].LChild = -1;
        HuffNode[i].RChild = -1;
     }
     for(i = 0; i < n; i++) {
        getchar();
        printf("输入第%d个叶结点值:", i+1);
        scanf("%c", &HuffNode[i].data);
        printf("输入对应结点权值:");
        scanf("%d", &HuffNode[i].Weight);
     }
}

/****--------------------------------------------*****/
//函数名: OutputHaffman(hnodetype HuffNode[], hcodetype HuffNode[], int n)
//参数名: (传入)hnodetype HuffNode[] 哈夫曼树结点
//        (传入)hcodetype HuffNode[] 哈夫曼树编码树结点
//        (传入)int n 结点数量
//功能:   输出哈夫曼编码
/****--------------------------------------------*****/

void OutputHaffman(hnodetype HuffNode[], hcodetype HuffCode[], int n)
{
    int i, j;
    printf("%d个叶结点对应编码为:\n", n);
    for(i = 0; i < n; i++) {
        printf("%c- - - -",HuffNode[i].data);
        for(j = HuffCode[i].Start+1; j < n; j++) {
            printf("%d", HuffCode[i].Bit[j]);
        }
        printf("\n");
    }
}

/****-------------------------------------------*****/
//函数名: Haffman(hnodetype HuffNode[], hcodetypeCode[], int n)
//参数:   (传入)hnodetype HuffNode[]  哈夫曼树结点
//        (传入)hcodetype HuffCode[] 哈夫曼树编码树结点
//        (传入)int n 结点数量
//功能:   构造哈夫曼树,根据树生成哈夫曼编码
/****-------------------------------------------*****/
void Haffman(hnodetype HuffNode[], hcodetype HuffCode[], int n)
{
    int i, j, m1, m2, x1, x2, c, p;
    hcodetype cd;

    for(i = 0; i < n-1; i++) { //构造哈夫曼树
       //根据哈夫曼树的构造过程,始终选择最小权值的两个结点构成一个二叉树
       m1 = m2 = MAXVALUE;
       //x1 和 x2位最小权重的两个结点位置
       x1 = x2 = 0;
       //循环从flag为0的节点中找到一个,供下面取最小值
       for(j = 0; j < n+i; j++) {
        if(HuffNode[j].Weight < m1 && HuffNode[j].Flag == 0) {
            m2 = m1;
            x2 = x1;
            m1 = HuffNode[j].Weight;
            x1 = j;  //记下x2的地址
        }
        else if(HuffNode[j].Weight < m2 && HuffNode[j].Flag == 0)
        {
            m2 = HuffNode[j].Weight;
            x2 = j;
        }
       }//for
        //把找到的两个节点按照哈夫曼树的规则构建成一个二叉树,x1为左孩子,x2为右孩子
        HuffNode[x1].Parent = n+i;
        HuffNode[x2].Parent = n+i;
        HuffNode[x1].Flag = 1;  //将x1的下标置1
        HuffNode[x2].Flag = 1;  //将x2的下标置1
        HuffNode[n+i].Weight = HuffNode[x1].Weight + HuffNode[x2].Weight;
        HuffNode[n+i].LChild = x1;
        HuffNode[n+i].RChild = x2;
    }//for
    for(i = 0; i < n; i++) {//根据哈夫曼树生成哈夫曼编码
        cd.Start = n-1;
        c = i;
        p = HuffNode[c].Parent;

        while(p != 0) {//当父结点不为根结点的时候,逆序往上找
            //如果当前是左孩子,则编码为0
            if(HuffNode[p].LChild == c) cd.Bit[cd.Start] = 0;
            //当前左孩子的编码为1
            else cd.Bit[cd.Start] = 1;
            cd.Start--;
            c = p;
            p = HuffNode[c].Parent;
        }

        for(j = cd.Start+1; j < n; j++) {
            HuffCode[i].Bit[j] = cd.Bit[j];
            HuffCode[i].Start = cd.Start;
        }
    }//for
}//end of Haffman

int main()
{
    hnodetype HuffNode[MAXNODE];
    hcodetype HuffCode[MAXLEAF];
    int n;
    printf("输入叶结点个数n:\n");
    scanf("%d", &n);

    InitHaffman(HuffNode, HuffCode, n);
    Haffman(HuffNode, HuffCode, n);
    OutputHaffman(HuffNode, HuffCode, n);
    return 0;
}