扩充二叉树 图5.3扩充二叉树 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 扩充二叉树 图5.3 扩充二叉树 6 3 1 2 4 9 7 10 5 8
扩充二叉树 从扩充的二叉树的根到每个外部结点的路径长 度之和称为外部路径长度(E)。 扩充的二叉树里从根到每个内部结点的路径长 度之和称为内部路径长度(I)。 ■外部路径长度E和内部路径长度I满足:E=I+ 2n,其中n是内部结点个数。 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 扩充二叉树 ◼ 从扩充的二叉树的根到每个外部结点的路径长 度之和称为外部路径长度(E)。 ◼ 扩充的二叉树里从根到每个内部结点的路径长 度之和称为内部路径长度(I)。 ◼ 外部路径长度E和内部路径长度I满足：E = I + 2n，其中n是内部结点个数
扩充二叉树 例如,在图5.3这个有10个内部结点的扩充二叉树里 E=3+4+4+3+4+4+3+4+4+3+3=39 Ⅰ=0+1+2+3+2+3+1+2+3+2=19 E和I两个量之间的关系为E=I+2n “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 扩充二叉树 6 3 1 2 4 9 7 10 5 8 ◼ 例如，在图5.3这个有10个内部结点的扩充二叉树里 ◼ E = 3 + 4 + 4 + 3 + 4 + 4 + 3 + 4 + 4 + 3 + 3= 39 ◼ I = 0 + 1 + 2 + 3 + 2 + 3 + 1 + 2 + 3 + 2 = 19 ◼ E和I两个量之间的关系为 E = I + 2n
扩充二叉树 证明:对内部结点数目进行归纳 当n=1时,I=0且E=2,故E=I+2n成立。 对于有n个内部结点的扩充二叉树此等式已成立,即En In十2n,现在考虑有n+1个内部结点的扩充二叉树 删去一个分支结点,该分支结点与根结点的路径长度 是K,使之成为有n个内部结点的扩充二叉树。由于删 去了一个路径长度为K的内部结点,内部路径长度变 为In=I-K;由于减少了两个路径长度为K+1的外部 结点,增加了一个路径长度为K的外部结点,外部路 径长度变为En=E+1-2(K+1)+K=En+1-K-2。由 前两个等式,有En+1=Ln+2n+K+2=In+1+2(n+1) 等式E=I+2n得证。 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 扩充二叉树 ◼ 证明：对内部结点数目进行归纳。 ◼ 当n = 1时，I = 0且E = 2，故E = I + 2n成立。 ◼ 对于有n个内部结点的扩充二叉树此等式已成立，即En = In十2n，现在考虑有n + 1个内部结点的扩充二叉树 ◼ 删去一个分支结点，该分支结点与根结点的路径长度 是K，使之成为有n个内部结点的扩充二叉树。由于删 去了一个路径长度为K的内部结点，内部路径长度变 为In = In+1 -K；由于减少了两个路径长度为K + 1的外部 结点，增加了一个路径长度为 K的外部结点，外部路 径长度变为En = En+1 - 2 ( K + 1) + K = En+1 – K - 2。由 前两个等式，有En+1 = In + 2n + K + 2 = In+1 + 2 ( n + 1 ) 。等式E = I+2n得证
二叉树的主要性质 性质1.在二叉树中,第i层上最多有2个结点(i≥0) 证明:利用数学归纳法 当i=0时,20=1,只有一个根结点,正确。 现在假设对所有的j,1≤j<i,命题成立,即第层上之多有2个结点。 下面证明当就=时结论也成立。由归纳假设,第-1层上最多有2-1 个结点。由于二叉树每个结点的度数最大为2,所以第层上的最大结点 数为第i-1层上的最大结点数的2倍,即2个。 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 二叉树的主要性质 ◼ 性质1. 在二叉树中，第i层上最多有2 i个结点（i≥0） 证明：利用数学归纳法 当i = 0时，20 = 1，只有一个根结点，正确。 现在假设对所有的j，1 ≤ j ＜ i，命题成立，即第j层上之多有2j个结点。 下面证明当就j = i时结论也成立。由归纳假设，第i - 1层上最多有2i - 1 个结点。由于二叉树每个结点的度数最大为2，所以第i层上的最大结点 数为第i - 1层上的最大结点数的2倍，即2i个