二叉树性质5证明

二叉树性质5证明 | 楼主 | 2016-11-30 22:40:10 共有3个回复
  1. 1二叉树性质5证明
  2. 2学生证明二叉树性质3(5班朱从州)
  3. 3二叉树性质3证明-5班熊文昌

摘要:如果则结点为叶子结点无左孩子否则其左孩子是结点,我们可以首先证明然后由很自然的就会推出,第一部分第层的我们之间假设的个结点,关系式是这样求得的即第层的结点数所以有。以下是小编整理的3篇最新二叉树性质5证明范文,欢迎参阅!

二叉树性质5证明2016-11-30 22:38:14 | #1楼回目录

针对当前缺少对二叉树性质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得到了证明。

学生证明二叉树性质3(5班朱从州)2016-11-30 22:37:24 | #2楼回目录

====================================================

From: zhucz333 <#url#>

To: #url# <#url#>

Subject: 证明n0n2 +1

Date: 04-9-25 9:50:53

====================================================

刘老师:

您好!

我是电信0305班的朱从州。您说的关于二叉树的第三个性质的证明,我证出来了,但不知道有没有漏洞,请您看一下!

证明思路:对于非空的二叉树,要从整体上给出终端结点和度为2的结点的关系,很不好把握。但分析二叉树的子树的结构有度为1和2两种结构(度为0的包含在度为一的情况中进行证明),从分析这两种结构来总结二叉树中度为0的结点和度为2的结点的关系。

证明:

(1):若二叉树的度为1,显然得到n0=n2 +1(n0=1,n2=0)。

结论1:度为一的二叉树满足n0=n2 +1。

结论2:度为一的子树不影响二叉树中度为0的结点和度为2的结点的关系。

(2):若二叉树为满二叉树,我们先给出一个根和他的两个子树,此时满足n0=n2 +1的关系 。现在若想再增加二叉树的层数,必须将原来的子叶变为度为2的结点,此时度为2的结点增加了一个,同时度为0的结点也增加了一个,所以层数的增加也不能影响n0=n2 +1的关系。

结论1:满二叉树满足n0=n2 +1的关系。

结论2:满二叉树层数的增加不能改变n0=n2 +1的关系。

(3):任意的非空二叉树都可以由(1),(2)的结构组合而成,并且(1)和(2)已证明它们不能改变n0=n2 +1的关系。因此得结论:任意的非空二叉树满足关系n0=n2 +1。

由此命题得证!

证毕!!

此致

朱从州

04-9-25

-------------------------------------------------------------------------------------

周杰伦在"第一现场"与你面对面 #url#

二叉树性质3证明-5班熊文昌2016-11-30 22:39:59 | #3楼回目录

二叉树性质3证明

电5熊文昌证明:

性质3:

对任何一颗二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1;

证明:设p[i]代表第i层的结点;

1> :i=1时 仅有根结点 ―――――――n0=1,n2=0 n0=n2+1;

2> :i>1时 对于每一层,其结点生成下层结点方式有两种:

a> :一个结点生成两个 :n0=n0+1, n2=n2+1n0=n2+1;

b> :一个结点生成一个 :n0=n0+0, n2=n2+0n0=n2+1;

(这两种方式可生成任何二叉树)

由此归纳可得:对任何一颗二叉树T,均有:n0=n2+1

电4张晓力证明:

设总结点数为n,则n=1时(即只有根结点),肯定满足n0=n2+1;

设n=k时满足n0=n2+1,

则n=k+1时,即在n=k的二叉树上再加一个结点,

若结点的双亲为叶子,则新的根的叶子总数n0不变,n2不变,仍然满足n0=n2+1; 若结点的双亲为只有一个分支的结点,则

叶子数n0=n0+1,度为2的结点数n2=n2+1;仍有n0=n2+1成立;

故n=任意值均满足条件。

电3邢昆峰证明:

设度为1的结点数为a,度为2的结点数为b,叶子数为c:

除根结点外,每个度为2的结点共与三个叉相连,度为1的结点与两个叉相连,在根结点上虚拟一个叉则应是一个叉上有一个节点,即[3( b-1)+2+c+2a]/2+1=a+b+c;整理得c=b+1;

证毕。

电1范倩证明性质5:

设左孩子标号为a,右孩子标号为b,选定结点标号为k;

1)当只有两层时:

根结点标号为k=i=1, 他的左孩子为a=2=2i, 右孩子为b=3=2i+1;

2)当其层数超过两层时:

取任一标号为k=i的结点,并设其左孩子标号a=2*I,其右孩子标号b=2*i+1, 则可求得a与k之间按标号相差的结点个数j=a-k+1=i-1;

在研究a的孩子时,a的左孩子和a之间按标号隔的是这(i-1)个结点的所有孩子[2*(i-1)],以及b点,故得a的左孩子的标号a'=a+2*(i-1)+1+1=4*i=2a,故a的右孩子标号b'=a'+1=4*i+1=2a+1;

反方向可证k结点的双亲为i/2;

综上所述,k=2时成立;

由前一层可推出下一层,故定理得证!

简单证明,必有疏漏,还待修改,请老师和同学赐教!

回复帖子
标题:
内容:
相关话题