Algorithms and Datastrucstures:Trees 二叉树的性质 性质3 对于一棵非空二叉树，如果叶子结点数为no,度数为2的结点数为n2 则有：n=n2十1成立。 证明 设n为二叉树的结点总数，n1为二叉树中度数为1的结点数。 二叉树中所有结点均小于或等于2，所以有： n=no+n1十n2 (5-1) 再看二叉树中的树枝（父结点和儿子结点之间的线段）总数。 在二叉树中，除根结点外，其余结点都有唯一的一个树枝进入本结点。 设B为二叉树中的树枝数，那么有下式成立： B=n-1 (5-2) 这些树枝都是由度为1和度为2的结点发出的， 一个度为1的结点发出一个树枝，一个度为2的结点发出两个树枝， 所以有： B=n1+2n2 (5-3) 由（5-1)、(5-2)、（5-3)式可以得到： n0=n2+1 16 ALDS
16 物料管理 ALDS 16 Algorithms and DataStrucstures:Trees 性质3 对于一棵非空二叉树，如果叶子结点数为n0，度数为2的结点数为n2， 则有: n0＝n2＋1 成立。 证明 设n为二叉树的结点总数，n1为二叉树中度数为1的结点数。 二叉树中所有结点均小于或等于2，所以有： n ＝ n0 ＋ n1 ＋ n2 （5-1） 再看二叉树中的树枝(父结点和儿子结点之间的线段)总数。 在二叉树中，除根结点外，其余结点都有唯一的一个树枝进入本结点。 设B为二叉树中的树枝数，那么有下式成立： B ＝ n－1 （5-2） 这些树枝都是由度为1和度为2的结点发出的， 一个度为1的结点发出一个树枝，一个度为2的结点发出两个树枝， 所以有： B ＝ n1＋2n2 （5-3） 由（5-1）、（5-2）、（5-3）式可以得到： n0＝n2＋1 二叉树的性质
Algorithms and Datastrucstures:Trees 满二叉树 如果一棵二叉树中的任意一层的结点个数都达到了最大值， 那么这棵二叉树称为满二叉树或丰满树。 图5.4所示是一棵层数为4层的满二叉树，结点个数达到了最大值15。 图5.5不是满二叉树，因第4层的结点个数未达到最大值。 M 图5.4满二叉树实例 图5.5一棵完全二叉树 17 ALDS
17 物料管理 ALDS 17 Algorithms and DataStrucstures:Trees 如果一棵二叉树中的任意一层的结点个数都达到了最大值， 那么这棵二叉树称为满二叉树或丰满树。 图5.4所示是一棵层数为4层的满二叉树，结点个数达到了最大值15。 图5.5不是满二叉树，因第4 层的结点个数未达到最大值。 图5.4 满二叉树实例 图5.5 一棵完全二叉树 满二叉树 D C E F G B A H I J K L M N O
Algorithms and Datastrucstures:Trees 完全二叉树 (a)完全二叉树 (b)非完全二叉树 在满二叉树的最底层自右至左依次（注意：不能跳过任何一个结点）去掉若干个 结点得到的二叉树也被称之为完全二叉树，图(a)就给出了一棵完全二叉树。 满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。 完全二叉树的特点是： (1)所有的叶结点都出现在最低的两层上。 (2)对任一结点，如果其右子树的高度为k,则其左子树的高度为k或k十1。 18 ALDS
18 物料管理 ALDS 18 Algorithms and DataStrucstures:Trees 0 1 2 3 4 (a)完全二叉树 ( b)非完全二叉树 完全二叉树 在满二叉树的最底层自右至左依次(注意：不能跳过任何一个结点)去掉若干个 结点得到的二叉树也被称之为完全二叉树，图(a)就给出了一棵完全二叉树。 满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。 完全二叉树的特点是： （1）所有的叶结点都出现在最低的两层上。 （2）对任一结点，如果其右子树的高度为k，则其左子树的高度为k或k＋1
Algorithms and Datastrucstures:Trees 完全二叉树的不同定义 4 (a)非完全二叉树 (b)完全二叉树 在有些数据结构的教科书上，将具有以下特点的二叉树定义为完全二叉树：即 二叉树中的所有结点要么有二个儿子，要么一个儿子也没有。 19 ALDS
19 物料管理 ALDS 19 Algorithms and DataStrucstures:Trees 0 1 2 3 4 (a)非完全二叉树 ( b) 完全二叉树 完全二叉树的不同定义 在有些数据结构的教科书上，将具有以下特点的二叉树定义为完全二叉树：即 二叉树中的所有结点要么有二个儿子，要么一个儿子也没有
Algorithms and Datastrucstures:Trees 完全二叉树的高度 性质4具有n个结点的完全二叉树的高度k=L1og2n+1。 证明根据完全二叉树的定义和性质2可知，高度为k的完全二叉树的第 一层到第k-1层具有最多的结点个数最多，总数为2k1-1个，第k层至少具有 一个结点。因此， 2k-1-1<n≤2k-1 即 2k-1≤n<2k 对不等式取对数，有 k-1≤1og2n〈k 由于k是整数，所以有：k=Llog2n」+1。 20 ALDS
20 物料管理 ALDS 20 Algorithms and DataStrucstures:Trees 完全二叉树的高度 性质4 具有n个结点的完全二叉树的高度k = log2n + 1。 证明 根据完全二叉树的定义和性质2可知，高度为k的完全二叉树的第 一层到第k-1层具有最多的结点个数最多，总数为 2 k-1- 1个，第k层至少具有 一个结点。因此， 2 k-1 - 1< n ≤ 2 k - 1 即 2 k-1≤n<2 k 对不等式取对数，有 k -1 ≤ log2n < k 由于k是整数，所以有：k = log2n ＋ 1