单选题
已知二叉树有50个叶子结点,则该二叉树的总结点数至少是______。
A、
96
B、
99
C、
100
D、
113
【正确答案】
B
【答案解析】
任何一棵二叉树叶子结点数等于度为2的结点的个数加1,因此此题中,度为2的结点的个数为50-1=49。二叉树中的结点的度只能为0、1或2,如果该二叉树中没有度为1的结点,显然总结点数最小。那么究竟存不存在这样一棵树呢?当然存在,比如将50个结点赋以权值,构成一棵哈夫曼树,我们知道,哈夫曼树是正则二叉树(即没有度为1的结点)。因此总结点数至少为50+49=99。
提交答案
关闭