如何用C++实现哈夫曼树的最优二进制编码构建算法核心逻辑

哈夫曼树的最优二进制编码构建是数据压缩领域的经典应用，核心思路是通过贪心策略反复合并权值最小的节点，最终生成带权路径长度最短的二叉树，对应每个叶子节点的二进制编码就是最优编码。实现该算法需要设计合理的节点结构，配合优先队列完成节点的快速选取与合并。

核心逻辑拆解

1. 节点结构设计

哈夫曼树的节点需要存储权值、左右子节点指针，为了方便后续生成编码，也可以存储对应的字符标识。节点之间需要支持权值比较，用于优先队列的排序。

2. 贪心策略的体现

算法的贪心选择是每次从当前所有节点中选取权值最小的两个节点进行合并，生成的新节点权值为两个子节点权值之和，再将新节点加入节点集合。这个选择过程不需要回溯，每一步都选取当前最优解，最终得到全局最优的树结构。

3. 编码生成逻辑

树构建完成后，从根节点出发遍历到每个叶子节点，向左走记录0，向右走记录1，到达叶子节点时记录的01序列就是该节点对应字符的最优二进制编码。

完整C++源码实现

以下是完整的实现代码，包含节点定义、哈夫曼树构建、编码生成三个核心部分：

#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>

// 哈夫曼树节点结构体
struct HuffmanNode {
    char ch;                // 节点对应的字符，内部合并节点用''表示
    int weight;             // 节点权值
    HuffmanNode* left;      // 左子节点
    HuffmanNode* right;     // 右子节点

    HuffmanNode(char c, int w) : ch(c), weight(w), left(nullptr), right(nullptr) {}
};

// 优先队列的比较函数，权值小的节点优先级高
struct CompareNode {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight;
    }
};

// 构建哈夫曼树，返回根节点
HuffmanNode* buildHuffmanTree(std::unordered_map<char, int> freq) {
    // 优先队列存储所有节点，自动按权值从小到大排序
    std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, CompareNode> pq;

    // 初始化所有叶子节点
    for (auto& pair : freq) {
        pq.push(new HuffmanNode(pair.first, pair.second));
    }

    // 贪心合并节点，直到只剩根节点
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top();
        pq.pop();
        HuffmanNode* right = pq.top();
        pq.pop();

        // 创建合并后的新节点，权值为两个子节点权值之和
        HuffmanNode* mergeNode = new HuffmanNode('', left->weight + right->weight);
        mergeNode->left = left;
        mergeNode->right = right;

        pq.push(mergeNode);
    }

    return pq.top();
}

// 递归生成编码，遍历哈夫曼树
void generateCode(HuffmanNode* root, std::string currentCode, std::unordered_map<char, std::string>& codeMap) {
    if (root == nullptr) return;

    // 到达叶子节点，记录编码
    if (root->ch != '') {
        codeMap[root->ch] = currentCode;
        return;
    }

    // 左子树编码加0，右子树编码加1
    generateCode(root->left, currentCode + "0", codeMap);
    generateCode(root->right, currentCode + "1", codeMap);
}

int main() {
    // 示例：字符及其出现频率
    std::unordered_map<char, int> charFreq = {
        {'a', 5},
        {'b', 9},
        {'c', 12},
        {'d', 13},
        {'e', 16},
        {'f', 45}
    };

    // 构建哈夫曼树
    HuffmanNode* root = buildHuffmanTree(charFreq);

    // 生成编码映射
    std::unordered_map<char, std::string> huffmanCode;
    generateCode(root, "", huffmanCode);

    // 输出每个字符的最优二进制编码
    std::cout << "哈夫曼最优二进制编码结果：" << std::endl;
    for (auto& pair : huffmanCode) {
        std::cout << pair.first << " : " << pair.second << std::endl;
    }

    return 0;
}

算法复杂度分析

构建哈夫曼树的过程中，优先队列的插入和删除操作时间复杂度为O(log n)，总共有n个叶子节点，合并过程需要n-1次操作，因此整体时间复杂度为O(n log n)，空间复杂度为O(n)，用于存储所有节点和生成的编码映射。

注意事项

• 节点指针使用完后需要手动释放内存，避免内存泄漏，实际项目中可以添加节点销毁函数
• 优先队列的比较函数需要严格定义，确保权值小的节点先出队
• 如果字符频率相同，合并顺序不影响最终编码的最优性，仅编码内容可能有差异

C++哈uffman_tree贪心算法二进制编码修改时间：2026-06-27 09:24:24