|
二叉树具有以下重要性质 性质 二叉树第i层上的结点数目最多为i(i≥) 证明用数学归纳法证明 归纳基础i=时有i==因为第层上只有一个根结点所以命题成立 归纳假设假设对所有的j(≤j<i)命题成立即第j层上至多有j个结点证明j=i时命题亦成立 归纳步骤根据归纳假设第i层上至多有i个结点由于二叉树的每个结点至多有两个孩子故第i层上的结点数至多是第i层上的最大结点数的倍即j=i时该层上至多有×i=i个结点故命题成立 性质 深度为k的二叉树至多有k个结点(k≥) 证明在具有相同深度的二叉树中仅当每一层都含有最大结点数时其树中结点数最多因此利用性质可得深度为k的二叉树的结点数至多为 ++…+k=k 故命题正确 性质 在任意棵二叉树中若终端结点的个数为n度为的结点数为n则no=n+ 证明因为二叉树中所有结点的度数均不大于所以结点总数(记为n)应等于度结点数度结点(记为n)和度结点数之和 n=no+n+n (式子) 另一方面度结点有一个孩子度结点有两个孩子故二叉树中孩子结点总数是 nl+n 树中只有根结点不是任何结点的孩子故二叉树中的结点总数又可表示为 n=n+n+ (式子) 由式子和式子得到 no=n+ 满二叉树和完全二叉树是二叉树的两种特殊情形满二叉树(FullBinaryTree) 一棵深度为k且有k个结点的二又树称为满二叉树 满二叉树的特点 （） 每一层上的结点数都达到最大值即对给定的高度它是具有最多结点数的二叉树 （） 满二叉树中不存在度数为的结点每个分支结点均有两棵高度相同的子树且树叶都在最下一层上 【例】图(a)是一个深度为的满二叉树 完全二叉树(Complete BinaryTree) 若一棵二叉树至多只有最下面的两层上结点的度数可以小于并且最下一层上的结点都集中在该层最左边的若干位置上则此二叉树称为完全二叉树 特点 （） 满二叉树是完全二叉树完全二叉树不一定是满二叉树 （） 在满二叉树的最下一层上从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树 （） 在完全二叉树中若某个结点没有左孩子则它一定没有右孩子即该结点必是叶结点 【例】如图(c)中结点F没有左孩子而有右孩子L故它不是一棵完全二叉树 【例】图(b)是一棵完全二叉树 性质 具有n个结点的完全二叉树的深度为 证明设所求完全二叉树的深度为k由完全二叉树定义可得 深度为k得完全二叉树的前k层是深度为k的满二叉树一共有k个结点 由于完全二叉树深度为k故第k层上还有若干个结点因此该完全二叉树的结点个数 n>k 另一方面由性质可得 n≤k 即kl<n≤k 由此可推出k≤n<k取对数后有 k≤lgn<k 又因k和k是相邻的两个整数故有 由此即得 注意 的证明【参见参考书目】 |
