C语言构造哈夫曼树并打印哈夫曼编码

以下是使用C语言构造哈夫曼树并打印哈夫曼编码的示例代码：

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

typedef struct HuffmanNode {
    int weight;
    struct HuffmanNode *left;
    struct HuffmanNode *right;
} HuffmanNode;

typedef struct {
    int size;
    HuffmanNode **nodes;
} MinHeap;

HuffmanNode* createHuffmanNode(int weight) {
    HuffmanNode *node = (HuffmanNode*)malloc(sizeof(HuffmanNode));
    node->weight = weight;
    node->left = NULL;
    node->right = NULL;
    return node;
}

MinHeap* createMinHeap(int capacity) {
    MinHeap *heap = (MinHeap*)malloc(sizeof(MinHeap));
    heap->size = 0;
    heap->nodes = (HuffmanNode**)malloc(capacity * sizeof(HuffmanNode*));
    return heap;
}

void swapNodes(HuffmanNode **a, HuffmanNode **b) {
    HuffmanNode *temp = *a;
    *a = *b;
    *b = temp;
}

void minHeapify(MinHeap *heap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < heap->size && heap->nodes[left]->weight < heap->nodes[smallest]->weight) {
        smallest = left;
    }

    if (right < heap->size && heap->nodes[right]->weight < heap->nodes[smallest]->weight) {
        smallest = right;
    }

    if (smallest != idx) {
        swapNodes(&heap->nodes[idx], &heap->nodes[smallest]);
        minHeapify(heap, smallest);
    }
}

void buildMinHeap(MinHeap *heap) {
    int n = heap->size - 1;
    int i;

    for (i = (n - 1) / 2; i >= 0; i--) {
        minHeapify(heap, i);
    }
}

HuffmanNode* extractMin(MinHeap *heap) {
    HuffmanNode *minNode = heap->nodes[0];
    heap->nodes[0] = heap->nodes[heap->size - 1];
    heap->size--;
    minHeapify(heap, 0);
    return minNode;
}

void insertMinHeap(MinHeap *heap, HuffmanNode *node) {
    int i = heap->size;
    heap->size++;

    while (i > 0 && node->weight < heap->nodes[(i - 1) / 2]->weight) {
        heap->nodes[i] = heap->nodes[(i - 1) / 2];
        i = (i - 1) / 2;
    }

    heap->nodes[i] = node;
}

int isLeaf(HuffmanNode *node) {
    return !(node->left) && !(node->right);
}

void printCodes(HuffmanNode *root, int *code, int top) {
    if (root->left) {
        code[top] = 0;
        printCodes(root->left, code, top + 1);
    }

    if (root->right) {
        code[top] = 1;
        printCodes(root->right, code, top + 1);
    }

    if (isLeaf(root)) {
        printf("Character: %c, Weight: %d, Code: ", root->data, root->weight);
        for (int i = 0; i < top; i++) {
            printf("%d", code[i]);
        }
        printf("\n");
    }
}

void huffmanCoding(int *weights, int num) {
    MinHeap *heap = createMinHeap(num);

    for (int i = 0; i < num; i++) {
        heap->nodes[i] = createHuffmanNode(weights[i]);
    }

    heap->size = num;
    buildMinHeap(heap);

    while (heap->size > 1) {
        HuffmanNode *left = extractMin(heap);
        HuffmanNode *right = extractMin(heap);

        HuffmanNode *newNode = createHuffmanNode(left->weight + right->weight);
        newNode->left = left;
        newNode->right = right;

        insertMinHeap(heap, newNode);
    }

    int code[100];
    int top = 0;
    HuffmanNode *root = extractMin(heap);
    printCodes(root, code, top);
}

int main() {
    int weights[] = {5, 9, 12, 13, 16, 45};
    int num = sizeof(weights) / sizeof(weights[0]);

    huffmanCoding(weights, num);

    return 0;
}