62二叉树 ●二叉树的性质 1、二叉树第层上的结点数目最多为21(i≥0) 归纳法证明 归纳基础:i=1时,有21=20=1。 归纳假设:假设对所有的j(1j<)命题成立,即第层上至多 有21个结点,证明=时命题成立 归纳步骤:根据归纳假设,第ⅰ-1层上至多有22个结点,由于 二叉树的每个结点至多有两个孩子,故第层上的 结点至多是第层上的最大结点数的2倍,=时 该层上至多有2*22=21个结点,故命题成立。6.2 二叉树 ⚫ 二叉树的性质 1、二叉树第i层上的结点数目最多为2 i-1 (i≥0)。 归纳法证明： 归纳基础：i=1时，有2 i-1=20=1。 归纳假设：假设对所有的j(1≤j<i)命题成立，即第j层上至多 有2 j-1个结点，证明j=i时命题成立。 归纳步骤：根据归纳假设，第i-1层上至多有2 i-2个结点，由于 二叉树的每个结点至多有两个孩子，故第i层上的 结点至多是第i层上的最大结点数的2倍，即j=i时 该层上至多有2*2i-2=2i-1个结点，故命题成立