若度为 m 的哈夫曼树中，叶结点数为 n，则非叶结点的个数为（ ）。

A. n−1 B. ⌊n/m⌋−1 C. (n−1)/(m−1) D. ⌈n/(m−1)⌉−1

[tag_link]

正确答案：C

推导

m 叉哈夫曼树的结点度只能为 0 或 m。设非叶结点数为 i，由边数 mi=n+i−1 得 i=(n−1)/(m−1)，故选 C。

易错点

该式要求叶数满足可构造条件；否则构造前应补权值 0 的虚叶，使 (n−1) 能被 (m−1) 整除。