6.2.2 二叉树的几个特性 　一、在二叉树的第 i 层上至多有 2i-1 个结点(i≥1)。 　　利用归纳法容易证得此结论。		在进一步讨论二叉树的存储结构和操作之前，我们需要先了解二叉树的一些重要特性。 证明： 　归 纳 基：i=1 时，只有一个根结点。显然 2i-1=20=1 是对的。 　归纳假设：设对所有的j(1≤j<i)，命题成立，即第j层上至多有 2j-1 个结点。 　归纳证明：由归纳假设"第 i-1 层上至多有 2i-2 个结点"，又二叉树的每个结点的度至多为2，则第 i 层上的最大结点数为第 i-1 层上最大结点数的2倍，即 2×2i-2=2i-1。 证毕。
	二、深度为k的二叉树中至多含有 2k-1 个结点，(k≥1)。		证明： 　　由特性一可推出，深度为k的二叉树上最大结点数为
	三、对任何一棵二叉树 T，如果其终端结点数为，度为2的结点数为，则 　　　 = + 1		证明： 　　由于二叉树中只有三种结点，假设n1为二叉树 T 中度为1的结点数，则二叉树中结点总数为 　　 = + + 　　　　 ① 　　再看二叉树中的分支数目。除了根结点外，其余结点都有一个分支进入，假设 B 为分支数，则 n=B+1。从另一角度看，这些分支是由度为1或2的结点射出的，所以又有 　　　B = + 2 　　即 = + 2 + 1 　　　　 ② 　　综合以上①和②两个等式便可得到 　　　 = + 1