设根结点的层次为0,则高度为k的二叉树的最大结点数为A.2kB.2k－1C.2k＋1D.2k＋1－1

Question

设根结点的层次为0，则高度为k的二叉树的最大结点数为

A．2k

B．2k-1

C．2k+1

D．2k+1-1

Answer 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。