性质1在二叉树的第i层上至多有2i-1个结点(i≥1)用归纳法证明归纳基：i=1层时，只有一个根结点：2i-1 = 20 = 1 ;归纳假设假设对所有的i，1≤j<i，命题成立;归纳证明：二叉树上每个结点至多有两棵子树则第i层的结点数=2i-2×2= 2i-1
性 质 1 ： 在二叉树的第 i 层上至多有 2 i-1个结点。 (i≥1) 用归纳法证明： 归纳基： 归纳假设： 归纳证明： i = 1 层时，只有一个根结点： 2 i-1 = 2 0 = 1； 假设对所有的 j，1≤ j i，命题成立； 二叉树上每个结点至多有两棵子树， 则第 i 层的结点数 = 2 i-2 2 = 2 i-1
性质2：深度为 k的二叉树上至多含 2k-1个结点（k≥1）。证明：基于上一条性质，深度为k的二叉树上的结点数至多为20+21+ ......+2k-1 = 2k-1
性质 2 ： 深度为 k 的二叉树上至多含 2 k -1 个结点（k≥1）。 证明： 基于上一条性质，深度为 k 的二叉 树上的结点数至多为 2 0+21+ +2k-1 = 2k -1
性质3：对任何一棵二叉树，若它含有n。个叶子结点、n，个度为 2 的结点，则必存在关系式 : n= n,+l证明：设二叉树上结点总数 n= no+ ni +n2又二叉树上分支总数b=nj+2n2而 b = n-l = no + ni + n2- I由此，no=n2+ 1
性质 3 ： 对任何一棵二叉树，若它含有n0 个叶 子结点、n2 个度为 2 的结点，则必存在 关系式：n0 = n2+1。 证明： 设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1
两类特殊的二叉树：32满二叉树：指的是5746深度为k且含有2k-1个结点的二叉树9 10 11 12 13 14 158完全二叉树：树中所含的 n个结点b和满二叉树中编号fdg为 1 至 n 的结点一h一对应
两类特殊的二叉树： 满二叉树：指的是 深度为k且含有2 k -1个 结点的二叉树。 完全二叉树：树 中所含的 n 个结点 和满二叉树中编号 为 1 至 n 的结点一 一对应。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 a b c d e f g h i j
性质4具有 n 个结点的完全二叉树的深度为 / log2n /+1 。证明：设完全二叉树的深度为kF 2k-l< n<2k则根据第二条性质得即 k-1≤ log2n<k因为 k只能是整数，因此，k=[log2n/+1
性 质 4 ： 具有 n 个结点的完全二叉树的深度 为 log2n +1 。 证明： 设完全二叉树的深度为 k 则根据第二条性质得 2 k-1≤ n < 2 k 即 k-1 ≤ log2 n < k 因为 k 只能是整数，因此， k =log2n + 1