二叉树性质总结

二叉树性质总结性质1:二叉树第i(i>=1)层上的节点数最多为2^(i-1)证明:归纳基础:第一层有一个节点,第二层最多有两个节点,第三层最多有四个节点,以此类推,数学归纳法证明如下:i=1时,2^(i-1)=2^0=1,因为第一层上为根节点,所以命题成立。归纳假设:假设对所有的j(1归纳步骤:根据归纳假设,第i-1层上至多有2(i-2)个节点,由于二叉树每个节点至多有两个孩子节点,所以第i

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

性质1:二叉树第i(i>=1)层上的节点数最多为2^(i-1)

证明:

归纳基础:第一层有一个节点,第二层最多有两个节点,第三层最多有四个节点,以此类推,数学归纳法证明如下:

i=1时,2^(i-1)=2^0=1,因为第一层上为根节点,所以命题成立。

归纳假设:假设对所有的j(1<=j<i)命题成立,即第j层上至多有2^(j-1)个节点,需要证明j=i时命题依然成立。

归纳步骤:根据归纳假设,第i-1层上至多有2(i-2)个节点,由于二叉树每个节点至多有两个孩子节点,所以第i层上的最多节点数是第i-1层上最多节点数的2倍,即j=i时,该层上最多有2^(i-2)*2=2^(i-1)个节点,因此命题成立。

性质2:高度为k的二叉树最多有2^k – 1个节点。

性质2可以根据性质1证明,即SUM(2^(i-1))(1<=i<=k)  =  2^k – 1(等比数列求和)

性质3:对于任何二叉树T,n0、n1、 n2分别代表度数为0、1、2的节点个数,则n0=n2+1

证明:因为二叉树所有节点的度数均不大于2,所以节点总数(记为n)应该等于0度节点数、1度节点数、2度节点数之和,即n0+n1+n2=n;

1度节点有一个儿子,2度节点有两个儿子,所以二叉树中所有儿子节点的个数是n1+n2,二叉树中只有根节点不是任何节点的儿子节点,因此二叉树中节点总数可以表示为n=n1+2n2+1

有上述两个公式n0+n1+n2=n、n=n1+2n2+1可得:n0=n2+1

性质4:具有n个节点的完全二叉树(包括满二叉树)的高度为[logn]+1(不做特殊说明这里的log都是以2为底的)

证明:设所求完全二叉树的深度为k,有完全二叉树的定义可知,其前k-1层是深度为k-1的满二叉树,一共有2^(k-1)-1个节点,由于完全二叉树深度为k,故第k蹭上还有若干节点,因此该完全二叉树的节点个数n>2^(k-1)-1。由性质2可知n<=2^k – 1,所以

2^(k-1) – 1< n <= 2^k-1

由此推导可得2^(k-1) <= n < 2^k,取对数后有

k-1 <= logn < k

因为k为整数,所以有k-1=logn,即可得k=[logn]+1

二叉树还具有其他性质,读者有兴趣可以自己推导得出,对以上四种性质比较常用,并且对于性质4在研究二叉树时间复杂度的时候可能会有所帮助理解nlogn这种时间复杂度的来源。

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

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

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

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

(0)


相关推荐

  • 51单片机实现流水灯

    51单片机实现流水灯文章目录51单片机实现流水灯一、点亮第一个LED灯二、流水灯1.总线型控制2.延时函数3._crol_函数使用4.实现流水灯51单片机实现流水灯以下是本篇文章正文内容,下面案例可供参考一、点亮第一个LED灯#include<reg52.h>#defineuintunsignedint//简化定义#defineucharunsignedchar//同上sbitD1=P2^1;voidmain(){ D1=0;}代码中D1代表着位定义,相.

  • plsql注册码永久可用_plsql登录不上怎么办

    plsql注册码永久可用_plsql登录不上怎么办2019独角兽企业重金招聘Python工程师标准>>>…

  • Pytorch的nn.Conv2d()详解

    Pytorch的nn.Conv2d()详解nn.Conv2d()的使用、形参与隐藏的权重参数in_channelsout_channelskernel_sizestride=1padding=0dilation=1groups=1bias=Truepadding_mode=’zeros’nn.Conv2d()的使用、形参与隐藏的权重参数  二维卷积应该是最常用的卷积方式…

  • 空洞骑士debug使用教程_debug调试汇编程序

    空洞骑士debug使用教程_debug调试汇编程序

    2022年10月15日
  • java8中的Collectors.groupingBy用法「建议收藏」

    java8中的Collectors.groupingBy用法「建议收藏」Collectors.groupingBy根据一个或多个属性对集合中的项目进行分组数据准备:publicProduct(Longid,Integernum,BigDecimalprice,Stringname,Stringcategory){ this.id=id; this.num=num; this.price=price; this.name=…

  • Python实现五子棋人机对战[通俗易懂]

    Python实现五子棋人机对战[通俗易懂]本文转载自数据札记倌,详情可以扫描下方二维码:五子棋是常见的一款小游戏,五子棋问题是人工智能中的一个经典问题。这篇文章主要介绍了python版本五子棋的实现代码,大家可以做个参考,与我的傻儿子对弈一下。简述虽然计算机已经几乎激活成功教程了五子棋的取胜秘籍,甚至给出了取胜的具体方案,然而,对人来说,五子棋还是非常有玩头的。我们往往有五子棋的技巧性和全局观远远比不上象棋,围棋之类的感觉:这个真不一定,先说技…

发表回复

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

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