题5

题5

题目

Q:度为 4 、高度为 的树,( ).
A. 至少有 个结点
B. 至多有 个结点
C. 至多有 个结点
D. 至少有 个结点

分析

A:有点不太能理解这个题目是在说什么意思，和题4对比起来看
度数+1应该是节点数，也就是这个数有五个节点
高度至少为2，最多是五

解

A
要使得度为 4 、高度为 的树的总结点数最少,需要满足以下两个条件:
① 至少有一个结点有 4 个分支。
② 每层的结点数目尽可能少。
情况类似下图所示的树,结点个数为 。

要使得度为 4、高度为 的树的总结点数最多,应使每个非叶结点的度均为 4,即为满树, 总结点个数最多为 。
对于上面的两题, 应画出草图来求解, 就能一目了然。