作业帮求证明关于二叉树性质6有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系： 若I为结点编号则 如果I1,则其父结点的编号为I/2； 如果2*IN,则无左儿子； 如
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/09 00:38:47
求证明关于二叉树性质6有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系： 若I为结点编号则 如果I1,则其父结点的编号为I/2； 如果2*IN,则无左儿子； 如
求证明关于二叉树性质6
有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系： 若I为结点编号则 如果I1,则其父结点的编号为I/2； 如果2*IN,则无左儿子； 如果2*I+1N,则无右儿子. (6)给定N个节点,能构成h(N)种不同的二叉树.
求证明关于二叉树性质6有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系： 若I为结点编号则 如果I1,则其父结点的编号为I/2； 如果2*IN,则无左儿子； 如
叉树具有以下重要性质：
性质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层上还有若干个结点,因此该完全二叉树的结点个数：
n
边的好证，2的k次方减一显然是小于2的k次方的，所以n小于2的k次方
左边的，因为结点n肯定是整数，2的k-1次方减一也是整数---记为A
如果n，A都是整数且n