单选题
某棵树只有度为3的结点和叶子结点,其中度为3的结点有8个,则该树中的叶子结点数为______。
【正确答案】
C
【答案解析】[解析] 树是一种简单的非线性结构,直观地来看,树是以分支关系定义的层次结构。在树结构中,一个结点所拥有的后件个数称为该结点的度,所有结点中最大的度称为树的度。由于只有度为3的结点和叶子结点,可知最后1层都为叶子结点,倒数第2层一部分结点度为3,一部分为叶子结点,其余结点的度均为3。计算度为3的结点总数(3
3-1
-1)/2<84-1-1)/2可知,树共有4层,前两层有度为3的结点(3
3-1
-1)/2=4个,第3层有3
2
=9个结点,其中4个是度为3的结点,5个是叶子结点,所以该树中的叶子结点数为4×3+5=17。故选C。