c语言哈夫曼树编译器

### C语言实现哈夫曼树

#### 创建节点结构体
为了构建哈夫曼树，定义一个表示树节点的数据结构是非常重要的。此结构通常包含字符、频率以及指向左右孩子的指针。

typedef struct TreeNode {
    unsigned char ch;
    int freq;
    struct TreeNode *left, *right;
} Node;

#### 初始化森林数组
初始化一系列单节点的二叉树，这些树构成了初始森林的一部分。每棵树仅有一个根节点，其权重等于相应字符出现次数。

Node* createForest(int size) {
    Node **forest = (Node**)malloc(size * sizeof(Node *));
    for (int i = 0; i < size; ++i){
        forest[i] = (Node*)malloc(sizeof(Node));
        forest[i]->ch = 'a' + i % ('z' - 'a' + 1); // 示例字符分配
        forest[i]->freq = rand() % 100 + 1;         // 随机生成频率
        forest[i]->left = NULL;
        forest[i]->right = NULL;
    }
    return *forest;
}

#### 构建哈夫曼树
通过不断选取两棵具有最小权重的独立树并创建一个新的内部节点来连接它们直到只剩下一棵树为止。新节点的权重为其子节点权重之和[^3]。

Node* buildHuffmanTree(Node** forest, int n) {
    while (--n > 0) {
        qsort(forest, n, sizeof(Node*), compareNodes);
        
        Node* left = forest[n-1];
        Node* right = forest[n];

        Node* parent = (Node *) malloc(sizeof(Node));
        parent->freq = left->freq + right->freq;
        parent->ch = '\0';
        parent->left = left;
        parent->right = right;

        forest[n-1] = parent;
    }

    return forest[0];    
}

// 辅助函数用于比较两个节点大小
int compareNodes(const void* a, const void* b) {
    return (*(Node **)b)->freq - (*(Node **)a)->freq;
}

#### 编码过程
一旦建立了哈夫曼树，则可以通过遍历这棵树来进行编码操作。对于每一个叶子结点来说，路径上的每一位决定了最终编码串中的对应位（左分支为`0`而右分支为`1`)。

void generateCodes(Node* root, int top, char code[], char codes[][MAX_CODE_LENGTH]) {
    if (!root)
        return;

    if (!root->left && !root->right) {
        strcpy(codes[root->ch], code);
        printf("Character: %c | Frequency: %d | Code: %s\n", root->ch, root->freq, code);
    } else {
        static char buffer[MAX_CODE_LENGTH];
        strncpy(buffer, code, MAX_CODE_LENGTH);

        strcat(code, "0");
        generateCodes(root->left, top + 1, code, codes);

        strcpy(code, buffer);
        strcat(code, "1");
        generateCodes(root->right, top + 1, code, codes);
    }
}

上述代码展示了如何利用C语言实现哈夫曼树及其编码功能。需要注意的是，在实际应用中还需要考虑更多细节问题，比如输入验证、内存管理等[^2]。