问题 单项选择题

设根结点的层次为0,则高度为k的二叉树的最大结点数为
A)2k
B)2k-1
C)2k+1
D)2k+1-1

答案

参考答案:D

解析:
【解析】可用数学归纳法证明二叉树第k层的结点数目为2k
  归纳基础:k=0时,只有一个根结点,命题成立。k=1时,最多有2个结点,命题也成立。
  归纳假设:假设k=1时命题成立。
  归纳步骤:高度为k-1的二叉树最大结点数为2k-1,由于二叉树的每个结点最多有2个孩子,第 k层的结点数目最大为第k-l的最大结点数的2倍,即2×2k-1=2k命题成立。
  在有相同深度的二叉树中,仅当每一层都含有最大结点数时二叉树中结点数最多,故根结点的层次为0,则高度为k的二叉树的最大结点数为:20+21+…+2k=2k+1-1。

多项选择题
问答题