若一棵哈夫曼(Huffman)树共有9个顶点,则其叶子结点的个数为( ) 。
- A.4
- B.5
- C.6
- D.7
正确答案及解析
正确答案
B
解析
哈夫曼首先给出了根据给定的叶子数目及其权值构造最优二叉树的方法，根据这种方法构造出来的二叉树称为哈夫曼树。具体过程如下：假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1，w2，...，wn，则哈夫曼树的构造规则为：（1）将w1，w2，...，wn看作有n棵树的森林（每棵树仅有一个结点）；（2）在森林中选出2个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；（3）从森林中删除选取的2棵树，并将新树加入森林；（4）重复第（2）和（3）步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。从以上构造过程可知，哈夫曼树是严格的二叉树，没有度数为1的分支结点。n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点，最终求得的哈夫曼树中共有2n-1个结点。
