函数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是叶子节点个数。####输入格式： 第一行输入一个数n，表示叶子节点的个数，接下去输入n个整数，表示每个节点的值 ####输出格式： 只要建树即可，输出已经确定了 输入样例： 4 1 2 3 4 输出样例： 1 5 0 0 2 5 0 0 3 6 0 0 4 7 0 0 3 6 1 2 6 7 3 5 10 0 4 6 110 111 10 0 。使用C语言将代码编写出来

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

#define MAX_N 1000

typedef struct {
    int weight;
    int parent;
    int left_child, right_child;
} HTNode, *HuffmanTree;

typedef char *HuffmanCode[MAX_N+1];

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

int main() {
    int n;
    int w[MAX_N];
    HuffmanTree HT;
    HuffmanCode HC;

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

    HuffmanCoding(&HT, HC, w, n);

    return 0;
}

void SelectTwoMin(int upbound, HuffmanTree HT, int *s1, int *s2) {
    int min1, min2;
    min1 = min2 = 0x7fffffff;
    *s1 = *s2 = 0;
    for (int i = 1; i <= upbound; i++) {
        if (HT[i].parent == 0) {
            if (HT[i].weight < min1) {
                min2 = min1;
                min1 = HT[i].weight;
                *s2 = *s1;
                *s1 = i;
            } else if (HT[i].weight < min2) {
                min2 = HT[i].weight;
                *s2 = i;
            }
        }
    }
    if (*s1 > *s2) {
        int tmp = *s1;
        *s1 = *s2;
        *s2 = tmp;
    }
}

void HuffmanCoding(HuffmanTree *HT, HuffmanCode HC, int *w, int n) {
    if (n <= 1) {
        return;
    }

    int m = n * 2 - 1;
    *HT = (HuffmanTree) malloc(sizeof(HTNode) * (m + 1));
    for (int i = 1; i <= m; i++) {
        (*HT)[i].weight = 0;
        (*HT)[i].parent = 0;
        (*HT)[i].left_child = 0;
        (*HT)[i].right_child = 0;
    }

    for (int i = 1; i <= n; i++) {
        (*HT)[i].weight = w[i-1];
    }

    for (int i = n+1; i <= m; i++) {
        int s1, s2;
        SelectTwoMin(i-1, *HT, &s1, &s2);
        (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
        (*HT)[i].left_child = s1;
        (*HT)[i].right_child = s2;
        (*HT)[s1].parent = i;
        (*HT)[s2].parent = i;
    }

    char *code = (char *) malloc(sizeof(char) * (n + 1));
    code[n] = '\0';

    for (int i = 1; i <= n; i++) {
        int start = n;
        int cur = i;
        while ((*HT)[cur].parent != 0) {
            if ((*HT)[(*HT)[cur].parent].left_child == cur) {
                code[--start] = '0';
            } else {
                code[--start] = '1';
            }
            cur = (*HT)[cur].parent;
        }
        HC[i] = (char *) malloc(sizeof(char) * (n - start));
        strcpy(HC[i], &code[start]);
    }

    free(code);
}