单选题
设n
0
为哈夫曼树的叶子结点数目,则该哈夫曼树共有
(51)
个结点。
A、
n
0
+1
B、
2n
0
-1
C、
2n
0
D、
3n
0
【正确答案】
B
【答案解析】
[解析] 设共有n个结点,则有n=n
0
+n
1
+n
2
(其中n
1
为有一个孩子的结点,n
2
为有两个孩子的结点),n
1
=0,所以有n=n
0
+n
2
;所有结点的入度和为n-1,出度和为2n
2
,所以有n-1=2n
2
。将n=n
0
+n
2
和n-1=2n
2
联合解之得n=2n
0
-1。
提交答案
关闭