二叉树性质的性质及证明整理

二叉树性质的性质及证明整理——整理于2020.4.29二叉树的性质及证明性质1:在二叉树的第i层上至多有2(i-1)个结点(i>=1)证明:数学归纳法(1) i=1时只有一个根节点。显然2(i-1)=20=1是对的(2) 假设对所有的j,1<=j<i,命题成立,即第j层上至多有2(j-1)个结点(3)由归纳假设可得:第i-1层上至多有2(i-2)个结点。由于二叉树…

大家好,又见面了,我是你们的朋友全栈君。

——整理于2020.4.29

二叉树的性质及证明

性质1:在二叉树的第i层上至多有2(i-1)个结点 (i>=1)

证明:数学归纳法
(1) i=1时只有一个根节点。显然 2(i-1)= 20= 1是对的
(2) 假设对所有的 j, 1<= j <i, 命题成立,即第j层上至多有2(j-1)个结点
(3) 由归纳假设可得: 第i-1层上至多有2(i-2)个结点。由于二叉树的每个结点的度数至多为2,所以在第i层上的结点数最多为i-1层上的两倍,即2*2(i-2)=2(i-1),即得出第i层上结点数至多为2(i-1)

性质2:深度为k的二叉树至多有2(k-1)个结点(k>=1)

证明:等比数列求和( Sn=a1(1-qn) / 1-q )
由性质一( 在二叉树的第i层上至多有2(i-1)个结点(i>=1) )可知,深度为k的二叉树的最大结点数为:
在这里插入图片描述

性质3:对任何一棵二叉树T, 如果其终端结点(叶子结点)数为 n0, 度数为2的结点数为 n2, 则n0=n2+1

证明:
设n1为二叉树T中度数为1的结点数,n为二叉树结点总数,则有:
n=n0+n1+n2
又因为二叉树中除根节点外每一个结点都对应一个分支,则分支数B=n-1,
由于这些分支是由度为一和二的结点射出的,所以有B=n1+2*n2,所以有:
n=n1+2*n2+1 ②
联立①②可得 n0=n2+1

完全二叉树的两个重要性质

性质4: 具有n个结点的完全二叉树的深度为 ⌊log2n⌋+1
注:⌊x⌋表示不大于x的最大整数

证明:假设完全二叉树的深度为k,则根据性质2和完全二叉树的定义有
2(k-1) -1 < n <= 2k -1
由于n为整数,上式可变为:
2(k-1) <= n < 2k
两边同时取对数得:
k-1 <= log2n < k
因k为整数,即得k= ⌊log2n⌋+1

性质5:
如果对一颗有n个结点得完全二叉树(其深度为⌊log2n⌋ +1)得结点按层序编号(从第1层到第⌊log2n⌋ +1层,每层从左到右),对任一结点 i (1<= i <= n)有:
1.如果 i =1,则结点 i 是二叉树得根,无双亲;如果 i>1,则其双亲是结点⌊i/2⌋
2.如果 2i > n,则结点 i 无左孩子(结点 i 为叶子结点); 否则其左孩子是结点 2i
3.如果 2i+1 > n,则结点 i 无右孩子; 否则其右孩子是结点2i+1

证明:(暂时简单说明,有空再补)
参考大话数据结构/北京大学出版社/程杰
/图片来自大话数据结构/北京大学出版社

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/138222.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • H264解码流程

    H264解码流程H264解码过程比较复杂,这里仅简要概述大致流程如果是非黑即白的二值图像,不压缩的情况下一个像素只需要1个bit。如果是256种状态的灰度图像,不压缩的情况下一个像素需要8bit(1字节,256种状态)。如果用256种状态标识屏幕上某种颜色的灰度,而屏幕采用三基色红绿蓝(RGB),不压缩的情况下一个像素需要占用24bit(3字节),这个就是常说的24位真彩色。…

  • 计算机组成原理实验移位运算,移位运算实验

    计算机组成原理实验移位运算,移位运算实验《移位运算实验》由会员分享,可在线阅读,更多相关《移位运算实验(4页珍藏版)》请在人人文库网上搜索。1、计算机组成原理实验报告姓名吕翠学号专业计算机科学与技术班级08级师范汉班联系电话Emailqq.com同组实验者梁瑞实验室名称计算机组成原理实验室实验日期2010年10月19日课程名称计算机组成原理实验序号二实验项目移位运算实验主讲教师侯宏霞辅导教师侯…

  • 字符串匹配——枚举法[通俗易懂]

    字符串匹配——枚举法[通俗易懂]字符串匹配——枚举法给定主串T和模式串P,返回P在T中首次出现的位置,如果P不存在于T中,返回-1。这样的问题就是字符串匹配问题,这里先给出枚举法的思想。设主串T的长度为n,模式串P的长度为m。主串从0到n-m,每次选取连续的m个字符,跟模式串P的m个字符进行一一比较。伪代码BruteForce(T,P)01fors<-0ton-m02j<-003//check

  • java标识符可以$开头吗_JAVA标识符

    java标识符可以$开头吗_JAVA标识符JAVA标识符JAVA标识符简介Java语言中,对于变量,常量,函数,语句块也有名字,我们统统称之为Java标识符。也就是程序员在定义java程序时,自定义的一些名字,例如helloworld程序里关键字class后跟的Demo,就是我们定义的类名。类名就属于标识符的一种。标识符除了应用在类名上,还可以用在变量、函数名、包名上。(要求同学们先记住,以后会详细见到这些)。标识符命名规则1.标识符由…

  • 使用CSS画一个三角形

    使用CSS画一个三角形使用CSS画一个三角形

  • python如何设置窗口背景色为白色_pycharm怎么将背景颜色设置成白色?「建议收藏」

    python如何设置窗口背景色为白色_pycharm怎么将背景颜色设置成白色?「建议收藏」方法:1、在pycharm中,点击顶部的“文件”选项;2、点击“设置”按钮,进入设置页面;3、点击“编辑器”选项,再点击“颜色&字体”选项;4、点击“控制台的颜色”选项,在右侧的“scheme”菜单中,选择“default”选项,点击确定即可。pycharm背景颜色设置成白色的方法1、如果没有安装pycharm可以先进行安装,安装完成之后我们点击桌面的pycharm图标进入首页。2、进入之…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号