哈夫曼树构建有三种C++实现方案：一、基于priority_queue的最小堆法，时间复杂度O(n log n)；二、vector手动找最小值法，时间复杂度O(n²)；三、静态数组索引模拟法，适合内存受限环境。
如果您需要在 C++ 环境中构建哈夫曼树并生成对应字符的最优二进制编码，则需基于贪心策略动态构造带权路径长度最小的二叉树。以下是三种相互独立、可直接编译运行的核心源码实现方案：
一、基于优先队列（最小堆）的标准实现
该方案使用 std::priority_queue 配合自定义比较器，每次合并权值最小的两棵子树，符合哈夫曼算法原始定义，时间复杂度为 O(n log n)，结构清晰且易于验证正确性。
1、定义哈夫曼树节点结构体，包含字符、权值、左右子指针，并重载小于运算符用于最小堆排序。
2、将所有叶节点（字符及其频次）压入 priority_queue。
立即学习“C++免费学习笔记（深入）”；
3、当队列中节点数大于 1 时，连续弹出两个最小权值节点，构造新父节点，权值为二者之和，左子为较小者，右子为较大者，再将父节点压回队列。
4、队列仅剩一个节点时即为哈夫曼树根节点。
5、从根出发递归遍历，向左走记 '0'，向右走记 '1'，到达叶节点时保存字符到编码字符串的映射关系。
二、基于 vector + 手动查找最小值的无堆实现
该方案不依赖 STL 堆容器，适用于嵌入式或受限环境；通过线性扫描维护两个最小索引，避免堆操作开销，空间更紧凑，但时间复杂度升至 O(n²)。
1、初始化 vector
2、循环执行：遍历当前 vector，找出权值最小与次小的两个节点索引，确保二者不为同一位置。
3、创建新内部节点，权值为两者之和，左子指向权值较小节点，右子指向另一节点。
4、从 vector 中删除已选中的两个节点指针，并插入新节点指针。
5、重复步骤 2–4 直至 vector 大小为 1，此时唯一元素即为根节点。
6、使用栈模拟非递归后序遍历，结合路径栈同步记录编码位，生成最终编码表。
三、基于数组静态存储的紧凑内存实现
该方案预先分配固定大小数组模拟树节点池，所有节点以索引代替指针，避免动态内存分配与指针解引用，适合实时系统或内存严格受限场景，支持完全栈式编码生成。
1、声明 struct Node { int weight; char ch; int left, right; int parent; }，其中 left/right/parent 均为整型索引，-1 表示空。
2、前 n 个位置存放叶节点（ch 非 '\0'，weight 为频次，left=right=parent=-1）。
3、从索引 n 开始逐个构造内部节点：每次扫描前缀区间 [0, current_size)，找出 weight 最小且 parent == -1 的两个节点索引 i 和 j。
4、在 current_size 位置新建节点，weight = nodes[i].weight + nodes[j].weight，left = i，right = j，nodes[i].parent = nodes[j].parent = current_size，current_size++。
5、当 total_nodes 达到 2n−1 时停止，根节点索引为 2n−2。
6、对每个叶节点，沿 parent 字段向上回溯至根，逆序记录路径（left 贡献 '0'，right 贡献 '1'），反转后得到该字符编码。
