二叉树 性质1 口若二叉树的层次从1开始,则在二叉树的第i(论1) 层最多有21个结点。 口证明:(用数学归纳法) i=1时,根结点只有1个,21=20=1; >若设i=k时性质成立,即该层最多有2k1个结点, 则当i=k+1时,由于第k层每个结点最多可有2个 子女,第k+1层最多结点个数可有2k1=2k个,故 性质成立。二叉树 ◼ 性质1  若二叉树的层次从1 开始, 则在二叉树的第i ( i≥1) 层最多有 2 i-1 个结点。  证明：(用数学归纳法) ➢ i = 1时，根结点只有1个，2 1-1 = 20 =1； ➢ 若设 i = k 时性质成立，即该层最多有2 k-1 个结点， 则当 i = k+1 时，由于第k 层每个结点最多可有2 个 子女，第 k+1 层最多结点个数可有2*2k-1 = 2k 个，故 性质成立。 7