针对当前缺少对二叉树性质5的较明确与直观的证明,故做了如下的证明:
性质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×i=2﹥n,也就是不存在结点2,此时结点i无左孩子。否则左孩子编号为2,结点1的右孩子是结点3,即2×1+1=3﹥n,也就不存在结点3,此时结点1无右孩子,否则右孩子编号为3。
当i>1时,可分为两种情况:
情况1:设第j(j>=1)层的第一个结点的编号为i,由完全二叉树关于求和的性质知 i=2j-1((2j-1-1+1))结点i的左孩子必定为的j+1层的第一个结点,其编号为2j(2j-1-1+1)如果2j>n,则无左孩子,否则有左孩子编号2j=2*2j-1=2*i,其右孩子必定为第j+1层的第二个结点,相应编号为2j+1。若2j+1>n,则无右孩子,否则右孩子编号为2j+1=2*2j-1+1=2*i+1,故符合性质描述。
情况2:假设第j层上的某个结点编号为i,则其若有左孩子则其左孩子的编号k我们可以这样来求得,首先需要求得当前第j层编号为i的节点与其左孩子节点之间相差多少个结点,我们把相差的结点数记为a。若我们能求得a则相应编号为i的节点的左孩子为:
k=i+a (1)
从而求得他们之间的关系,下面我们就来求这个a:
接下来我们来求上面提到的a,我们怎么求呢,很简单,a的构成有两部分:
第一部分:第j层的我们之间假设的b个结点
第二部分:第j+1层的到第i个结点的左孩子之前的结点数c
即
a=b+c (2)
为了求a我们需要先求得b和c,下面先求b,假设与编号为i的节点处于同一层(即j层)的并且位于其左边的结点的结点数记为b,那么我们可以得到第j层之前包括第j层的结点总数(即深度为j的满二叉树的结点总数)=2j-1=i+b,:
i+b=2j-1 (3)
关系式(2)是这样求得的,即第j层的结点数=2j-1=i+b,所以有i+d=2j-1。我们将关系式(2)变换后可以求得b,即:
b= 2j-i-1 (4)
下面我们再来求c,c怎么求呢,也很简单,c也就是处于第j层并且位于编号为i的结点之前的一系列结点生成的子结点的个数,故
c=[i-(2j-1-1)-1]*2=(i-2j-1)*2 (4)
这样我们由上面的(1)(2)(4)式就可以得到k与i之间的关系:
K=i+a=i+b+c=i+2j-i-1+(i-2j-1)*2=2i (5)
由式子(5)我们得到了编号为i的结点的左孩子的编号为:2i,同样若其有右孩子则右孩子的编号必然为2i+1。
综上所述,不失一般性,我们得证二叉树的性质5中的第二个和第三个性质,也就是关于完全二叉树的性质。
既然上面的性质得证那么我们很自然的就会推出,二叉树性质5中的第一个性质,即编号为i的结点的双亲结点的编号为:[i/2]向下取整。
至此二叉树的性质5得到了证明。