C++实现哈夫曼树最优二进制编码构建算法核心源码
来源：互联网 2026-05-10 12:05:08哈夫曼树用于生成最优二进制编码，核心是构建带权路径最短的二叉树。实现主要有三种方案：基于优先队列的标准方法逻辑清晰；基于向量手动查找实现简单但较慢；基于数组的紧凑实现适合内存受限场景。可根据需求选择。
在C++中实现哈夫曼树，其核心目标是运用贪心策略，将一组带权重的字符构建成一棵带权路径长度最短的二叉树，从而获得最优的二进制编码。这一过程虽然原理清晰，但在具体实现上存在多种路径。以下三种方案各有其适用场景与特点，可根据实际项目需求进行选择。
长期稳定更新的攒劲资源： >>>点此立即查看<<<
一、基于优先队列（最小堆）的标准实现
这是最符合教科书描述的经典方法。使用std::priority_queue配合自定义比较器，确保每次都能弹出当前权值最小的两个节点。将它们合并后，将新节点重新放入队列，循环此过程直至队列中仅剩一个根节点。
该方法的优势在于逻辑清晰，严格遵循哈夫曼算法的原始定义，时间复杂度稳定在O(n log n)，且易于验证。具体步骤如下：
首先，定义节点结构体，包含字符、权值、左右子节点指针等成员，并重载小于运算符以便优先队列进行排序。
接着，将所有叶子节点（即原始字符及其出现频次）全部压入队列。
随后进入核心循环：只要队列中的节点数量大于1，便弹出权值最小的两个节点，以它们为左右孩子创建一个新的父节点（其权值为两者之和），并将此新节点压回队列。
循环结束后，队列中剩余的节点即为哈夫曼树的根节点。最后，从根节点开始递归遍历，向左子树移动记录‘0’，向右子树移动记录‘1’，当到达叶子节点时，所记录的路径即为该字符的哈夫曼编码。
二、基于 vector + 手动查找最小值的无堆实现
若开发环境受限无法使用STL的优先队列，或希望避免堆操作带来的开销，可考虑此方案。它使用vector存储节点，每次合并前通过线性扫描手动找出权值最小和次小的两个节点。
此方法的代价是时间复杂度上升至O(n)，但换来了更紧凑的空间控制与更少的依赖。实现流程如下：
首先，使用一个vector存储所有叶子节点的指针。
随后开始循环：遍历当前vector，找到权值最小和次小的两个节点的索引。
接着，创建一个新的内部节点，其权值为这两个节点权值之和，并正确设置其左右孩子指针。
之后，从vector中移除已选中的两个节点，并将新创建的节点加入。
重复此过程，直到vector中仅剩一个节点，该节点即为根节点。
生成编码表时，可使用栈来模拟非递归的后序遍历，同时用另一个栈同步记录路径上的‘0’和‘1’，以提升效率。
三、基于数组静态存储的紧凑内存实现
此方案追求极致的内存控制。它预先分配一个固定大小的结构体数组，将所有节点存储其中，并使用整型索引替代指针，完全避免了动态内存分配。
这对于嵌入式系统、实时系统或任何对内存有严格限制的场景而言是理想选择。整个编码生成过程都可在栈上完成。具体实现方式如下：
首先，定义一个节点结构，包含权值、字符以及三个整型字段：left、right、parent，均用索引表示，-1代表空值。
将数组的前n个位置预留给叶子节点，填入字符和权值，父节点和子节点索引均初始化为-1。
然后从索引n开始构造内部节点：每次在当前所有未绑定父节点的节点中（即parent == -1），扫描找出权值最小的两个索引i和j。
在下一个可用位置创建新节点，其权值为nodes[i].weight + nodes[j].weight，并设置其左右孩子索引为i和j，同时将i和j的父节点索引指向此新位置。
重复此过程，直到总共生成2n-1个节点。最后一个节点（索引2n-2）即为根节点。
生成编码时，对每个叶子节点，顺着它的parent索引向上回溯至根节点。若当前节点是其父节点的左孩子，则记录‘0’；若是右孩子，则记录‘1’。最后将记录的路径反转，即可得到正确的哈夫曼编码。
侠游戏发布此文仅为了传递信息，不代表侠游戏网站认同其观点或证实其描述
