若一棵哈夫曼（Huffman）树共有9个顶点,则其叶子结点的个数为（ ）。A.4B.5C.6D.7
若一棵哈夫曼（Huffman）树共有9个顶点,则其叶子结点的个数为（ ）。
A.4
B.5
C.6
D.7
B.5
C.6
D.7
参考解析
解析：哈夫曼首先给出了根据给定的叶子数目及其权值构造最优二叉树的方法，根据这种方法构造出来的二叉树称为哈夫曼树。具体过程如下：假设有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.一般在哈夫曼树中，权值越大的叶子离根结点越近B.哈夫曼树中没有度数为1的分支结点C.若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点D.若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树
下列关于哈夫曼树的叙述错误的是A．一棵哈夫曼树是带权路径长度最短的二叉树B．一棵哈夫曼树中叶结点的个数比非叶结点的个数大1C．一棵哈夫曼树结点的度要么是0，要么是2D．哈夫曼树的根结点的权值等于各个叶子结点的权值之和
填空题一棵有n个叶子结点的哈夫曼树共有（）个结点