最优二叉树C语言代码

最优二叉树（也称为完全二叉树或哈夫曼树）是一种特殊的二叉树结构，其中每个节点都有最多两个子节点，并且除最后一层外，所有层级都是满的。在哈夫曼树中，叶子节点代表字符，而非叶节点则对应字符的编码。这种树常用于数据压缩，如 Huffman 编码。

下面是创建一个简单的哈夫曼树（最优二叉树）的基本 C 语言代码示例，它使用了优先队列（通常是一个最小堆）：

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

typedef struct Node {
    int weight;
    char symbol;
    struct Node* left, *right;
} Node;

// 插入新节点到堆中
Node* insert(Node** heap, int weight) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->weight = weight;
    newNode->left = newNode->right = NULL;
    
    if (*heap == NULL) {
        *heap = newNode;
    } else {
        Node* temp = *heap;
        while (temp && temp->weight < newNode->weight) {
            temp = temp->left ? temp->left : temp->right;
        }
        
        if (temp->weight > newNode->weight) {
            newNode->left = temp->left;
            temp->left = newNode;
        } else {
            newNode->right = temp->right;
            temp->right = newNode;
        }
    }
    return *heap;
}

// 构建哈夫曼树
Node* buildHuffmanTree(int weights[], int n) {
    // 创建一个大小为n的堆
    Node** heap = (Node**)calloc(n, sizeof(Node*));
    for (int i = 0; i < n; ++i) {
        heap[i] = insert(heap, weights[i]);
    }

    // 当只剩下一个元素时，返回它作为根节点
    while (heap[0]->left || heap[0]->right) {
        int leftWeight = heap[0]->left ? heap[0]->left->weight : INT_MAX;
        int rightWeight = heap[0]->right ? heap[0]->right->weight : INT_MAX;
        
        // 合并权重较小的两个节点
        Node* temp = insert(heap, leftWeight + rightWeight);
        temp->left = heap[0]->left;
        temp->right = heap[0]->right;
        
        // 移除已经合并的节点
        heap[0]->left = heap[0]->right = NULL;
        
        // 将新的堆顶节点移动到数组下标为1的位置
        heap[1] = heap[0];
        heap[0] = heap[1]->left ? heap[1]->left : heap[1]->right;
    }
    return heap[0];
}

// 主函数演示如何使用
void printHuffmanCode(Node* root, char symbols[], int codes[]) {
    // ... （这里需要递归处理，将生成的哈夫曼编码存储在codes数组中）
}

int main() {
    int weights[] = {4, 9, 3, 5, 1};
    int n = sizeof(weights)/sizeof(weights[0]);
    Node* huffmanRoot = buildHuffmanTree(weights, n);

    // 调用printHuffmanCode函数打印编码
    char symbols[] = {'a', 'b', 'c', 'd', 'e'};
    int codes[n];
    printHuffmanCode(huffmanRoot, symbols, codes);

    free(huffmanRoot); // 释放内存
    return 0;
}

这个代码实现了基本的哈夫曼树构建过程，但`printHuffmanCode`函数的实现会涉及递归遍历树和生成编码，这部分需要你自己补充。请注意，这只是一个基础示例，实际应用可能需要更复杂的数据结构和错误处理机制。