★二叉树性质 令性质1:在二叉树的第层上至多有2个结点(i≥1) 证明:用归纳法证明之 ①i=1时,只有一个根结点21=2=1是对的 ②假设对所有j(1j<i)命题成立,即第层上至多有2个结点 那么,第-1层至多有2-2个结点 又二叉树每个结点的度至多为2 第层上最大结点数是第i-1层的2倍,即2.22=2-1 故命题得证 令性质2:深度为k的二叉树至多有2-1个结点(K1) 证明:由性质1,可得深度为k的二叉树最大结点数是 ∑(第层的最大结点数)=∑27=2-1二叉树性质 ❖性质1： 2 ( 1) 1  − i i 在二叉树的第 层上至多有 i 个结点 证明：用归纳法证明之 i=1时，只有一个根结点， 是对的 假设对所有j(1j<i)命题成立，即第j层上至多有 个结点 那么，第i-1层至多有 个结点 又二叉树每个结点的度至多为2  第i层上最大结点数是第i-1层的2倍，即 故命题得证 2 2 1 1 0 = = i− 1 2 j− 2 2 i− 2 1 2 2 2 − −  = i i ❖性质2：深度为k的二叉树至多有 2 −1 个结点(k1) k 证明：由性质1，可得深度为k 的二叉树最大结点数是 ( ) 2 2 1 1 1 1  =  = − = = − k k i k i i 第i层的最大结点数