二叉树性质5证明 - 范文中心

二叉树性质5证明

07/27

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


相关内容

  • 高中立体几何教案
    高中立体几何教案 第一章 直线和平面 两个平面平行的性质教案 教学目标 1.使学生掌握两个平面平行的性质定理及应用: 2.引导学生自己探索与研究两个平面平行的性质定理,培养和发展学生发现问题解决问题的能力. 教学重点和难点 重点:两个平面平 ...
  • 20**年高考数学(理)一轮突破热点题型:第7章 第5节 直线.平面垂直的判定及其性质
    第五节 直线.平面垂直的判定及其性质 1.直线与平面垂直的判定与性质是每年高考的必考内容,题型多为解答题,难度适中,属中档题. 2.高考对直线与平面垂直的判定与性质的考查常有以下几个命题角度: (1)同真假命题的判断相结合考查: (2)以多 ...
  • 齐齐哈尔市20XX年数学学科考试说明(定稿)
    齐齐哈尔市2017年数学学科考试说明 一.指导思想 初中升学考试应有利于贯彻国家的教育方针,促进学校全面实施素质教育:有利于体现九年义务教育的性质,全面提高教育质量:有利于引导新课程的实施,全面落实课程标准所设定的目标:有利于引导课程改革的 ...
  • 4初高中数学新课标解读
    初中数学课程标准高中数学新课标解读 周德俊,李万春 高中老师要面对现实,认真学习义务教育与普通高中的两本<数学课程标淮>,分析参加课改的初中学生有何特点,要做哪些补缺补漏工作,如何调整自己的教学方式.方法等等,才能较好地解决义教 ...
  • 人教版高中数学必修(1-5)目录
    必修一(高一) 第一章 集合与函数概念 一 总体设计 二 教科书分析 1.1 集合 1.2 函数及其表示 1.3 函数的基本性质 实习作业 三 自我检测题 四 拓展资源 第二章 基本初等函数(Ⅰ) 一 总体设计 二 教科书分析 2.1 指数 ...
  • 上海员工办理社保流程及材料
    员工情况员工 户籍分类 其他 需员工提供的资料 用工.办理档案 前程办理程序 需员工提供的资料 办理社保前程办理程序 属代理性质:由我司填写<社会保险业务办事提示单>和<个人社会保险登记表(登记2表)>: 属派遣性质 ...
  • 不等式性质证明复习
    不等式的性质和证明 1. 不等式的性质是证明不等式和解不等式的依据. 样 由不等式性质定理4的推论2和定理5可得: 如果a .b ∈ R+, 那么a > b ⇔ a n > b n (n∈N), 在比较分数指数幂或根式的值的大小 ...
  • 冀教版初中数学教材总目录
    冀教版初中数学教材 总目录 七年级上册 第一章 几何图形的初步认识 1.1 几何图形1.2 图形中的点.线.面1.3 几何体的表面展开图 1.4 从不同方向看几何体1.5 用平面截几何体 第二章 有理数 2.1 正数和负数2.2 数轴2.3 ...
  • 三角形全等的证明教案
    三角形全等的证明 [知识梳理] (一)三角形概述: 1.定义(包括内.外角) 2.性质:三角形的边角关系:⑴角与角:①内角和及推论;②外角和;③n边形内角和;④n边形外角和. ⑵边与边:三角形两边之和大于第三边,两边之差小于第三边. ⑶角与 ...
  • 涉黑犯罪的辩护词
    江 苏 致 邦 律 师 事 务 所 Jiang Su Co-Far Law Firm 中国"南京"石头城6号石榴财智中心05幢 邮编:210013 building 05,6 shitoucheng Rd,gulou d ...