数组实现哈夫曼树编码的核心是用下标模拟树结构：设大小为2n−1的结构体数组，每项含weight、parent、lchild、rchild四字段；前n项存字符权值，通过n−1次选最小权“孤儿”节点合并构建树；再从各叶子沿parent上溯，逆序记录0/1生成编码。
用数组实现哈夫曼树编码，核心在于**不用指针、不建链表**，而是靠下标关系模拟父子与兄弟结构，同时把字符权值和最终编码一一对应存下来。关键不是写得“像树”，而是让数组下标承载逻辑关系，并确保编码能从叶子反推到根。
数组结构设计：固定大小 + 四字段
定义一个结构体数组（或结构体数组的简化版），每个元素存四个整数：
- weight：当前节点权值（初始时前n个为字符频率，后续为子树和）
- parent：双亲在数组中的下标，-1表示无父节点（即尚未被合并）
- lchild / rchild：左右孩子下标，-1表示空
数组总长度设为 2n − 1——这是哈夫曼树的硬性性质（n个叶子 → 总结点数必为2n−1），不能少，否则无法容纳所有中间节点。
权值映射关系怎么存？分两步走
权值本身是输入源头，但“哪个字符对应哪个权值”必须在编码生成前就绑定好。常见做法：
- 初始化时，前n个数组元素（下标0到n−1）按顺序存放字符及其权值，例如：
ht[0].weight = 5; ht[0].ch = 'a'; - 额外维护一个字符→下标映射表，比如
int idx['z' + 1]，令idx['a'] = 0，这样后续查‘a’的编码，直接去下标0对应的叶子出发回溯即可 - 或者更简洁：用一个结构体数组
char_to_weight[] = {{'a',5}, {'b',29}, ...}，构建树时按此顺序填入前n个位置
构造哈夫曼树：n−1次合并，每次找两个“孤儿”
所谓“孤儿”，就是 parent == -1 的节点。算法逻辑如下：
- 循环 n−1 次（i 从 n 到 2n−2）
- 在已存在节点中（下标 0 到 i−1），扫描出 weight 最小且 parent == -1 的两个节点，记下标为 s1、s2
- 新建节点 i：
ht[i].weight = ht[s1].weight + ht[s2].weight - 设置父子关系：
ht[s1].parent = ht[s2].parent = i；ht[i].lchild = s1; ht[i].rchild = s2（左小右大或反之均可，但需统一约定）
注意：扫描时跳过已有 parent 的节点，避免重复使用；合并后 s1、s2 就不再是叶子，不能再参与后续选择。
生成哈夫曼编码：从叶子上溯，逆序填码
对每个原始字符（即下标 0 到 n−1），从它出发沿 parent 往上走到根，边走边记录路径方向：
- 申请一个临时数组
cd[n]，设start = n−1，cd[start] = '\0' - c = 当前叶子下标，f = ht[c].parent
- while (f != -1)：
– 若 c 是 f 的左孩子（ht[f].lchild == c），则cd[--start] = '0'
– 否则cd[--start] = '1'
– 更新 c = f，f = ht[c].parent - 此时
&cd[start]就是该字符的哈夫曼编码字符串，复制到结果数组中（如code_table[i] = strdup(&cd[start])）
这个“逆序填、正向读”的方式，天然适配从叶到根的遍历路径，无需翻转。
不复杂但容易忽略：数组下标从0开始还是从1开始、parent初始化为-1还是0、字符是否带进结构体——这些细节一旦混用，会导致回溯失败或越界。统一按“下标0起、parent初值-1、字符单独映射”来组织，最稳。
