若一棵哈夫曼（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个结点。
你可能感兴趣的试题
-
- A.V(S2)和P(S4)
- B.P(S2)和V(S4)
- C.P(S2)和P(S4)
- D.V(S2)和V(S4)
- 查看答案
-
- A.V（S1）P（S2）和V（S3）
- B.P（S1）V（S2）和V（S3）
- C.V（S1）V（S2）和V（S3）
- D.P（S1）P（S2）和V（S3）
- 查看答案
-
- A.P（S4）和V（S4）V（S5）
- B.V（S5）和P（S4）P（S5）
- C.V（S3）和V（S4）V（S5）
- D.P（S3）和P（S4）V（P5）
- 查看答案
-
- A.P(S3)和V(S4)V(S5)
- B.V(S3)和P(S4)P(S5)
- C.P(S3)和P(S4)P(S5)
- D.V(S3)和V(S4)V(S5)
- 查看答案
-
- A.P（S2）和P（S4）
- B.P（S2）和V（S4）
- C.V（S2）和P（S4）
- D.V（S2）和V（S4）
- 查看答案