若一棵哈夫曼树共有9个顶点,则其叶子结点的个数为(69)。A.4B.5C.6D.7

Question

若一棵哈夫曼树共有9个顶点，则其叶子结点的个数为(69)。

A．4

B．5

C．6

D．7

Answer 1

正确答案：B
解析：哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，根据这种方法构造出来的二叉树称为哈夫曼树。具体过程请读者参考本节练习10的分析。从哈夫曼树的构造过程可知，哈夫曼树是严格的二叉树(即没有度数为1的分支结点)。设哈夫曼树的0度结点(即叶子结点)个数为n0，2度结点个数为n2，则哈夫曼树的总结点数n＝n0+n2。又因为对任何一棵二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n0＝n2+1。所以n=n2+1+n2。即9=n2+1+n2，故n2＝4，n0=5。