若一棵深度为 5 的完全二叉树有 30 个叶子结点,则此完全二叉树的结点总数最少为多少?
答案解析
核心考点说明:本题考察完全二叉树的性质,特别是结点数和叶子结点数的关系,以及完全二叉树深度和结点数的关系。难点在于如何利用已知条件计算最小值。
解题思路分析:深度为5的完全二叉树,最多有2^5 - 1 = 31个结点。要使得结点数最少,应该尽可能少的包含非叶子结点。考虑到叶子结点为30,那么倒数第二层至多有30/2 = 15个结点(如果奇数则向上取整)。由于是完全二叉树,倒数第二层必须填满或左边填满,才能使结点总数最少。深度为4的满二叉树的节点数为2^4 -1 = 15个。要满足30个叶子节点,倒数第二层节点数不能少于ceil(30/2)=15个。为了使得总数最少,那么倒数第二层尽量满,此时倒数第二层的结点为15,倒数第三层节点数为15/2 = 8(向上取整)或者7(如果倒数第二层有14个结点,最少情况)。依此类推,倒数第4层至少有4 个,倒数第5层至少有1个。所以,总节点数 = 1+4+8+15+30 = 58。
每个选项的详细分析:
- A. 选项58:根据推理过程,此选项正确。
- B. 选项60:此选项偏大,是错误地将倒数第二层填满导致的错误。
- C. 选项61:此选项偏大,是考虑了叶子结点满二叉树的情况导致的错误。
- D. 选项62:此选项偏大,是错误的认为最后一层必须全部填满。
易错点提醒:容易错误认为完全二叉树的每一层都必须填满,或者叶子节点是上一层节点数的2倍。需要注意完全二叉树的定义和特性,特别是最后一层。
正确答案的关键依据:深度为5的完全二叉树,最少结点数的情况,在倒数第二层尽可能多,且满足有30个叶子节点。
正确答案:A