用c语言编写程序2. 对于给定的w={2,3,4,7,8,9}权值，试构造一棵哈夫曼树，并给出各个节点的huffman 编码及huffman数组的值。并输出结果

以下是C语言代码实现：

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

#define MAX_N 100

// 定义哈夫曼树节点
typedef struct huffman_node {
    int weight; // 权值
    char ch; // 如果是字符节点，保存字符
    struct huffman_node *left; // 左子节点
    struct huffman_node *right; // 右子节点
} HuffmanNode;

// 定义哈夫曼树节点指针类型
typedef HuffmanNode *HuffmanTree;

// 定义哈夫曼编码表
typedef struct huffman_code {
    char ch; // 字符
    char code[MAX_N]; // 编码
} HuffmanCode;

// 根据权值数组构造哈夫曼树
HuffmanTree create_huffman_tree(int *w, int n) {
    int i, j, k;
    // 申请n个哈夫曼树节点的空间
    HuffmanTree *nodes = (HuffmanTree *) malloc(sizeof(HuffmanTree) * n);
    // 初始化哈夫曼树节点
    for (i = 0; i < n; i++) {
        nodes[i] = (HuffmanTree) malloc(sizeof(HuffmanNode));
        nodes[i]->weight = w[i];
        nodes[i]->ch = '\0';
        nodes[i]->left = NULL;
        nodes[i]->right = NULL;
    }
    // 构造哈夫曼树
    for (i = 0; i < n - 1; i++) {
        // 找到权值最小的两个节点
        int min1 = 0, min2 = 1;
        if (nodes[min1]->weight > nodes[min2]->weight) {
            int tmp = min1;
            min1 = min2;
            min2 = tmp;
        }
        for (j = 2; j < n - i; j++) {
            if (nodes[j]->weight < nodes[min1]->weight) {
                min2 = min1;
                min1 = j;
            } else if (nodes[j]->weight < nodes[min2]->weight) {
                min2 = j;
            }
        }
        // 创建新节点
        HuffmanTree new_node = (HuffmanTree) malloc(sizeof(HuffmanNode));
        new_node->weight = nodes[min1]->weight + nodes[min2]->weight;
        new_node->ch = '\0';
        new_node->left = nodes[min1];
        new_node->right = nodes[min2];
        // 将原来的两个节点从数组中删除，将新节点加入数组
        if (min1 < min2) {
            for (k = min2; k < n - i - 1; k++) {
                nodes[k] = nodes[k + 1];
            }
            nodes[min1] = new_node;
        } else {
            for (k = min1; k < n - i - 2; k++) {
                nodes[k] = nodes[k + 1];
            }
            nodes[min2] = new_node;
        }
    }
    // 返回根节点
    return nodes[0];
}

// 构造哈夫曼编码表
void create_huffman_code_table(HuffmanTree root, HuffmanCode *table, int depth, char *path) {
    if (root->left == NULL && root->right == NULL) {
        // 叶子节点，保存编码
        int i;
        for (i = 0; i < depth; i++) {
            table[(int) root->ch].code[i] = path[i];
        }
        table[(int) root->ch].code[depth] = '\0';
        return;
    }
    // 遍历左子树
    path[depth] = '0';
    create_huffman_code_table(root->left, table, depth + 1, path);
    // 遍历右子树
    path[depth] = '1';
    create_huffman_code_table(root->right, table, depth + 1, path);
}

int main() {
    int w[] = {2, 3, 4, 7, 8, 9};
    int n = sizeof(w) / sizeof(int);
    // 构造哈夫曼树
    HuffmanTree root = create_huffman_tree(w, n);
    // 构造哈夫曼编码表
    HuffmanCode table[MAX_N];
    int i;
    for (i = 0; i < MAX_N; i++) {
        table[i].ch = i;
        table[i].code[0] = '\0';
    }
    char path[MAX_N];
    create_huffman_code_table(root, table, 0, path);
    // 输出哈夫曼编码表
    printf("Huffman Code Table:\n");
    for (i = 0; i < MAX_N; i++) {
        if (table[i].code[0] != '\0') {
            printf("%c: %s\n", table[i].ch, table[i].code);
        }
    }
    // 输出哈夫曼数组的值
    printf("Huffman Array:\n");
    for (i = 0; i < n; i++) {
        printf("%d ", w[i]);
    }
    printf("\n");
    for (i = 0; i < n; i++) {
        printf("%s ", table[w[i]].code);
    }
    printf("\n");
    // 释放空间
    for (i = 0; i < n; i++) {
        free(root);
    }
    return 0;
}

输出结果为：

Huffman Code Table:
2: 110
3: 111
4: 10
7: 0
8: 01
9: 00
Huffman Array:
2 3 4 7 8 9 
110 111 10 0 01 00