二叉树的主要性质 性质2深度为k的二叉树至多有2k+1-1个结点(k0) 其中深度(deph)定义为二叉树中层数最大的叶结点的层 数 证明:由性质1可知,第i层的最大结点数为2,所以 k ∑2=21-1 1=0 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 二叉树的主要性质 ◼ 性质2. 深度为k的二叉树至多有 2 k+1 -1个结点（k≥0）。 其中深度(depth)定义为二叉树中层数最大的叶结点的层 数。 证明：由性质1可知，第i层的最大结点数为2i，所以 k i k i 0 2 2 1− +1 ＝ ＝
二叉树的主要性质 性质3任何一棵二叉树,若其终端结点数为m,度为2 的结点数为n2,则n=n2+1。 证明:设n1为二叉树中度为1的结点数。该二叉树的结点总数n为度分别为0 1,2的结点数之和,即 n=no+n1+n2 (公式51) 除根结点外,其余结点都有一条边进入,设边数为e,有n=e+1。由于 这些边是由度为1或2的的结点发出的,所以又有e=n1+2n2,于是得 n=e+1=n1+2n2+1(公式52) 由公式51和52得n+n1+n2=n1+2n2+1, 即 1 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 二叉树的主要性质 ◼ 性质3. 任何一棵二叉树，若其终端结点数为n0，度为2 的结点数为n2，则n0=n2+1 。 证明：设n1为二叉树中度为1 的结点数。该二叉树的结点总数n为度分别为0 ，1，2的结点数之和，即 n=n0+n1+n2 （公式5.1） 除根结点外，其余结点都有一条边进入，设边数为e，有n = e + 1。由于 这些边是由度为1或2的的结点发出的，所以又有e=n1+2n2，于是得 n=e+1=n1+2n2+1 （公式5.2） 由公式5.1和5.2得 n0+n1+n2=n1+2n2+1， 即 n0=n2+1
二叉树的主要性质 性质4.满二叉树定理:非空满二叉树树叶数目 等于其分支结点数加1 证明:满二叉树定理由性质3可直接推出。 性质5.满二叉树定理推论:一个非空二叉树的 空子树数目等于其结点数加1。 证明:设二叉树为T,将其所有空子树换为树叶,记新扩充满二叉 树为T。所有原来T的结点现在是T的分支结点。根据满二叉树定 理,新添加的树叶数目等于T结点个数加1而每个新添加的树叶 对于T的一个空子树。因此T中空子树数目等于T中的结点个数加1 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 二叉树的主要性质 ◼ 性质4. 满二叉树定理：非空满二叉树树叶数目 等于其分支结点数加1。 证明：满二叉树定理由性质3可直接推出。 ◼ 性质5. 满二叉树定理推论：一个非空二叉树的 空子树数目等于其结点数加1。 证明：设二叉树为T，将其所有空子树换为树叶，记新扩充满二叉 树为T’。所有原来T的结点现在是T’的分支结点。根据满二叉树定 理，新添加的树叶数目等于T结点个数加1。而每个新添加的树叶 对于T的一个空子树。因此T中空子树数目等于T中的结点个数加1
二叉树的主要性质 ■性质6.有n个结点(n>0)的完全二叉树的高度为 og2(n+1)(深度为og2(n+1)-1)。其中二叉 树的高度( height定义为二叉树中层数最大的叶结 点的层数加1。 证明:假设高度为h,则根据性质2和完全二叉树的定义, 有21-1<ns2-1或2<n+1<2h 不等式中各项取对数,于是得到h-1<log2+≤h因为h为整数 ,所以h=og2(n+1) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 二叉树的主要性质 ◼ 性质6. 有n个结点（n>0）的完全二叉树的高度为 [log2 (n+1)]（深度为[log2 (n+1)] - 1）。 其中二叉 树的高度(height)定义为二叉树中层数最大的叶结 点的层数加1。 证明：假设高度为h，则根据性质2和完全二叉树的定义， 有 或 不等式中各项取对数，于是得到 。因为h为整数 ，所以h＝[log2 (n+1)]。 h-1 h 2 1 n 2 1 − − h-1 h 2 n+1 2 n 1 h 1 log h − 2 ＋
二叉树的主要性质 性质7对于具有n个结点的完全二叉树,结点按层 次由左到右编号,则对任一结点i(0<i≤n-1) 有 (1)如果i=0,则结点i是二叉树的根结点;着i>0,则其父结点编号 是I(-1)/2 (2)当2i+1≤n-1时,结点的左子结点是2+1,否则结点设没有左子 结点。 当2i+2≤n-1时,结点i的右子结点是2i+2,否则结点设没有右子结 点。 (3)当i为偶数且0<i<n时,结点左兄弟是结点i-1,否则结点设没 有左兄弟 当i为奇数且计+1<n时,结点i右兄弟是结点i+1,否则结点设有 右兄弟。 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 二叉树的主要性质 ◼ 性质7. 对于具有n个结点的完全二叉树，结点按层 次由左到右编号，则对任一结点i（0 ≤ i ≤ n - 1） 有 （1）如果i = 0，则结点i是二叉树的根结点；若i＞0，则其父结点编号 是[(i - 1)/2]。 （2）当2i + 1 ≤ n - 1时，结点i的左子结点是2i + 1，否则结点i没有左子 结点。 当2i + 2 ≤ n - 1时，结点i的右子结点是2i + 2，否则结点i没有右子结 点。 （3）当i为偶数且0 < i < n时，结点i的左兄弟是结点i - 1，否则结点i没 有左兄弟。 当i为奇数且i+1 < n时，结点i的右兄弟是结点i + 1，否则结点i没有 右兄弟