用C语言写出哈夫曼树的代码和注释

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

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

// 定义哈夫曼树节点结构体
typedef struct huffman_node {
    int value; // 节点权值
    struct huffman_node *left; // 左子节点指针
    struct huffman_node *right; // 右子节点指针
} HuffmanNode;

// 定义优先队列（小根堆）结构体
typedef struct priority_queue {
    HuffmanNode **nodes; // 节点数组指针
    int size; // 当前队列大小
    int capacity; // 队列容量
} PriorityQueue;

// 创建一个新的哈夫曼树节点
HuffmanNode *new_huffman_node(int value) {
    HuffmanNode *node = (HuffmanNode *) malloc(sizeof(HuffmanNode));
    node->value = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 交换两个哈夫曼树节点的位置
void swap_nodes(HuffmanNode **a, HuffmanNode **b) {
    HuffmanNode *tmp = *a;
    *a = *b;
    *b = tmp;
}

// 初始化优先队列
PriorityQueue *init_priority_queue(int capacity) {
    PriorityQueue *queue = (PriorityQueue *) malloc(sizeof(PriorityQueue));
    queue->nodes = (HuffmanNode **) malloc(sizeof(HuffmanNode *) * capacity);
    queue->size = 0;
    queue->capacity = capacity;
    return queue;
}

// 向优先队列插入一个节点
void insert_node(PriorityQueue *queue, HuffmanNode *node) {
    // 如果队列已满则返回
    if (queue->size == queue->capacity) {
        return;
    }
    // 将新节点插入队列末尾
    queue->nodes[queue->size++] = node;
    int index = queue->size - 1;
    // 将新节点上浮到正确的位置
    while (index > 0 && queue->nodes[index]->value < queue->nodes[(index - 1) / 2]->value) {
        swap_nodes(&queue->nodes[index], &queue->nodes[(index - 1) / 2]);
        index = (index - 1) / 2;
    }
}

// 从优先队列中取出最小的节点
HuffmanNode *pop_min_node(PriorityQueue *queue) {
    // 如果队列为空则返回 NULL
    if (queue->size == 0) {
        return NULL;
    }
    // 取出队列头部节点
    HuffmanNode *min_node = queue->nodes[0];
    // 将队列尾部节点移到头部
    queue->nodes[0] = queue->nodes[--queue->size];
    int index = 0;
    // 将头部节点下沉到正确的位置
    while (index * 2 + 1 < queue->size) {
        int left_child_index = index * 2 + 1;
        int right_child_index = index * 2 + 2;
        int min_child_index = left_child_index;
        if (right_child_index < queue->size && queue->nodes[right_child_index]->value < queue->nodes[left_child_index]->value) {
            min_child_index = right_child_index;
        }
        if (queue->nodes[min_child_index]->value >= queue->nodes[index]->value) {
            break;
        }
        swap_nodes(&queue->nodes[index], &queue->nodes[min_child_index]);
        index = min_child_index;
    }
    return min_node;
}

// 构建哈夫曼树
HuffmanNode *build_huffman_tree(int *weights, int size) {
    PriorityQueue *queue = init_priority_queue(size);
    // 将所有树叶节点插入优先队列
    for (int i = 0; i < size; i++) {
        insert_node(queue, new_huffman_node(weights[i]));
    }
    // 不断取出两个最小的节点合并成一个新节点，直到队列中只有一个节点为止
    while (queue->size > 1) {
        HuffmanNode *left_child = pop_min_node(queue);
        HuffmanNode *right_child = pop_min_node(queue);
        HuffmanNode *new_node = new_huffman_node(left_child->value + right_child->value);
        new_node->left = left_child;
        new_node->right = right_child;
        insert_node(queue, new_node);
    }
    HuffmanNode *root = pop_min_node(queue);
    free(queue->nodes);
    free(queue);
    return root;
}

// 打印哈夫曼树的结构
void print_huffman_tree(HuffmanNode *root, int depth) {
    if (root == NULL) {
        return;
    }
    for (int i = 0; i < depth; i++) {
        printf(" ");
    }
    if (root->left == NULL && root->right == NULL) {
        printf("%d\n", root->value);
    } else {
        printf("+-\n");
        print_huffman_tree(root->left, depth + 1);
        print_huffman_tree(root->right, depth + 1);
    }
}

int main() {
    int weights[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    int size = sizeof(weights) / sizeof(weights[0]);
    HuffmanNode *root = build_huffman_tree(weights, size);
    print_huffman_tree(root, 0);
    return 0;
}

以上代码实现了哈夫曼树的构建和打印结构功能。可以通过修改 `weights` 数组中的元素来构建不同的哈夫曼树。