(1)满二叉树 下面介绍两种特殊形态的二叉树:满二叉树和完全二叉树。 ●一棵深度为k且由2k-1个结点的二叉树称为满二叉树。 图64就是一棵满二叉树,对结点进行了顺序编号。 图64满二叉树 北京邮电大学自动化学院 11
北京邮电大学自动化学院 11 图6.4 满二叉树 2 4 5 3 6 7 1 （1）满二叉树 ⚫ 一棵深度为k且由2 k -1个结点的二叉树称为满二叉树。 图6.4就是一棵满二叉树，对结点进行了顺序编号。 下面介绍两种特殊形态的二叉树： 满二叉树和完全二叉树
(2)完全二叉树 如果深度为k、由n个结点的二叉树中每个结点能够与深度为 k的顺序编号的满二叉树从1到n标号的结点相对应,则称这 样的二叉树为完全二叉树,图65(b)、(c)是2棵非完全 叉树。满二叉树是完全二叉树的特例 (a)完全二叉树(b)非完全二叉树(c)非完全二叉树 图65完全二叉树 北京邮电大学自动化学院
北京邮电大学自动化学院 12 1 2 3 4 5 6 （a）完全二叉树 1 2 3 4 5 7 （b）非完全二叉树 1 2 3 6 7 （c）非完全二叉树 图6.5 完全二叉树 （2）完全二叉树 ⚫ 如果深度为k、由n个结点的二叉树中每个结点能够与深度为 k的顺序编号的满二叉树从1到n标号的结点相对应，则称这 样的二叉树为完全二叉树，图6.5（b）、（c）是2棵非完全 二叉树。满二叉树是完全二叉树的特例
完全二叉树的特点 (1)所有的叶结点都出现在第k层或k-1层。 (2)对任一结点,若其右分支下的子孙的最大层次为,则其 左分支下的子孙的最大层次必为或l+1。 性质4:具有n个结点的完全二叉树的深度为log2n+1。 ●符号Lx表示不大于x的最大整数。 假设此二叉树的深度为k,则根据性质2及完全二叉树的定义得: 2k-1<n<=2k-1或2k1<=n<2k 取对数得到:k-1og2n<k因为k是整数。所以有: k og2n」+1 北京邮电大学自动化学院 13
北京邮电大学自动化学院 13 完全二叉树的特点 ⚫ （1）所有的叶结点都出现在第k层或k－1层。 ⚫ （2）对任一结点，若其右分支下的子孙的最大层次为l，则其 左分支下的子孙的最大层次必为l或l＋1。 ⚫ 性质4：具有n个结点的完全二叉树的深度为log2n＋1。 ⚫ 符号 x表示不大于x的最大整数。 ⚫ 假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得： ⚫2 k-1－1<n<=2k -1 或 2 k-1<=n<2k ⚫ 取对数得到:k－1log2n<k 因为k是整数。所以有： ⚫k＝ log2n ＋1
性质5:如果对一棵有n个结点的完全二叉树的结点按层序 编号(从第1层到第 Logan+1层,每层从左到右)则对任 结点i(1=<=n),有: (1)如果i=1,则结点无双亲,是二叉树的根;如果i>1, 则其双亲是结点i2」。 (2)如果2i>n,则结点i为叶子结点,无左孩子;否则,其 左孩子是结点2i。 (3)如果2+1>n,则结点i右孩子;否则,其右孩子是 结点2i+1。 北京邮电大学自动化学院 14
北京邮电大学自动化学院 14 ⚫ 性质5： 如果对一棵有n个结点的完全二叉树的结点按层序 编号（从第1层到第log2n +1层，每层从左到右),则对任一 结点i（1<=i<=n),有： ⚫ （1）如果i＝1，则结点i无双亲，是二叉树的根；如果i>1， 则其双亲是结点i/2 。 ⚫ （2）如果2i>n，则结点i为叶子结点，无左孩子；否则，其 左孩子是结点2i。 ⚫ （3）如果2i＋1>n，则结点i无右孩子；否则，其右孩子是 结点2i＋1
我们只要先证明(2)和(3),便可以从(2)和(3)推出(1) 对于i=1,由完全二叉树的定义,其左孩子是结点2,若2>n, 即不存在结点2,此时,结点无孩子。结点右孩子也只能是 结点3,若结点3不存在,即3>n,此时结点无右孩子。 2i 2i)(+1(+1(2+3 2i+3 (a)i+1结点在同一层 (b)和i+1结点不在同一层 图66完全二叉树中结点和i+1 北京邮电大学自动化学院
北京邮电大学自动化学院 15 ⚫ 图6.6 完全二叉树中结点i和i+1 [i/2] i i+1 2i 2i+1 2(i+1) 2i+3 (a) i和i+1结点在同一层 i+1 2(i+1) 2i+3 i 2i 2i+1 ⚫ (b)i和i+1结点不在同一层 ⚫ 我们只要先证明（2）和（3），便可以从（2）和（3）推出（1）。 ⚫ 对于i＝1，由完全二叉树的定义，其左孩子是结点2，若2>n， 即不存在结点2，此时，结点i无孩子。结点i的右孩子也只能是 结点3，若结点3不存在，即3>n，此时结点i无右孩子