二叉树性质及证明「建议收藏」

二叉树性质及证明「建议收藏」二叉树性质及证明(1)规定根节点层次为0,则一棵非空二叉树的第i层上最多有2i个结点。(2)规定根节点层次为0,则深度为k的二叉树的最大结点数为2(k+1)-1。(3)具有n个结点的完全二叉树的深度k为不超过lb(n+1)-1的最大整数。(4)对于一棵非空二叉树,如果叶节点个数为n0,度为2的结点数为n2,则有n0=n2+1。(5)对于具有n个结点的完…

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

二叉树性质及证明

  • (1)规定根节点层次为0,则一棵非空二叉树的第i层上最多有2i个结点。
  • (2)规定根节点层次为0,则深度为k的二叉树的最大结点数为2(k+1)-1。
  • (3)具有n个结点的完全二叉树的深度k为不超过lb(n+1)-1的最大整数。
  • (4)对于一棵非空二叉树,如果叶节点个数为n0,度为2的结点数为n2,则有n0=n2+1。
  • (5)对于具有n个结点的完全二叉树,按上下左右顺序对结点从0编号,则对于序号为i的结点有:
+ 如果i>0,则i的双亲序号为(i-1)/2 (/为整除)

+ 如果2*i+1<n,则序号为i结点的左孩子为2*i+1,若大于n,则无左孩子

+ 如果2*i+2<n,则序号为i结点的右孩子为2*i+2,若大于n,则无右孩子

证明:

  • (1)根据二叉树的特点,每个结点可分至多两个叉,规律可寻,即得2i。

  • (2)深度为k的二叉树所有最大结点个数,即满二叉树时,根据(1)每层结点相加,得2(k+1)-1。

  • (3)根据(2),n个结点必然大于深度为其上一层结点数,小于等于同等深度满二叉结点数,即
    2k-1<n<=2k+1-1 移项,两边取2的对数,得 k<lb(n+1)<=k+1

  • (4)二叉树只有0,1,2度结点所以n=n0+n1+n2

    二叉树的进入分支数,即有双亲的结点数除去根节点 M=n-1

    二叉树的发出结点数,1度发出1个,2度发出2。 可有M=n1+2*n2

    综上可移项得n0=n2+1

  • (5)对于性质5,可举例图示,按序号代替具体数值

              0
    
        1           2
    
      3    4     5     6 
    
    7    8
    

   1号在其层上索引为0,2号在其层索引为1。 同理3号在其层索引为0,5号其层索引为2 。因为二叉树分二叉的特点 可知按照各自本层索引有关系 y=2*x x为双亲层索引 y为孩子层索引。

   那么只需求得各自层内索引即可,因为按顺序编号,所以各自层索引就是 结点的二叉树索引减去除去本层的结点总数即

  2*(i-(2k-1)=j-(2k-1) 移项 i为双亲结点号,j为左孩子结点号 ,

  得左孩子结点索引j=2*i+1 。

  同理 右孩子j=2*i+2 ,双亲 (i-1)/2

  
  PS:根据性质5 我们就可以用一维数组存储二叉树了,可以索引并修改。 对于性质的应用,举例:哈夫曼编码,总结点数为2*n0-1,有兴趣自行推导

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

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

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

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

(0)


相关推荐

  • 银行家算法详解(C语言)

    银行家算法详解(C语言)概述银行家算法是荷兰学者Dijkstra为银行系统设计的,以确保银行在发放现金贷款时,不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中,用于避免死锁核心思想:在进程提出资源申请时,先预判此分配是否会导致系统进入不安全状态。如果会进入不安全状态,就暂时不答应这次请求,让该进程先阻塞等待。过程演示图解假定有五个进程{P0,P1,P2,P3,P4}和三类资源{A,B,C},各种资源的数量分别为10、5、7。在T0时刻的资源分配情况如下T0时刻的安全性P1发出请求向量Request1(1,

  • 服务器iscsi存储挂载_redis查询命令

    服务器iscsi存储挂载_redis查询命令当前包含磁盘[root@xifenfei~]#fdisk-lDisk/dev/sda:21.4GB,21474836480bytes255heads,63sectors/track,2610cylindersUnits=cylindersof16065*512=8225280bytesDeviceBootStartEnd…

  • poj 1146

    poj 1146题目链接:http://poj.org/problem?id=1146此题求所给字符串按字典序的下一个由原串字母排列的串,题目不难,开始看错了,wrong一次#include<stdio.h>#include<stdlib.h>#include<string.h>intmain(intargc,char**argv){…

  • 参数化(三):参数嗅探

    参数化(三):参数嗅探

    2021年11月26日
  • 使用谷歌搜索攻略_Google浏览器

    使用谷歌搜索攻略_Google浏览器由于谷歌被封,无法使用谷歌搜索。但是对于研发人员来说,很多问题只有在谷歌中才能找到答案。后来一朋友推荐了archsocks代理服务1、访问https://github.com/archsocks/archsocks链接,下载windows版本安装。 如果没有,附件中有安装文件2、按照readme中的操作步骤来操作。 3、配置pac代理。 首先打开网络网络和共享中…

  • 网络编程初识和socket套接字[通俗易懂]

    网络的产生不同机器上的程序要通信,才产生了网络:凡是涉及到倆个程序之间通讯的都需要用到网络软件开发架构软件开发架构的类型:应用类、web类应用类:qq、微信、网盘、优酷这一类是属于需要安装的桌

发表回复

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

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