C语言 写函数以字母出现次数作权值，建Haffman树（n个叶子），给出每个字母的Haffman编码。

下面是基于哈夫曼编码的 C 语言实现代码：

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

#define MAX_LETTERS 26

typedef struct Node {
    int weight;
    int parent;
    int lchild;
    int rchild;
    char code[MAX_LETTERS];
} Node;

void build_huffman_tree(Node *nodes, int n);
void generate_huffman_code(Node *nodes, int n);

int main() {
    // 初始化字符出现次数
    int freq[MAX_LETTERS] = {0};
    char str[] = "hello world";
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        freq[str[i] - 'a']++;
    }

    // 构建哈夫曼树
    Node nodes[MAX_LETTERS * 2 - 1];
    int n = MAX_LETTERS;
    for (int i = 0; i < n; i++) {
        nodes[i].weight = freq[i];
        nodes[i].parent = -1;
        nodes[i].lchild = -1;
        nodes[i].rchild = -1;
    }
    build_huffman_tree(nodes, n);

    // 生成哈夫曼编码
    generate_huffman_code(nodes, n);

    // 输出每个字符的哈夫曼编码
    for (int i = 0; i < n; i++) {
        printf("%c: %s\n", i + 'a', nodes[i].code);
    }

    return 0;
}

void build_huffman_tree(Node *nodes, int n) {
    int min1, min2;
    for (int i = n; i < 2 * n - 1; i++) {
        min1 = min2 = 0;
        for (int j = 0; j < i; j++) {
            if (nodes[j].parent == -1) {
                if (nodes[j].weight < nodes[min1].weight) {
                    min2 = min1;
                    min1 = j;
                } else if (nodes[j].weight < nodes[min2].weight) {
                    min2 = j;
                }
            }
        }
        nodes[min1].parent = i;
        nodes[min2].parent = i;
        nodes[i].weight = nodes[min1].weight + nodes[min2].weight;
        nodes[i].lchild = min1;
        nodes[i].rchild = min2;
    }
}

void generate_huffman_code(Node *nodes, int n) {
    for (int i = 0; i < n; i++) {
        int j = i;
        int parent = nodes[j].parent;
        while (parent != -1) {
            if (nodes[parent].lchild == j) {
                strcat(nodes[i].code, "0");
            } else {
                strcat(nodes[i].code, "1");
            }
            j = parent;
            parent = nodes[j].parent;
        }
        strrev(nodes[i].code);
    }
}

代码中，我们首先统计字符串中每个字母出现的次数，然后根据出现次数构建哈夫曼树，最后根据哈夫曼树生成每个字母的哈夫曼编码。在生成哈夫曼编码时，我们从每个叶子节点出发，沿着其父节点一直到根节点，记录下所经过的路径（0 表示左子树，1 表示右子树），然后把路径逆序，就得到了该叶子节点的哈夫曼编码。