itgle.com
若一棵Huffman树共有9个节点，则其叶节点的个数为______。A．4B．5C．6D．7
题目
若一棵Huffman树共有9个节点，则其叶节点的个数为______。
A．4
B．5
C．6
D．7
相似考题
参考答案和解析
正确答案：B
解析：由Huffman树的构造过程可知，Huffman树中没有度为1的点，只有度为0(叶节点)和度为2的节点，设度为2的节点数为n2，度为0的节点数为n0，因此树共有9个节点，所以此树的总度数为n-1=8，所以有：树的总度数的等量关系：8=2×n2；树的总节点数的等量关系：9=n2+n0由此可解得n2=4，n0=5。故选B。
解析：由Huffman树的构造过程可知，Huffman树中没有度为1的点，只有度为0(叶节点)和度为2的节点，设度为2的节点数为n2，度为0的节点数为n0，因此树共有9个节点，所以此树的总度数为n-1=8，所以有：树的总度数的等量关系：8=2×n2；树的总节点数的等量关系：9=n2+n0由此可解得n2=4，n0=5。故选B。
更多“若一棵Huffman树共有9个节点,则其叶节点的个数为______。A.4B.5C.6D.7 ”相关问题
-
第1题：
若一棵哈夫曼(Huffman)树共有9个顶点，则其叶子节点的个数为(15)。
A．4
B．5
C．6
D．7
正确答案：B
解析：哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，根据这种方法构造出来的二叉树称为哈夫曼树。假设有n个权值，则构造出的哈夫曼树有n个叶子节点。N个权值分别设为w1，w2，…，wn，则哈夫曼树的构造规则如下。第一步：将w1，w2，…，wn看成是有n棵树的森林；第二步：在森林中选出两个根节点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根节点权值为其左右子树根节点权值之和；第三步：从森林中删除选取的两棵树，并将新树加入森林：第四步：重复第二步和第三步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。从以上构造过程可知，哈夫曼树是严格的二叉树，没有度数为1的分支节点。n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新节点，最后求得的哈夫曼树中共有2n-1个节点。 -
第2题：
若一棵哈夫曼（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个结点。 -
第3题：
若一棵度为4的树中度为2、3、4的节点个数分别为3、2、2，总节点个数为25，则该树中度为1的节点个数是多少？
节点总数 n=n 0 +n 1 +n 2 +n 3 +n 4 ,又由于除根节点外,每个节点都对应一个分支,所以总的分支数等于 n - 1 。而度为 i ( 0 ≤ i ≤ 4 )的节点的分支数为 i ,所以有:总分支数 =n - 1=0×n 0 +1×n 1 +2×n 2 +3×n 3 +4×n 4 。综合两式得: n 0 =n 2 +2n 3 +3n 4 +1=3+2×2+3×2=14 ,则 n=n 0 +n 1 +n 2 +n 3 +n 4 , n1=n - n 0 - n 2 - n 3 - n 4 =25 - 14 - 3 - 2 - 2=4 ,所以该树中度为 1 的节点个数是 4 。 -
第4题：
若一棵哈夫曼(Huffman)树共有9个顶点，则其叶子结点的个数为(34)。
A．4
B．5
C．6
D．7
正确答案：B
解析：哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，根据这种方法构造出来的二叉树称为哈夫曼树。具体过程如下所述。假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1，w2，…，wn，则哈夫曼树的构造规则为:(1)w1，w2，…，wn看成是有n棵树的森林(每棵树仅有一个结点)：(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林；(4)重复第(2)和(3)步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。从以上构造过程可知，哈夫曼树是严格的二叉树，没有度数为1的分支结点。n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点，最终求得的哈夫曼树中共有2n-1个结点。 -
第5题：
若一棵度为4的树中度为1、2、3、4的节点个数分别为4、3、2、2，则该树的总节点个数是多少？
节点总数 n=n 0 +n 1 +n 2 +n 3 +n 4 ,又由于除根节点外,每个节点都对应一个分支,所以总的分支数等于 n - 1 。而度为 i ( 0 ≤ i ≤ 4 )的节点的分支数为 i ,所以有:总分支数 =n - 1=0×n 0 +1×n 1 +2×n 2 +3×n 3 +4×n 4 。综合两式得: n 0 =n 2 +2n 3 +3n 4 +1=3+2×2+3×2=14 ,则 n=n 0 +n 1 +n 2 +n 3 +n 4 , n1=n - n 0 - n 2 - n 3 - n 4 =25 - 14 - 3 - 2 - 2=4 ,所以该树中度为 1 的节点个数是 4 。