1429: 哈夫曼树及哈夫曼编码

函数SelectTwoMin(int upbound, HuffmanTree HT, int &s1, int &s2)是从1到upbound中找出father为0的节点赋给s1,s2,（为了保证答案唯一，请让s1的节点编号小于s2），

函数HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)是构造哈夫曼树以及计算哈夫曼编码。保证输入的权重值小于1000。

函数接口定义：

	



	

void SelectTwoMin(int upbound, HuffmanTree HT, int &s1, int &s2); void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n);

其中upbound编号，HT是哈夫曼树，HC是哈夫曼编码，w是权值，n是叶子节点个数。

裁判测试程序样例：

	



	

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

typedef struct {
    int weight;
    int parent;
    int lchild;
    int rchild;
} HTNode, *HuffmanTree;
typedef char ** HuffmanCode;

void SelectTwoMin(int upbound, HuffmanTree HT, int &s1, int &s2);
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n);

int main() {
    HuffmanTree ht;
    HuffmanCode hc;

    int n;
    scanf("%d", &n);
    
    int *w = (int *) malloc (n * sizeof(int));
    for(int i = 0; i < n; ++ i)
        scanf("%d", &w[i]);

    HuffmanCoding(ht, hc, w, n);
    
    for (int i = 1; i <= 2 * n - 1; ++ i) {
        printf("%d %d %d %d\n", 
        ht[i].weight, ht[i].parent, ht[i].lchild, ht[i].rchild);
    }

    for (int i = 1; i <= n; ++ i)
        printf("%s\n", hc[i]);

    free(w);
    free(ht);
    for (int i = 1; i <= n; ++ i)
        free(hc[i]);
    
    return 0;
}
/* 你的代码将被嵌在这里 */