题26

题26

题目

Q:【2012 统考真题】若平衡二叉树的高度为 6 , 且所有非叶结点的平衡因子均为 1 , 则该平衡二又树的结点总数为 ( ).
A. 12
B. 20
C. 32
D. 33

分析

A:和题15对比，平衡二叉树的结点总数满足递推式 ,递推式在题12有提到过

解

B
所有非叶结点的平衡因子均为 1 , 即平衡二叉树满足平衡的最少结点情况, 如下图所示。
对于高度为 、左右子树的高度分别为 和 、所有非叶结点的平衡因子均为 1 的平衡二叉树, 计算总结点数的公式为

画图法: 先画出 和 ; 然后新建一个根结点,连接 构成 ; 新建一个根结点,连接 构成 直到画出 ,可知 的结点数为 20 。
排除法: 对于 ,高度为 6、结点数为 12 的树怎么也无法达到平衡。对于 ,结点较多时, 考虑较极端的情形, 即第 6 层只有最左叶子的完全二叉树刚好有 32 个结点, 虽然满足平衡的条件, 但显然再删去部分结点依然不影响平衡, 不是最少结点的情况。同理 D 错误。