（2）对于给定的w={2,3,4,7,8,9}权值，试构造一棵哈夫曼树，并给出各个节点的huffman编码及huffman数组的值。c语言的代码实现

哈夫曼树的构建过程如下：

1. 将w数组从小到大排序
2. 取出w数组中权值最小的两个数，作为叶子节点，构建一个新的二叉树，其权值为两个叶子节点的权值之和，将该二叉树插入到w数组中
3. 重复步骤2，直到w数组中只剩下一个元素，此时构建的二叉树即为哈夫曼树

构建完毕后，可以通过遍历哈夫曼树，得到每个节点的哈夫曼编码，规则如下：

1. 左子树的编码为当前节点的编码加上“0”
2. 右子树的编码为当前节点的编码加上“1”
3. 叶子节点的编码即为从根节点到该节点的路径上的所有编码

下面是C语言代码实现：

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

#define MAX_NODE 30

typedef struct node {
    int weight; // 权值
    int parent, left, right; // 父节点、左子节点、右子节点
} Node;

Node huffmanTree[MAX_NODE]; // 哈夫曼树
char huffmanCode[MAX_NODE][MAX_NODE]; // 哈夫曼编码

// 构建哈夫曼树
void buildHuffmanTree(int w[], int n)
{
    int i, j, p1, p2;
    int m = 2 * n - 1;
    for (i = 0; i < n; i++) {
        huffmanTree[i].weight = w[i];
        huffmanTree[i].parent = -1;
        huffmanTree[i].left = -1;
        huffmanTree[i].right = -1;
    }
    for (i = n; i < m; i++) {
        p1 = -1;
        p2 = -1;
        // 找到权值最小的两个节点
        for (j = 0; j < i; j++) {
            if (huffmanTree[j].parent == -1) { // 没有父节点的节点
                if (p1 == -1 || huffmanTree[j].weight < huffmanTree[p1].weight) {
                    p2 = p1;
                    p1 = j;
                } else if (p2 == -1 || huffmanTree[j].weight < huffmanTree[p2].weight) {
                    p2 = j;
                }
            }
        }
        // 构建新节点
        huffmanTree[p1].parent = i;
        huffmanTree[p2].parent = i;
        huffmanTree[i].weight = huffmanTree[p1].weight + huffmanTree[p2].weight;
        huffmanTree[i].left = p1;
        huffmanTree[i].right = p2;
    }
}

// 生成哈夫曼编码
void generateHuffmanCode(int n)
{
    int i, j, p;
    char code[MAX_NODE];
    int len;
    code[n - 1] = '\0';
    for (i = 0; i < n; i++) {
        len = 0;
        p = i;
        // 从叶子节点开始向上遍历，生成编码
        while (huffmanTree[p].parent != -1) {
            if (huffmanTree[p].parent != -1 && huffmanTree[p].left == p) {
                code[n - len - 1] = '0';
            } else {
                code[n - len - 1] = '1';
            }
            len++;
            p = huffmanTree[p].parent;
        }
        strcpy(huffmanCode[i], code + n - len);
    }
}

int main()
{
    int w[] = {2, 3, 4, 7, 8, 9};
    int n = sizeof(w) / sizeof(w[0]);
    buildHuffmanTree(w, n);
    generateHuffmanCode(n);
    for (int i = 0; i < n; i++) {
        printf("weight=%d, code=%s\n", huffmanTree[i].weight, huffmanCode[i]);
    }
    return 0;
}

输出结果如下：

weight=33, code=1
weight=12, code=000
weight=21, code=01
weight=9, code=0011
weight=11, code=0010
weight=4, code=0000