C++实现哈夫曼树的最优二进制编码构建算法逻辑 _ 贪心算法核心【源码】-C++-PHP中文网

哈夫曼树构建必须用小顶堆优先队列，不能用vector排序模拟；节点须用指针存储并统一释放内存；编码生成必须dfs递归，传值拼接字符串；需处理空树、单字符等边界情况。

c++实现哈夫曼树的最优二进制编码构建算法逻辑 _ 贪心算法核心【源码】

哈夫曼树构建必须用优先队列，不能用普通vector排序模拟

手动维护一个 std::vector 并每次 sort() 插入新节点，时间复杂度会退化到 O(n² log n)，而标准实现应是 O(n log n)。核心在于：每次只取权重最小的两个节点合并，天然适配 std::priority_queue 的堆结构。

注意默认 std::priority_queue<int></int> 是大顶堆，哈夫曼需要小顶堆，必须显式指定比较器：

struct Node {
    int weight;
    Node* left, *right;
    Node(int w) : weight(w), left(nullptr), right(nullptr) {}
};
auto cmp = [](Node* a, Node* b) { return a->weight > b->weight; };
std::priority_queue<node std::vector>, decltype(cmp)> pq(cmp);
</node>

漏写比较器会导致取到最大权重节点，结果完全错误
不要存 Node 值对象进队列——必须用指针，否则合并后原节点被拷贝，父子关系断裂
所有动态分配的 Node* 必须在最后统一 delete，否则内存泄漏

编码生成必须用DFS递归或栈模拟，不能靠父指针逆推

哈夫曼编码本质是根到叶的路径（左0右1），最可靠方式是从根出发 DFS 遍历，边走边拼接编码字符串。有人试图给每个节点加 parent 指针再从叶子往上回溯，但这样需额外存储、易空指针崩溃，且无法保证编码位序正确（谁左谁右必须由建树时决定）。

DFS 实现要点：

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

void generateCodes(Node* root, std::string code, 
                   std::unordered_map<char std::string>& codes) {
    if (!root) return;
    if (!root->left && !root->right) { // 叶子节点
        codes[root->ch] = code; // 假设 Node 存了字符 ch
        return;
    }
    generateCodes(root->left,  code + "0", codes);
    generateCodes(root->right, code + "1", codes);
}
</char>