二叉树 n二叉树是结点的有限集合: 该集合或者为空; 或者由一个根结点加上两棵分别称为左子树和右子 树的、互不相交的二叉树组成 这个定义也是递归的 R R 空 只有根右子树为空右子树为空 左右子树不为空
二叉树 ◼ 二叉树是结点的有限集合： 该集合或者为空； 或者由一个根结点加上两棵分别称为左子树和右子 树的、互不相交的二叉树组成。 ◼ 这个定义也是递归的 6 Ф L R L R 空 只有根 右子树为空 右子树为空 左右子树不为空
二叉树 性质1 口若二叉树的层次从1开始,则在二叉树的第i(论1) 层最多有21个结点。 口证明:(用数学归纳法) i=1时,根结点只有1个,21=20=1; >若设i=k时性质成立,即该层最多有2k1个结点, 则当i=k+1时,由于第k层每个结点最多可有2个 子女,第k+1层最多结点个数可有2k1=2k个,故 性质成立
二叉树 ◼ 性质1 若二叉树的层次从1 开始, 则在二叉树的第i ( i≥1) 层最多有 2 i-1 个结点。 证明：(用数学归纳法) ➢ i = 1时，根结点只有1个，2 1-1 = 20 =1； ➢ 若设 i = k 时性质成立，即该层最多有2 k-1 个结点， 则当 i = k+1 时，由于第k 层每个结点最多可有2 个 子女，第 k+1 层最多结点个数可有2*2k-1 = 2k 个，故 性质成立。 7
二叉树 n性质2 口高度为h(h21)的二叉树最多有2-1个结点。 口证明:(用求等比级数前k项和的公式) 高度为h的二叉树有h层,各层最多结点个数相加, 得到等比级数,求和得: 20+21+22++2h-1=2h-1 a空树的高度为0,只有根结点的树的高度为1
二叉树 ◼ 性质2 高度为 h (h≥1) 的二叉树最多有 2 h -1个结点。 证明：(用求等比级数前k项和的公式) ➢ 高度为 h 的二叉树有 h 层，各层最多结点个数相加， 得到等比级数，求和得： ➢ 2 0 + 21 + 22 + … + 2h-1 = 2h-1 空树的高度为 0，只有根结点的树的高度为 1。 8
二叉树 性质3 口对任何一棵非空二叉树,如果其叶结点有n个,度 为2的非叶结点有n2个,则有n=n2+1 证明: 若设度为1的结点有n1个,总结点个数为n,总边 数为e,则根据二叉树的定义, n=n0+n+n2,且e=2n2+n1=n-1 因此,有2n2+n1=n0+n1+n21 0 +1
二叉树 ◼ 性质3 对任何一棵非空二叉树, 如果其叶结点有 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 9
二叉树 n满二叉树 深度为k的满二叉树是有2k1个结点的二叉树 特点:每一层结点数都达到了最大数 完全二叉树 深度为k的完全二叉树中每一个结点的编号都与 深度为k的满二叉树中编号一一对应 特点:从第1层到第k-1层是满的,仅最下面第k层 或是满的,或是从右到左缺若千结点 10
二叉树 ◼ 满二叉树 深度为k的满二叉树是有2 k -1个结点的二叉树 特点：每一层结点数都达到了最大数 ◼ 完全二叉树 深度为 k 的完全二叉树中每一个结点的编号都与 深度为k的满二叉树中编号一一对应 特点：从第1层到第k-1层是满的，仅最下面第k层 或是满的，或是从右到左缺若干结点 10