性质 性质1在二叉树的第i层上至多有2-1 个结点。(≥1)[证明用归纳法 证明:当i=1时,只有根结点,211=20=1 假设对所有j,」1,命题成立,即第层 上至多有2个结点。 由归纳假设第i-1层上至多有2-2个结点。 由于二又树的每个结点的度至多为2,故在 第i层上的最大结点数为第-1层上的最大结 点数的2倍,即2*2-2=2
性质1 在二叉树的第 i 层上至多有 2 i －1 个结点。(i 1) [证明用归纳法] 证明：当i=1时，只有根结点，2 i-1=2 0=1。 假设对所有j，i>j1，命题成立，即第j层 上至多有2 j-1 个结点。 由归纳假设第i-1 层上至多有 2 i －2个结点。 由于二叉树的每个结点的度至多为2，故在 第i层上的最大结点数为第i-1层上的最大结 点数的2倍，即2* 2i －2= 2 i-1。 性质
性质2深度为k的二叉树至多有2k-1 个结点(k≥1) 证明:由性质1可见,深度为k的二叉树的 最大结点数为 (第读上的最大结点数) =∑21=20+21++2k1=2k-1
性质2 深度为 k 的二叉树至多有 2 k-1 个结点(k 1)。 证明：由性质1可见，深度为k的二叉树的 最大结点数为 = − k i i 1 1 2 ＝2 0 + 21 + … + 2 k-1 = 2 k-1 = k i i 1 (第 层上的最大结点数） ＝
性质3对任何一棵二叉树T,如果其叶 结点数为n,度为2的结点数为n2则n=n2 +1 证明:若度为1的结点有n1个,总结点个 数为n,总边数为e,则根据二叉树的定 义 n=n0+n1+n2e=2n2+n1=n-1 因此,有2n2+n Ino tn,t n 2 2 0 n+1
性质3 对任何一棵二叉树T, 如果其叶 结点数为 n0 , 度为2的结点数为 n2 ,则n0＝n2 ＋1. 证明：若度为1的结点有 n1 个，总结点个 数为 n，总边数为 e，则根据二叉树的定 义， n = n0 + n1 + n2 e = 2n2 + n1 = n - 1 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1
两种特殊形态的二叉树 定义1满二叉树( Full Binary Tree) 一棵深度为k且有2k-1个结点的二叉树称为 满二叉树。 8)9 满二叉树
定义1 满二叉树 (Full Binary Tree) 一棵深度为k且有2 k -1个结点的二叉树称为 满二叉树。 两种特殊形态的二叉树 6 2 1 4 5 7 3 8 9 10 11 12 13 14 15 满二叉树
定义2完全二叉树( Complete Binary tree) 若设二叉树的高度为h,则共有h层。除第 h层外,其它各层(0~h-1)的结点数都达到 最大个数,第h层从右向左连续缺若干结点, 这就是完全二叉树。 完全二叉树 非完全二叉树
2 1 4 5 3 6 7 2 1 4 5 6 3 非完全二叉树 定义2 完全二叉树 (Complete Binary Tree) 若设二叉树的高度为h，则共有h层。除第 h 层外，其它各层 (0 h-1) 的结点数都达到 最大个数，第 h 层从右向左连续缺若干结点， 这就是完全二叉树。 6 2 1 4 5 7 3 8 9 10 11 12 完全二叉树