C语言构造哈夫曼树的算法

C语言构造哈夫曼树的算法大致如下：

1. 定义哈夫曼树的结构体：

typedef struct HuffmanTreeNode {
    int weight; // 权重
    int parent; // 父节点
    int left;   // 左子节点
    int right;  // 右子节点
} HuffmanTreeNode;

2. 定义哈夫曼树的节点数组：

HuffmanTreeNode nodes[2 * n - 1]; // n为叶子节点个数，哈夫曼树共有2n-1个节点

3. 初始化叶子节点，即将权重值存储到节点的weight中：

for (int i = 0; i < n; i++) {
    nodes[i].weight = weights[i];
    nodes[i].parent = -1;
    nodes[i].left = -1;
    nodes[i].right = -1;
}

4. 构建哈夫曼树：

for (int i = 0; i < n - 1; i++) {
    // 选择权重最小的两个节点作为合并的节点
    int min1 = -1, min2 = -1;
    for (int j = 0; j <= i; j++) {
        if (nodes[j].parent == -1) { // 未合并的节点
            if (min1 == -1 || nodes[j].weight < nodes[min1].weight) {
                min2 = min1;
                min1 = j;
            } else if (min2 == -1 || nodes[j].weight < nodes[min2].weight) {
                min2 = j;
            }
        }
    }
    // 合并节点
    nodes[min1].parent = i + n;
    nodes[min2].parent = i + n;
    nodes[i + n].weight = nodes[min1].weight + nodes[min2].weight;
    nodes[i + n].left = min1;
    nodes[i + n].right = min2;
}

5. 构建完成后，根据哈夫曼树构建哈夫曼编码表：

for (int i = 0; i < n; i++) {
    int node = i;
    int parent = nodes[node].parent;
    while (parent != -1) {
        if (nodes[parent].left == node) {
            codes[i] = strcat("0", codes[i]);
        } else {
            codes[i] = strcat("1", codes[i]);
        }
        node = parent;
        parent = nodes[node].parent;
    }
}