用C语言编译构造哈夫曼树

首先，我们需要定义哈夫曼树的数据结构。哈夫曼树是一种特殊的二叉树，每个节点都有一个权值，所有叶子节点的权值都不相同，且叶子节点的权值和等于根节点的权值。

typedef struct TreeNode {
    int weight;  // 权值
    int parent;  // 父节点下标
    int left;    // 左子节点下标
    int right;   // 右子节点下标
} TreeNode;

接下来，我们需要定义一些基本的操作函数。首先是建立哈夫曼树的函数，传入一个权值数组和数组长度，返回一个哈夫曼树的根节点下标。

int buildHuffmanTree(int *weight, int n) {
    // 创建节点数组
    TreeNode *nodes = (TreeNode*)malloc(sizeof(TreeNode) * (2 * n - 1));
    for (int i = 0; i < 2 * n - 1; i++) {
        nodes[i].weight = 0;
        nodes[i].parent = -1;
        nodes[i].left = -1;
        nodes[i].right = -1;
    }
    // 初始化叶子节点
    for (int i = 0; i < n; i++) {
        nodes[i].weight = weight[i];
    }
    // 构造哈夫曼树
    int m = 2 * n - 1;
    for (int i = n; i < m; i++) {
        int x1, x2;
        select(nodes, i - 1, &x1, &x2);
        nodes[x1].parent = i;
        nodes[x2].parent = i;
        nodes[i].left = x1;
        nodes[i].right = x2;
        nodes[i].weight = nodes[x1].weight + nodes[x2].weight;
    }
    // 返回根节点下标
    return m - 1;
}

在构造哈夫曼树的过程中，我们需要实现一个选择函数，用于从节点数组中选择两个权值最小的节点。这个函数的实现比较简单，可以使用一个循环遍历整个节点数组，找到权值最小的两个节点。

void select(TreeNode *nodes, int n, int *x1, int *x2) {
    int i, j;
    i = j = -1;
    for (int k = 0; k <= n; k++) {
        if (nodes[k].parent != -1) {
            continue;
        }
        if (i == -1 || nodes[k].weight < nodes[i].weight) {
            j = i;
            i = k;
        } else if (j == -1 || nodes[k].weight < nodes[j].weight) {
            j = k;
        }
    }
    *x1 = i;
    *x2 = j;
}

最后，我们可以编写一个测试函数来验证我们的代码是否正确。

void test() {
    int weight[] = {5, 2, 4, 7, 1, 3, 6};
    int n = sizeof(weight) / sizeof(int);
    int root = buildHuffmanTree(weight, n);
    printf("根节点权值为：%d\n", nodes[root].weight);
}

完整代码如下：

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

typedef struct TreeNode {
    int weight;  // 权值
    int parent;  // 父节点下标
    int left;    // 左子节点下标
    int right;   // 右子节点下标
} TreeNode;

void select(TreeNode *nodes, int n, int *x1, int *x2) {
    int i, j;
    i = j = -1;
    for (int k = 0; k <= n; k++) {
        if (nodes[k].parent != -1) {
            continue;
        }
        if (i == -1 || nodes[k].weight < nodes[i].weight) {
            j = i;
            i = k;
        } else if (j == -1 || nodes[k].weight < nodes[j].weight) {
            j = k;
        }
    }
    *x1 = i;
    *x2 = j;
}

int buildHuffmanTree(int *weight, int n) {
    // 创建节点数组
    TreeNode *nodes = (TreeNode*)malloc(sizeof(TreeNode) * (2 * n - 1));
    for (int i = 0; i < 2 * n - 1; i++) {
        nodes[i].weight = 0;
        nodes[i].parent = -1;
        nodes[i].left = -1;
        nodes[i].right = -1;
    }
    // 初始化叶子节点
    for (int i = 0; i < n; i++) {
        nodes[i].weight = weight[i];
    }
    // 构造哈夫曼树
    int m = 2 * n - 1;
    for (int i = n; i < m; i++) {
        int x1, x2;
        select(nodes, i - 1, &x1, &x2);
        nodes[x1].parent = i;
        nodes[x2].parent = i;
        nodes[i].left = x1;
        nodes[i].right = x2;
        nodes[i].weight = nodes[x1].weight + nodes[x2].weight;
    }
    // 返回根节点下标
    return m - 1;
}

int main() {
    int weight[] = {5, 2, 4, 7, 1, 3, 6};
    int n = sizeof(weight) / sizeof(int);
    int root = buildHuffmanTree(weight, n);
    printf("根节点权值为：%d\n", nodes[root].weight);
    return 0;
}