哈夫曼树子总比特数计算方法及编码100对应值疑问

首先明确子总比特数的定义：它是指以对应节点为根的子树的编码总代价，计算方式为该子树所有叶子节点的「频率 × 编码长度」之和。

针对你的疑问逐个解释： #

• 编码0对应叶子节点A：A的频率是15，编码长度为1（从根节点到A仅需走1步），因此总比特数为 15 × 1 = 15，与表中结果一致。
• 编码100对应叶子节点B：B的频率是7，编码长度为3（从根节点到B需要走3步：根→1→10→100），因此总比特数为 7 × 3 = 21，这就是表中数值的由来。你之前错误地将A的频率加入计算，但A并不属于B的子树（B是独立叶子节点，其子树仅包含自身），因此无需累加A的数值。

额外补充内部节点的子总比特数计算： #

如果是内部节点（比如编码10对应的节点），它的子总比特数等于其两个子节点的子总比特数之和。例如假设10的另一个子节点是101（频率为x，编码长度3，子总比特数为x×3），那么10的子总比特数就是 21 + x×3。

内容的提问来源于stack exchange，提问作者Cao Dingjie