构造哈夫曼树 c语言数据结构

哈夫曼树是一种特殊的二叉树，它的每个叶子节点都对应一个字符，并且每个字符的权值（即出现频率）越高，它在哈夫曼树中距离根节点越近。构造哈夫曼树的基本思路是：首先将所有字符按照权值从小到大排序，然后选取权值最小的两个字符，将它们作为左右子节点构造一棵二叉树，它的根节点的权值为两个子节点的权值之和。接着将新的二叉树插入到原来的字符集合中，再次排序，重复以上步骤，直到只剩下一棵二叉树，即为所求的哈夫曼树。

以下是C语言实现哈夫曼树的代码：

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

typedef struct node {
    char ch;
    int freq;
    struct node* left;
    struct node* right;
} Node;

typedef struct list {
    Node* node;
    struct list* next;
} List;

List* create_list(char ch, int freq) {
    List* list = (List*) malloc(sizeof(List));
    list->node = (Node*) malloc(sizeof(Node));
    list->node->ch = ch;
    list->node->freq = freq;
    list->node->left = NULL;
    list->node->right = NULL;
    list->next = NULL;
    return list;
}

List* add_list(List* list, char ch, int freq) {
    if (list == NULL) {
        return create_list(ch, freq);
    }
    List* tmp = list;
    while (tmp->next != NULL) {
        tmp = tmp->next;
    }
    tmp->next = create_list(ch, freq);
    return list;
}

List* remove_list(List* list, List* node) {
    if (list == node) {
        list = list->next;
        free(node->node);
        free(node);
        return list;
    }
    List* tmp = list;
    while (tmp->next != node) {
        tmp = tmp->next;
    }
    tmp->next = node->next;
    free(node->node);
    free(node);
    return list;
}

Node* create_huffman_tree(List* list) {
    while (list->next != NULL) {
        List* node1 = list;
        List* node2 = list->next;
        list = remove_list(list, node1);
        list = remove_list(list, node2);
        Node* node = (Node*) malloc(sizeof(Node));
        node->ch = '\0';
        node->freq = node1->node->freq + node2->node->freq;
        node->left = node1->node;
        node->right = node2->node;
        list = add_list(list, '\0', node->freq);
        list->node = node;
    }
    return list->node;
}

void print_huffman_tree(Node* node) {
    if (node == NULL) {
        return;
    }
    printf("%c:%d\n", node->ch, node->freq);
    print_huffman_tree(node->left);
    print_huffman_tree(node->right);
}

int main() {
    List* list = NULL;
    list = add_list(list, 'a', 5);
    list = add_list(list, 'b', 9);
    list = add_list(list, 'c', 12);
    list = add_list(list, 'd', 13);
    list = add_list(list, 'e', 16);
    list = add_list(list, 'f', 45);
    Node* node = create_huffman_tree(list);
    print_huffman_tree(node);
    return 0;
}