假设高度为h的二叉树上只有度为0 和度为2的结点,则此类二叉树中所包含的结点数至少为_____。A. 2hB. 2h-1C. 2h+1D. h+1

考查要点：本题主要考查二叉树的基本性质，特别是严格二叉树（所有非叶子结点度数为2）的结点数与高度的关系。

解题核心思路：

1. 严格二叉树的定义：每个非叶子结点必须有两个子结点。
2. 高度为h的树中，最长路径的边数为h-1，对应层数为h。
3. 最小结点数构造：通过递归思想，构造一条最长路径，使得每层仅新增一个必要结点，其余子树尽可能矮小，从而推导出公式。

破题关键点：

• 理解严格二叉树的结构特点，即每层非叶子结点必须分叉。
• 通过递推关系发现，高度为h的最小结点数为2h-1。

构造严格二叉树的最小结点数

1. 高度为1：只有根结点，结点数为1，满足2×1−1=1。
2. 高度为2：根结点有两个子结点，总结点数为3，满足2×2−1=3。
3. 高度为h：
   • 根结点有两个子树，其中一棵子树高度为h−1，另一棵为叶子。
   • 递推公式：总结点数 = 1（根） + 1（叶子子树） + (2×(h−1)−1)，化简得2h−1。

递推验证

• 假设高度为h−1时成立：子树结点数为2(h−1)−1。
• 总结点数：1（根） + 1（叶子） + [2(h−1)−1] = 2h−1。
• 归纳得证：公式对所有h成立。