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

admin2006-10-10  54

问题 设根结点的层次为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。
转载请注明原文地址:https://kaotiyun.com/show/rO0Z777K
0

相关试题推荐
最新回复(0)