第 5 次作业 · 树与哈夫曼编码

82，对应 B。由边数等于各结点度数之和，又等于结点总数减一，可解得叶结点数。

$m=n-1$，$n=2^h-1$。源答案对应 D。

每个分支结点的度都为 1，对应 D。

树的深度，对应 A。

左孩子指针为空的结点数，对应 C。

无法确定，对应 D。只有完全二叉树按层存储时才直接使用 $2i$。

- + A * B C / D E，对应 D。

11,10,001,101,0001，对应 B；10 是 101 的前缀。

55，对应 B。

21，对应 B。严格二叉树满足总结点数为 $2n_0-1$。

$\lfloor i/2\rfloor$、$2i$、$2i+1$，编号存在时成立。

$k^{i-1}$。

1024。

HIDJEBFGCA。

共 $2n$ 个指针域，其中 $n-1$ 个链接孩子，$n+1$ 个为空。

DCBFGEA。

$\lfloor\log_2 i\rfloor=\lfloor\log_2 j\rfloor$。

+-*ABCD 的值为 7；-*A+BCD 的值为 9。

3 次：依次比较 54、73、62。

69。

提交建立二叉树并递归遍历；遇到左右孩子都为空的结点时输出，从而只访问叶结点。

提交把操作数放在叶结点、运算符放在分支结点，递归求左右子表达式并在根处计算。它与上次后缀栈版本解决同一类问题，但保存的是表达式结构。

提交以单词为关键字建立二叉搜索树；相同单词增加计数，小于当前结点进入左子树，大于则进入右子树。中序遍历可按字典序输出。

lab_tree2 保存 huffman2student.c、输入和输出。提交统计字符频率、构造哈夫曼树并生成编码。源目录只有学生版实现，不另称为教师标准答案。

提交用树形或优先关系组织服务数据并计算优化结果。独立题面未保存，无法确认全部业务约束，故不从代码反推原题。