讨论3:二叉树的叶子数和度为2的结点数之间有关系吗? 3若非空二叉树有n个叶结点有n2个度为2的结点, 则n=n2+1 证明 设该二叉树有n1个度为1的结点结点总数为n有 n=n0+n1+n2 --(1) 设二叉树的分支数目为B有 B=n-1 (2) 这些分支来自度于为1的结点与度度为2结点即 B=n1+2n2 (3) 联列关系(1,(2)与(3)可得到 证毕 n0=n2+1 实际意。叶数=2度结点数+1 「推论;mo=n2+2n3+3n4+…+(m-1)nm+1
3. 若非空二叉树有n0个叶结点,有n2个度为2的结点, 则 n0=n2+1 证明: 设该二叉树有n1个度为1的结点,结点总数为n,有 n=n0+n1+n2 --------(1) 设二叉树的分支数目为B,有 B=n-1 --------(2) 这些分支来自度于为1的结点与度度为2结点,即 B=n1+2n2 --------(3) 联列关系(1),(2)与(3),可得到 n0=n2+1 证毕. 推论： n0=n2+2n3+3n4+ +(m-1)nm +1 二叉树的性质 讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？ A B C E G I D H F J 实际意义：叶子数＝2度结点数＋1
对于两种特殊形式的二叉树(满二叉树和完全二叉树),还特别 具备以下2个性质: 4.具有n个结点的完全二叉树的深度h=ogn1 证明: 设完全二叉树的深度为k 则根据第二条性质得2k1≤n<2k 即k-l≤log2n<k 因为k只能是整数,因此,k=log2n/+1 证毕
4. 具有n个结点的完全二叉树的深度h=log2n+1. 证明: 二叉树的性质 设 完全二叉树的深度为 k 则根据第二条性质得 2 k-1≤ n < 2k 即 k-1 ≤ log2 n < k 因为 k 只能是整数，因此， k =log2n + 1 证毕. 对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别 具备以下2个性质：
5.若对具有n个结点的完全二叉树按照层次从上到下每层从 左到右的顺序进行编号,则编号为的结点具有以下性质 (1)当i=1,则编号为的结点为二叉树的根结点; 若>1,则编号为的结点的双亲结点的编号为Li2 (2)若2>n,则编号为的结点无左子树; 若2≤n,则编号为的结点的左子树的根的编号为2 (3)若2+1>n,则编号为的结点无右子树; 若2+1≤n,则编号为的结点的右子树的根的编号为2+1 n=10 5 880
5. 若对具有n个结点的完全二叉树按照层次从上到下,每层从 左到右的顺序进行编号, 则编号为i 的结点具有以下性质: (1) 当i=1, 则编号为i的结点为二叉树的根结点; 若i>1, 则编号为i 的结点的双亲结点的编号为i/2. (2) 若2i>n, 则编号为i 的结点无左子树; 若2in, 则编号为i 的结点的左子树的根的编号为2i. (3) 若2i+1>n, 则编号为i 的结点无右子树; 若2i+1n, 则编号为i 的结点的右子树的根的编号为2i+1. 1 2 3 4 5 6 7 8 9 10 n=10 二叉树的性质
间的 商影态的又筒 满二叉 特点:每层都“充满”了结点) 为何要研究这两种特殊形式? 喇因为它们在顺序存储方式下可以复原! 样 2亮金二又制 若棵二又树中只有最下 面两层的结点的度可以于2 解释:完全二叉树的特点就是 并且最下面一层的结点〔结 只有最后层叶不满,且全部 集中在左边。 点都依》排列在该层从左至 这其实是顺序二叉树的含义。 右的位置上。这样的二又树为在图论概念中的“完全二叉树 完全二叉树 是指n=0的情况
两种特殊形态的二叉树 若一棵二叉树中的结点, 或者为叶结点，或者具有两 棵非空子树,并且叶结点都集 中在二叉树的最下面一层.这 样的二叉树为满二叉树. 1. 满二叉树 若一棵二叉树中只有最下 面两层的结点的度可以小于2, 并且最下面一层的结点(叶结 点)都依次排列在该层从左至 右的位置上。这样的二叉树为 完全二叉树. 2.完全二叉树 二叉树的性质 解释：完全二叉树的特点就是， 只有最后一层叶子不满，且全部 集中在左边。 这其实是顺序二叉树的含义。 在图论概念中的“完全二叉树” 是指n1=0的情况。 为何要研究这两种特殊形式？ 因为它们在顺序存储方式下可以复原! （特点：每层都“充满”了结点）
1、顺序高储结构 、链露高储构
三、二叉树的存储结构 1、顺序存储结构 2、链式存储结构