题9

题9

题目

Q:若度为 的哈夫曼树中,叶结点个数为 ,则非叶结点的个数为 ( ).
A.
B.
C.
D.

分析

A:n个叶结点，非叶结点总数就有n-1个，题1里面有这个结论。
同时，只有度为2，和度为0的，两种结点
这个题居然不选A，和题1好像是矛盾的
不矛盾，突然发觉，只要把度代入成2，那么就是对的，哈夫曼的度是什么概念，哈夫曼的度如果是m，那哈夫曼树岂不是就不是二叉树了？

解

C
一棵度为 的哈夫曼树应只有度为 0 和 的结点,设度为 的结点有 个,度为 0 的结点有 个,又设结点总数为 。
因有 个结点的哈夫曼树有 条分支,则 ,整理得 。