二叉树的性质和图.docxVIP

二叉树和图 图是由顶点和边组成的，如果从顶点v1道顶点v2有条路径，则称它们是连通的，如果无向图G中的每两个顶点都是连通的则G就叫做连通图。 那么如果任意一个无向图的极大连通子图就叫做连通分量。 而如果有向图G中的任意两个顶点都是连通的，那么G就是强连通图。 生成树就是包含图中所有顶点的树。 最小生成树是权值之和最小的生成树。 二叉树具有以下重要性质：性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。证明：用数学归纳法证明：　??? 归纳基础：i=1时，有2i-1=20=1。因为第1层上只有一个根结点，所以命题成立。??? 　归纳假设：假设对所有的j(1≤ji)命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。??? 　归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2×2i-2=2i-1个结点，故命题成立。性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为：??????????????? 20+21+…+2k-1=2k-1??? 故命题正确。性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点(记为n1)和2度结点数之和：???????????????????? n=no+n1+n2 (式子1)　??? 另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：????????????????????? nl+2n2　　树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：????????????????????? n=n1+2n2+1 (式子2)　　由式子1和式子2得到：????????????????????? no=n2+1满二叉树和完全二叉树是二叉树的两种特殊情形。1、满二叉树(FullBinaryTree)???? 　一棵深度为k且有2k-1个结点的二又树称为满二叉树。??? 　满二叉树的特点：　　（1） 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。　　（2） 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。　　【例】图(a)是一个深度为4的满二叉树。 2、完全二叉树(Complete BinaryTree)???? 若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。? 特点：? （1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。? （2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。? （3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。【例】如图(c)中，结点F没有左孩子而有右孩子L，故它不是一棵完全二叉树。【例】图(b)是一棵完全二叉树。? 性质4? 具有n个结点的完全二叉树的深度为????????????????????????? 证明：设所求完全二叉树的深度为k。由完全二叉树定义可得：　　深度为k得完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数：????????????????? n2k-1-1。??? 　另一方面，由性质2可得：????????????????? n≤2k-1，?????? 即：2k-1-ln≤2k-1??? 　由此可推出：2k-1≤n2k，取对数后有：????????????????? k-1≤lgnk??? 　又因k-1和k是相邻的两个整数，故有??????????????????????????????????? ,??? 　由此即得：???????????????? 注意：???????? 的证明【参见参考书目】