简介面向数据结构课程实训的“构建哈夫曼树及编码”配套资源包适合正在完成头歌平台相关实验、希望掌握最优二叉树构造与哈夫曼编码原理的学习者。资源围绕两关任务展开第一关要求根据字符权值构造带权路径最短的哈夫曼树第二关则基于已建树生成前缀编码包内提供完整C语言实现与关键代码注释覆盖Select选点、HuffmanTreeing建树、output输出等核心函数细致展示parent、lchild、rchild等指针域如何联动更新可帮助读者从代码层面理解哈夫曼树的存储结构与构建过程。同时编码环节对应哈夫曼编码的生成逻辑便于对照教材原理进行验证和调试也能为后续文件压缩、译码实现打下基础。资源仅含1个docx文档压缩包大小14KB内容集中便于快速查阅适合作为实验报告撰写、代码补全练习或期末复习的参考资料。当前已有9869人学习下载尤其适合数据结构课程中二叉树相关章节的配套巩固。1. 哈夫曼树卡在哪带权路径长度、双亲数组和两道头歌关卡处理数据压缩相关题目时哈夫曼树几乎是数据结构课程里第一个让人既兴奋又头秃的算法原理一听就懂代码一写就错。头歌平台的「构建哈夫曼树及编码」分成两关第一关要求补全Select和HuffmanTreeing第二关要求补全HuffmanCoding。真正难的不是“选择最小两个节点”这个思路而是parent字段的语义、从叶子到根回溯编码时cd数组的下标以及Select函数每次线性扫描带来的边界风险。这篇文章按头歌环境的 C 代码逐段拆把建树、编码、验证串起来讲既适合正在刷数据结构与算法题的学生也适合想回头理解静态三叉链表实现的工程师。2. 选最小节点Select 函数的时间复杂度与优先队列替代Select是整个哈夫曼树构建中调用最频繁的函数。它的任务是在HT[1..i]范围内找出parent 0且权值最小的两个节点把下标通过引用参数s1、s2返回。注意parent字段在这里既是父节点指针也是“是否已被合并进新树”的状态位。只要某个节点被选走并作为孩子挂到新节点下它的parent就会被置为非 0下次再扫描时就会被跳过。2.1 逐行拆解原版 Select头歌模板里的Select是线性扫描版本void Select(HuffmanTree HT, int i, int s1, int s2) { int j, k 1; while (HT[k].parent ! 0) k; s1 k; for (j 1; j i; j) { if (HT[j].parent 0 HT[j].weight HT[s1].weight) s1 j; } k 1; while (HT[k].parent ! 0 || k s1) k; s2 k; for (j 1; j i; j) { if (HT[j].parent 0 HT[j].weight HT[s2].weight j ! s1) s2 j; } }这个函数的第一个while是从头找到第一个parent 0的节点作为s1的初始值避免s1初始化为 0 导致比较出错第二个while则额外跳过k s1保证s2不会和s1重叠。两个for循环分别扫一遍数组所以单次Select的时间复杂度是O(i)整个建树过程要调用n - 1次总时间复杂度是O(n^2)。很多同学误写的点在于把条件写成了HT[j].weight HT[s1].weight HT[j].parent 0。虽然看起来只是交换判断顺序但在HT[s1].weight还没有被初始化时可能会拿一个parent非 0 的节点来更新s1。我一般建议把parent判断放在最前面这和判断顺序的短路执行也有关系能少踩一个坑。判断条件常见误写后果HT[j].parent 0 HT[j].weight HT[s1].weight先比较 weight 再判断 parent可能选中已合并节点HT[j].weight HT[s2].weight j ! s1忘记排除j s1s2与s1相同建树失败第一个while无边界保护用if而不是while初始候选可能不是parent 0边界条件也需要注意当i 1时第二个while中的k s1会让k一直加到 2超过数组有效范围。在实际建树调用中Select至少要到i 2才会被调用所以头歌测试数据不容易触发这个问题但如果你想封装成独立工具函数最好加一层防御判断。2.2 优先队列优化思路如果面试或工程里遇到 n 很大的情况线性扫描太慢可以用小顶堆来找最小两个节点。C 的priority_queue默认是大顶堆需要自定义比较器struct Cmp { bool operator()(const pairint, int a, const pairint, int b) const { return a.first b.first; // 小顶堆 } }; void SelectOpt(HuffmanTree HT, int i, int s1, int s2) { priority_queuepairint, int, vectorpairint, int, Cmp q; for (int j 1; j i; j) { if (HT[j].parent 0) { q.push({HT[j].weight, j}); } } auto t1 q.top(); q.pop(); auto t2 q.top(); q.pop(); s1 t1.second; s2 t2.second; }这种写法只是把一次扫描换成了堆构建单次复杂度反而变成O(i log i)对整体O(n^2)没有本质提升。真正要优化应该在初始化时把所有叶子节点丢进堆每次合并后把新节点入堆、把两个被选节点标记为“已合并”从堆中惰性删除这样总复杂度能降到O(n log n)。但头歌关卡并不要求性能优化我一般建议先把线性版本写对再考虑堆优化。因为Select函数本身并不难难的是parent状态管理和新节点下标计算换成堆之后还要维护“无效节点”的规避逻辑代码复杂度会明显上升。3. 静态三叉链表建树HuffmanTreeing 初始化、合并循环与参数表建树函数HuffmanTreeing用的是静态三叉链表一个长度为2*n的HTNode数组每个节点保存weight、parent、lchild、rchild四个字段。为什么不直接写二叉树结构体指针因为哈夫曼树是满二叉树节点数量固定为2*n - 1用数组下标代替指针可以减少内存碎片也方便Select通过下标快速访问。3.1 初始化两段循环第一段循环初始化前n个叶子节点权值来自w数组第二段循环初始化从n1到m的内部节点权值置 0。注意下标从 1 开始所以分配空间是m1下标 0 闲置不用。void HuffmanTreeing(HuffmanTree HT, int *w, int n) { if (n 1) return; int m 2 * n - 1; HT (HuffmanTree)malloc((m 1) * sizeof(HTNode)); int i; HuffmanTree p HT 1; for (i 1; i n; i, p) { p-weight w[i - 1]; p-parent 0; p-lchild 0; p-rchild 0; } for (; i m; i, p) { p-weight 0; p-parent 0; p-lchild 0; p-rchild 0; } for (i n 1; i m; i) { int s1, s2; Select(HT, i - 1, s1, s2); HT[s1].parent i; HT[s2].parent i; HT[i].lchild s1; HT[i].rchild s2; HT[i].weight HT[s1].weight HT[s2].weight; } }if (n 1) return;是必要的。哈夫曼树至少要两个叶子节点才有合并意义否则m 1后面的循环会直接跳过代码虽然没有语法错误但HT没有分配空间后续HuffmanCoding访问HT[i]会越界。所以这个防御必须在最前面。第二段初始化循环里p-weight 0和parent/lchild/rchild各字段都必须清零不能只写一个。否则后面Select扫描到未初始化节点时weight是随机值可能被误选为最小值导致整棵树结构错误。3.2 合并循环与 Select 的配合合并循环从i n 1开始到i m结束。每次调用Select(HT, i - 1, s1, s2)注意第二个参数是i - 1因为新节点HT[i]还没有初始化它的weight为 0如果让Select扫描到它一定会把它当作最小节点选出来。所以必须限定在已有的i-1个节点范围内找。找到s1和s2后执行四步把两个孩子节点的parent指向新节点i把新节点的左右孩子指针指向s1、s2最后把权值相加写入HT[i].weight。这四步顺序可以任意但必须都做缺一个都会导致输出异常。3.3 以 {7,5,2,4} 为例的最终数组表为了验证函数行为我用n 4, w {7, 5, 2, 4}走一遍第一次合并选到权值 2 和 4合并成第 5 号节点权值 6 第二次在剩余节点 7、5 和 5 号节点 6 中选 5 和 6合并成第 6 号节点权值 11 第三次选 7 和 6 号节点 11合并成根节点 7权值 18。最终数组中各节点状态如下节点编号weightparentlchildrchild1770025600325004450056634611725718016从这个表可以验证parent 0的只有根节点 7节点 5 和节点 6 虽然也是内部节点但它们同样被作为孩子挂到了上层。哈夫曼树中每个节点要么是叶子要么有两个孩子不存在只有一个孩子的内部节点所以最终parent字段也是一个很好的结构校验点。4. 从叶子到根的反向编码与从根出发的前缀编码实现哈夫曼编码要求每个叶子节点有唯一路径路径上的左分支记 0、右分支记 1。头歌第二关给的HuffmanCoding采用从叶子到根的反向方式代码更紧凑但下标处理很绕是出错高发区。4.1 原版逆向编码cd 数组为什么这么设计先看原版核心代码void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int n) { HC (HuffmanCode)malloc((n 1) * sizeof(char*)); char *cd (char*)malloc(n * sizeof(char)); cd[n - 1] \0; for (int i 1; i n; i) { int start n - 1; int c i; int f HT[i].parent; while (f ! 0) { if (HT[f].lchild c) cd[--start] 0; else cd[--start] 1; c f; f HT[f].parent; } HC[i] (char*)malloc((n - start) * sizeof(char)); strcpy(HC[i], cd[start]); } free(cd); }因为编码是从根到叶子的顺序而这里从叶子向上回溯得到的是逆序。解决办法是让start从n-1开始每次--start从后往前填充最后cd[start]到cd[n-1]这一段就是正序编码。例如深度为 3 的叶子第一次填在cd[2]第二次填在cd[1]第三次填在cd[0]cd[3]是结束符整个字符串长度为 3。这里有一个容易忽视的点为什么临时数组长度是n而不是n*2因为哈夫曼树最大深度不会超过n-1编码长度也不会超过n-1再加上结束符n个字符正好够用。如果某个叶子深度刚好是n-1最后一次--start会让start变成 0不会越界因为数组下标 0 到n-1。但如果叶子深度等于n才会越界这在哈夫曼树中不可能发生因为节点的父子关系是一棵树深度最大为n-1。4.2 正向递归编码的另一种写法如果你觉得逆向cd下标难懂可以用从根出发的 DFS 递归逻辑更直白void dfs(HuffmanTree HT, int root, char *path, int depth, HuffmanCode HC) { if (HT[root].lchild 0 HT[root].rchild 0) { HC[root] (char*)malloc(depth 1); strncpy(HC[root], path, depth); HC[root][depth] \0; return; } if (HT[root].lchild ! 0) { path[depth] 0; dfs(HT, HT[root].lchild, path, depth 1, HC); } if (HT[root].rchild ! 0) { path[depth] 1; dfs(HT, HT[root].rchild, path, depth 1, HC); } }调用时从根节点m 2*n-1开始传一个长度为n的临时字符数组。每次递归到叶子就把当前路径存下来。注意path只填0和1最后在叶子处手动补结束符。这种写法对调试更友好在printf打印路径时可以看到完整路径逐步生成的过程。4.3 易错点父节点要延迟到建树完成才编码HuffmanCoding必须在HuffmanTreeing整棵树构造完之后再调用。有的同学想在合并过程中同时生成编码认为可以在HT[i].lchild s1时立即给s1编码实际上是不行的。因为叶子节点可能很深路径上的内部节点此时还没有被合并完整的父链还没建立。只有等所有内部节点都构造完毕每个叶子的parent链才完整逆向回溯才能走到根。以{7,5,2,4}为例最终编码表如下叶子节点序号权值哈夫曼编码17025103211044111可以看到权值大的7编码最短权值小的2和4编码最长这正是哈夫曼编码“高频短码、低频长码”的特征。任何一个编码都不是另一个编码的前缀这也是HuffmanCoding能无歧义解码的前提。5. 用前缀校验函数检查编码表并顺手算出 WPL很多头歌作业只要求输出编码没有要求校验。但你自己验证时可以加一个小的前缀检查函数确定生成的编码表没有歧义同时计算带权路径长度 WPL。5.1 前缀冲突检查的小函数int isPrefixFree(HuffmanCode HC, int n) { for (int i 1; i n; i) { for (int j i 1; j n; j) { if (strncmp(HC[i], HC[j], strlen(HC[i])) 0 || strncmp(HC[j], HC[i], strlen(HC[j])) 0) { printf(prefix conflict: %s and %s\n, HC[i], HC[j]); return 0; } } } return 1; }检查原理很简单两个编码若互为前缀则短串和长串的前strlen(短串)个字符完全一致。strncmp只比较前n个字符所以用短串长度作为第三个参数。这个函数放在HuffmanCoding之后执行如果返回 0基本可以断定建树或编码逻辑出了问题。通常会和assert(isPrefixFree(HC, n))配合使用保证测试数据不通过时立即终止而不是带着错误编码继续跑。5.2 核验哈夫曼树带权路径长度的两种姿势计算 WPL 有两条路一是从树结构上累加每个叶子深度乘权值二是直接用编码长度代替深度。后者更简单因为strlen(HC[i]就是叶子到达根节点的路径长度也就是深度。int wpl 0; for (int i 1; i n; i) { wpl strlen(HC[i]) * w[i - 1]; } printf(WPL %d\n, wpl);仍以{7,5,2,4}为例WPL 为7*1 5*2 2*3 4*3 35。如果你想进一步检查建树函数是否正确也可以从根开始 DFS 累加每深入一层深度加 1遇到叶子把深度乘上该节点权值加起来。两种方式得到的结果必须一致。我自己的习惯是先用编码长度算一遍再用递归算一遍两者对不上时优先怀疑Select选出的节点不是真正最小的两个因为合并顺序错了会直接影响树的形态和叶子深度。把这几个校验函数塞进头歌题的main函数里提交前跑一遍基本能避免因为数组越界或编码顺序导致的分值丢失。本文还有配套的精品资源点击获取 哈夫曼树构建与编码详解：Select函数、静态三叉链表及WPL校验
简介面向数据结构课程实训的“构建哈夫曼树及编码”配套资源包适合正在完成头歌平台相关实验、希望掌握最优二叉树构造与哈夫曼编码原理的学习者。资源围绕两关任务展开第一关要求根据字符权值构造带权路径最短的哈夫曼树第二关则基于已建树生成前缀编码包内提供完整C语言实现与关键代码注释覆盖Select选点、HuffmanTreeing建树、output输出等核心函数细致展示parent、lchild、rchild等指针域如何联动更新可帮助读者从代码层面理解哈夫曼树的存储结构与构建过程。同时编码环节对应哈夫曼编码的生成逻辑便于对照教材原理进行验证和调试也能为后续文件压缩、译码实现打下基础。资源仅含1个docx文档压缩包大小14KB内容集中便于快速查阅适合作为实验报告撰写、代码补全练习或期末复习的参考资料。当前已有9869人学习下载尤其适合数据结构课程中二叉树相关章节的配套巩固。1. 哈夫曼树卡在哪带权路径长度、双亲数组和两道头歌关卡处理数据压缩相关题目时哈夫曼树几乎是数据结构课程里第一个让人既兴奋又头秃的算法原理一听就懂代码一写就错。头歌平台的「构建哈夫曼树及编码」分成两关第一关要求补全Select和HuffmanTreeing第二关要求补全HuffmanCoding。真正难的不是“选择最小两个节点”这个思路而是parent字段的语义、从叶子到根回溯编码时cd数组的下标以及Select函数每次线性扫描带来的边界风险。这篇文章按头歌环境的 C 代码逐段拆把建树、编码、验证串起来讲既适合正在刷数据结构与算法题的学生也适合想回头理解静态三叉链表实现的工程师。2. 选最小节点Select 函数的时间复杂度与优先队列替代Select是整个哈夫曼树构建中调用最频繁的函数。它的任务是在HT[1..i]范围内找出parent 0且权值最小的两个节点把下标通过引用参数s1、s2返回。注意parent字段在这里既是父节点指针也是“是否已被合并进新树”的状态位。只要某个节点被选走并作为孩子挂到新节点下它的parent就会被置为非 0下次再扫描时就会被跳过。2.1 逐行拆解原版 Select头歌模板里的Select是线性扫描版本void Select(HuffmanTree HT, int i, int s1, int s2) { int j, k 1; while (HT[k].parent ! 0) k; s1 k; for (j 1; j i; j) { if (HT[j].parent 0 HT[j].weight HT[s1].weight) s1 j; } k 1; while (HT[k].parent ! 0 || k s1) k; s2 k; for (j 1; j i; j) { if (HT[j].parent 0 HT[j].weight HT[s2].weight j ! s1) s2 j; } }这个函数的第一个while是从头找到第一个parent 0的节点作为s1的初始值避免s1初始化为 0 导致比较出错第二个while则额外跳过k s1保证s2不会和s1重叠。两个for循环分别扫一遍数组所以单次Select的时间复杂度是O(i)整个建树过程要调用n - 1次总时间复杂度是O(n^2)。很多同学误写的点在于把条件写成了HT[j].weight HT[s1].weight HT[j].parent 0。虽然看起来只是交换判断顺序但在HT[s1].weight还没有被初始化时可能会拿一个parent非 0 的节点来更新s1。我一般建议把parent判断放在最前面这和判断顺序的短路执行也有关系能少踩一个坑。判断条件常见误写后果HT[j].parent 0 HT[j].weight HT[s1].weight先比较 weight 再判断 parent可能选中已合并节点HT[j].weight HT[s2].weight j ! s1忘记排除j s1s2与s1相同建树失败第一个while无边界保护用if而不是while初始候选可能不是parent 0边界条件也需要注意当i 1时第二个while中的k s1会让k一直加到 2超过数组有效范围。在实际建树调用中Select至少要到i 2才会被调用所以头歌测试数据不容易触发这个问题但如果你想封装成独立工具函数最好加一层防御判断。2.2 优先队列优化思路如果面试或工程里遇到 n 很大的情况线性扫描太慢可以用小顶堆来找最小两个节点。C 的priority_queue默认是大顶堆需要自定义比较器struct Cmp { bool operator()(const pairint, int a, const pairint, int b) const { return a.first b.first; // 小顶堆 } }; void SelectOpt(HuffmanTree HT, int i, int s1, int s2) { priority_queuepairint, int, vectorpairint, int, Cmp q; for (int j 1; j i; j) { if (HT[j].parent 0) { q.push({HT[j].weight, j}); } } auto t1 q.top(); q.pop(); auto t2 q.top(); q.pop(); s1 t1.second; s2 t2.second; }这种写法只是把一次扫描换成了堆构建单次复杂度反而变成O(i log i)对整体O(n^2)没有本质提升。真正要优化应该在初始化时把所有叶子节点丢进堆每次合并后把新节点入堆、把两个被选节点标记为“已合并”从堆中惰性删除这样总复杂度能降到O(n log n)。但头歌关卡并不要求性能优化我一般建议先把线性版本写对再考虑堆优化。因为Select函数本身并不难难的是parent状态管理和新节点下标计算换成堆之后还要维护“无效节点”的规避逻辑代码复杂度会明显上升。3. 静态三叉链表建树HuffmanTreeing 初始化、合并循环与参数表建树函数HuffmanTreeing用的是静态三叉链表一个长度为2*n的HTNode数组每个节点保存weight、parent、lchild、rchild四个字段。为什么不直接写二叉树结构体指针因为哈夫曼树是满二叉树节点数量固定为2*n - 1用数组下标代替指针可以减少内存碎片也方便Select通过下标快速访问。3.1 初始化两段循环第一段循环初始化前n个叶子节点权值来自w数组第二段循环初始化从n1到m的内部节点权值置 0。注意下标从 1 开始所以分配空间是m1下标 0 闲置不用。void HuffmanTreeing(HuffmanTree HT, int *w, int n) { if (n 1) return; int m 2 * n - 1; HT (HuffmanTree)malloc((m 1) * sizeof(HTNode)); int i; HuffmanTree p HT 1; for (i 1; i n; i, p) { p-weight w[i - 1]; p-parent 0; p-lchild 0; p-rchild 0; } for (; i m; i, p) { p-weight 0; p-parent 0; p-lchild 0; p-rchild 0; } for (i n 1; i m; i) { int s1, s2; Select(HT, i - 1, s1, s2); HT[s1].parent i; HT[s2].parent i; HT[i].lchild s1; HT[i].rchild s2; HT[i].weight HT[s1].weight HT[s2].weight; } }if (n 1) return;是必要的。哈夫曼树至少要两个叶子节点才有合并意义否则m 1后面的循环会直接跳过代码虽然没有语法错误但HT没有分配空间后续HuffmanCoding访问HT[i]会越界。所以这个防御必须在最前面。第二段初始化循环里p-weight 0和parent/lchild/rchild各字段都必须清零不能只写一个。否则后面Select扫描到未初始化节点时weight是随机值可能被误选为最小值导致整棵树结构错误。3.2 合并循环与 Select 的配合合并循环从i n 1开始到i m结束。每次调用Select(HT, i - 1, s1, s2)注意第二个参数是i - 1因为新节点HT[i]还没有初始化它的weight为 0如果让Select扫描到它一定会把它当作最小节点选出来。所以必须限定在已有的i-1个节点范围内找。找到s1和s2后执行四步把两个孩子节点的parent指向新节点i把新节点的左右孩子指针指向s1、s2最后把权值相加写入HT[i].weight。这四步顺序可以任意但必须都做缺一个都会导致输出异常。3.3 以 {7,5,2,4} 为例的最终数组表为了验证函数行为我用n 4, w {7, 5, 2, 4}走一遍第一次合并选到权值 2 和 4合并成第 5 号节点权值 6 第二次在剩余节点 7、5 和 5 号节点 6 中选 5 和 6合并成第 6 号节点权值 11 第三次选 7 和 6 号节点 11合并成根节点 7权值 18。最终数组中各节点状态如下节点编号weightparentlchildrchild1770025600325004450056634611725718016从这个表可以验证parent 0的只有根节点 7节点 5 和节点 6 虽然也是内部节点但它们同样被作为孩子挂到了上层。哈夫曼树中每个节点要么是叶子要么有两个孩子不存在只有一个孩子的内部节点所以最终parent字段也是一个很好的结构校验点。4. 从叶子到根的反向编码与从根出发的前缀编码实现哈夫曼编码要求每个叶子节点有唯一路径路径上的左分支记 0、右分支记 1。头歌第二关给的HuffmanCoding采用从叶子到根的反向方式代码更紧凑但下标处理很绕是出错高发区。4.1 原版逆向编码cd 数组为什么这么设计先看原版核心代码void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int n) { HC (HuffmanCode)malloc((n 1) * sizeof(char*)); char *cd (char*)malloc(n * sizeof(char)); cd[n - 1] \0; for (int i 1; i n; i) { int start n - 1; int c i; int f HT[i].parent; while (f ! 0) { if (HT[f].lchild c) cd[--start] 0; else cd[--start] 1; c f; f HT[f].parent; } HC[i] (char*)malloc((n - start) * sizeof(char)); strcpy(HC[i], cd[start]); } free(cd); }因为编码是从根到叶子的顺序而这里从叶子向上回溯得到的是逆序。解决办法是让start从n-1开始每次--start从后往前填充最后cd[start]到cd[n-1]这一段就是正序编码。例如深度为 3 的叶子第一次填在cd[2]第二次填在cd[1]第三次填在cd[0]cd[3]是结束符整个字符串长度为 3。这里有一个容易忽视的点为什么临时数组长度是n而不是n*2因为哈夫曼树最大深度不会超过n-1编码长度也不会超过n-1再加上结束符n个字符正好够用。如果某个叶子深度刚好是n-1最后一次--start会让start变成 0不会越界因为数组下标 0 到n-1。但如果叶子深度等于n才会越界这在哈夫曼树中不可能发生因为节点的父子关系是一棵树深度最大为n-1。4.2 正向递归编码的另一种写法如果你觉得逆向cd下标难懂可以用从根出发的 DFS 递归逻辑更直白void dfs(HuffmanTree HT, int root, char *path, int depth, HuffmanCode HC) { if (HT[root].lchild 0 HT[root].rchild 0) { HC[root] (char*)malloc(depth 1); strncpy(HC[root], path, depth); HC[root][depth] \0; return; } if (HT[root].lchild ! 0) { path[depth] 0; dfs(HT, HT[root].lchild, path, depth 1, HC); } if (HT[root].rchild ! 0) { path[depth] 1; dfs(HT, HT[root].rchild, path, depth 1, HC); } }调用时从根节点m 2*n-1开始传一个长度为n的临时字符数组。每次递归到叶子就把当前路径存下来。注意path只填0和1最后在叶子处手动补结束符。这种写法对调试更友好在printf打印路径时可以看到完整路径逐步生成的过程。4.3 易错点父节点要延迟到建树完成才编码HuffmanCoding必须在HuffmanTreeing整棵树构造完之后再调用。有的同学想在合并过程中同时生成编码认为可以在HT[i].lchild s1时立即给s1编码实际上是不行的。因为叶子节点可能很深路径上的内部节点此时还没有被合并完整的父链还没建立。只有等所有内部节点都构造完毕每个叶子的parent链才完整逆向回溯才能走到根。以{7,5,2,4}为例最终编码表如下叶子节点序号权值哈夫曼编码17025103211044111可以看到权值大的7编码最短权值小的2和4编码最长这正是哈夫曼编码“高频短码、低频长码”的特征。任何一个编码都不是另一个编码的前缀这也是HuffmanCoding能无歧义解码的前提。5. 用前缀校验函数检查编码表并顺手算出 WPL很多头歌作业只要求输出编码没有要求校验。但你自己验证时可以加一个小的前缀检查函数确定生成的编码表没有歧义同时计算带权路径长度 WPL。5.1 前缀冲突检查的小函数int isPrefixFree(HuffmanCode HC, int n) { for (int i 1; i n; i) { for (int j i 1; j n; j) { if (strncmp(HC[i], HC[j], strlen(HC[i])) 0 || strncmp(HC[j], HC[i], strlen(HC[j])) 0) { printf(prefix conflict: %s and %s\n, HC[i], HC[j]); return 0; } } } return 1; }检查原理很简单两个编码若互为前缀则短串和长串的前strlen(短串)个字符完全一致。strncmp只比较前n个字符所以用短串长度作为第三个参数。这个函数放在HuffmanCoding之后执行如果返回 0基本可以断定建树或编码逻辑出了问题。通常会和assert(isPrefixFree(HC, n))配合使用保证测试数据不通过时立即终止而不是带着错误编码继续跑。5.2 核验哈夫曼树带权路径长度的两种姿势计算 WPL 有两条路一是从树结构上累加每个叶子深度乘权值二是直接用编码长度代替深度。后者更简单因为strlen(HC[i]就是叶子到达根节点的路径长度也就是深度。int wpl 0; for (int i 1; i n; i) { wpl strlen(HC[i]) * w[i - 1]; } printf(WPL %d\n, wpl);仍以{7,5,2,4}为例WPL 为7*1 5*2 2*3 4*3 35。如果你想进一步检查建树函数是否正确也可以从根开始 DFS 累加每深入一层深度加 1遇到叶子把深度乘上该节点权值加起来。两种方式得到的结果必须一致。我自己的习惯是先用编码长度算一遍再用递归算一遍两者对不上时优先怀疑Select选出的节点不是真正最小的两个因为合并顺序错了会直接影响树的形态和叶子深度。把这几个校验函数塞进头歌题的main函数里提交前跑一遍基本能避免因为数组越界或编码顺序导致的分值丢失。本文还有配套的精品资源点击获取