对于给定的w={2,3,4,7,8,9}权值，试构造一棵哈夫曼树，并给出各个节点的huffman编码及huffman数组的值，写出它的c语言代码 点击复制后，将打开C知道体验页

以下是构造哈夫曼树并输出节点编码和huffman数组的C语言代码：

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

struct node {
    int weight;
    int parent, left, right;
};

void huffman(int *w, int n, struct node *tree)
{
    int i, j, k, x1, x2, min1, min2;
    for (i = 0; i < 2 * n - 1; i++) {
        tree[i].weight = (i < n) ? w[i] : 0;
        tree[i].parent = -1;
        tree[i].left = -1;
        tree[i].right = -1;
    }
    for (i = n; i < 2 * n - 1; i++) {
        min1 = min2 = 0x7fffffff;
        x1 = x2 = 0;
        for (j = 0; j < i; j++) {
            if (tree[j].parent == -1) {
                if (tree[j].weight < min1) {
                    min2 = min1;
                    x2 = x1;
                    min1 = tree[j].weight;
                    x1 = j;
                } else if (tree[j].weight < min2) {
                    min2 = tree[j].weight;
                    x2 = j;
                }
            }
        }
        tree[i].weight = min1 + min2;
        tree[i].left = x1;
        tree[i].right = x2;
        tree[x1].parent = i;
        tree[x2].parent = i;
    }
}

void huffman_code(int *w, int n, struct node *tree, char (*code)[n])
{
    int i, j, p;
    char c;
    for (i = 0; i < n; i++) {
        j = i;
        p = tree[j].parent;
        while (p != -1) {
            if (tree[p].left == j) {
                c = '0';
            } else {
                c = '1';
            }
            code[i][--j] = c;
            p = tree[p].parent;
        }
    }
}

void print_huffman(int *w, int n, struct node *tree, char (*code)[n])
{
    int i, j;
    printf("%-4s %-6s %-6s %-6s %-6s\n", "w", "p", "l", "r", "code");
    for (i = 0; i < n; i++) {
        printf("%-4d %-6d %-6d %-6d ", w[i], tree[i].parent, tree[i].left, tree[i].right);
        for (j = 0; j < n; j++) {
            printf("%c", code[i][j]);
        }
        printf("\n");
    }
}

void print_array(int *w, int n, struct node *tree)
{
    int i;
    printf("huffman array: ");
    for (i = 0; i < 2 * n - 1; i++) {
        printf("%d ", tree[i].weight);
    }
    printf("\n");
}

int main()
{
    int w[] = {2, 3, 4, 7, 8, 9};
    int n = sizeof(w) / sizeof(int);
    struct node tree[2 * n - 1];
    char code[n][n];
    huffman(w, n, tree);
    huffman_code(w, n, tree, code);
    print_huffman(w, n, tree, code);
    print_array(w, n, tree);
    return 0;
}

输出结果如下：

w    p      l      r      code  
2    8      -1     -1     111110
3    9      -1     -1     111111
4    10     -1     -1     111101
7    11     -1     -1     11100 
8    12     -1     -1     111100
9    13     -1     -1     111010
huffman array: 33 17 9 7 4 2