二叉树的基本性质及证明

二叉树的基本性质及证明性质1:一棵非空二叉树的第i层上最多有2^(i-1)个结点,(i>=1)。性质2:一棵深度为k的二叉树中,最多具有2^k-1个结点,最少有k个结点。性质3:对于一棵非空的二叉树,度为0的结点(即叶子结点)总比度为1的结点多一个,即叶子结点数为n0,度为2的结点数为n2,则有n0=n2+1。证明:如果n0表示度为0(即叶子结点)的结点数,用n1表示度为1的结点数,n2表示度为2的结点数,

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

性质1:一棵非空二叉树的第i层上最多有2^(i-1)个结点,(i>=1)。

性质2:一棵深度为k的二叉树中,最多具有2^k-1个结点,最少有k个结点。

性质3:对于一棵非空的二叉树,度为0的结点(即叶子结点)总比度为1的结点多一个,即叶子结点数为n0,度为2的结点数为n2,则有n0=n2+1。

证明:如果n0表示度为0(即叶子结点)的结点数,用n1表示度为1的结点数,n2表示度为2的结点数,n表示整个完全二叉树的结点总数,则有n=n0+n1+n2,根据二叉树和树的性质,可知n=n1+2xn2+1(所有结点的度数之和加1等于结点总数),根据两个等式可知n0+n1+n2=n1+2xn2+1,即n2=n0-1,也即n0=n2+1。

性质4:具有n个结点的完全二叉树深度为(log2(n))+1。

证明:根据性质2,深度为k的二叉树,最多有2^k-1个结点,且完全二叉树的定义是与同深度的满二叉树前边的编号相同,即它们的结点总数n位于k层和k-1层的满二叉树容量之间,即2^(k-1)-1< n <=2^k-1之间,或2^(k-1) <= n <2^k,两边同时取对数得,k-1<=log2(n)<k,又因层数为整数,故log2(n)=k-1,即k=log2(n)+1。

性质5:对具有n个结点的完全二叉树,如果按照从上至下和从左至右的顺序对二叉树的所有结点从1开始编号,则对于任意的序号为i的结点有:

如果i>1,那么序号为i的结点的双亲结点序号为i/2;

如果i=1,那么序号为i的结点为根节点,无双亲结点;

如果2i<=n,那么序号为i的结点的左孩子结点序号为2i;

如果2i>n,那么序号为i的结点无左孩子;

如果2i+1<=n,那么序号为i的结点右孩子序号为2i+1;

如果2i+1>n,那么序号为i的结点无右孩子。

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

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

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

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

(0)


相关推荐

  • uml的什么模型图由活动图顺序图状态图和协作图组成_uml9种图

    uml的什么模型图由活动图顺序图状态图和协作图组成_uml9种图uml是程序员需要掌握一个重要工具,特别在研究hadoop(http://www.iigrowing.cn/hadoop)系统中,有很多相关的uml图形需要绘制,为了方便大家了解uml,在网络上找了些uml方面的文章(http://www.iigrowing.cn/?s=uml)在参考资料中,在uml参考资料中缺少活动图方面的介绍,因此特地在网络上寻找了一些资料,然后整理成一篇文章,供大家参考,水…

  • python aes ecb_python简单加密

    python aes ecb_python简单加密前言AES加密的模式有很多种,下面来介绍ECB模式的加密解密importbase64fromCrypto.CipherimportAESclassAESECB:def__init

  • 一种成熟的MODBUS调试测试工具助手上位机软件(MThings) 免费中文

    一种成熟的MODBUS调试测试工具助手上位机软件(MThings) 免费中文一种成熟的MODBUS调试测试工具助手软件(MThings)免费中文现有MODBUS调测软件种类丰富,基本可以满足日常调测需求,但是面对用户群体对高效灵活友好的进一步需求都存在着差距。MThings是一款全新的标准化MODBUS调测工具,提供主从机一体化操作。全功能覆盖MODBUSPollSlave,功能全网最强。

  • phantomjs入门使用

    phantomjs入门使用PhantomJS是一个命令行工具。确保您熟悉命令提示符或PowerShell(在Windows上)或终端(在macOS和Linux上)的使用。这个指令假设PhantomJS已经安装并放置在路径的某个地方(例如,Windows用户请参阅本教程)。官网:https://phantomjs.org/中文网:http://wenku.kuryun.com/docs/phantomjs/index.html一、下载地址:https://phantomjs.org/download.html选择对应操

  • Groovy新手教程

    Groovy新手教程

    2021年11月29日
  • SimpleDateFormat 常用用法[通俗易懂]

    SimpleDateFormat 常用用法[通俗易懂]1、SimpleDateFormat函数语法:G年代标志符y年M月d日h时在上午或下午(1~12)H时在一天中(0~23)m分s秒S毫秒E星期D一年

发表回复

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

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