二叉树的五个性质「建议收藏」

二叉树的五个性质「建议收藏」性质1:在二叉树的第i层上最多有2^(i-1)个结点(i≥1)。第一层是根结点,只有一个,所以2(1-1)=20=1。第二层有两个,2(2-1)=21=2。第三层有四个,2(3-1)=22=4。第四层有八个,2(4-1)=2^3=8。性质2:深度为k的二叉树至多有2^k-1个结点(k≥1)。注意这里一定要看清楚,是2k后再减去1,而不是2(k-1)。以前很多同学不能完全理解,这样去记忆,就容易把性质2与性质1给弄混淆了。深度为k意思就是有k层的二叉树,我们先来看看简单的。如果有一层,至多1=

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

性质1:在二叉树的第i层上最多有2^(i-1)个结点(i≥1)。

第一层是根结点,只有一个,所以2(1-1)=20=1。 第二层有两个,2(2-1)=21=2。 第三层有四个,2(3-1)=22=4。 第四层有八个,2(4-1)=2^3=8。

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

注意这里一定要看清楚,是2k后再减去1,而不是2(k-1)。以前很多同学不能完全理解,这样去记忆,就容易把性质2与性质1给弄混淆了。 深度为k意思就是有k层的二叉树,我们先来看看简单的。 如果有一层,至多1=21-1个结点。 如果有二层,至多1+2=3=22-1个结点。 如果有三层,至多1+2+4=7=23-1个结点。 如果有四层,至多1+2+4+8=15=2^4-1个结点。

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

终端结点数其实就是叶子结点数,而一棵二叉树,除了叶子结点外,剩下的就是度为1或2的结点数了,我们设n1为度是1的结点数。则树T结点总数n=n0+n1+n2
终端结点数其实就是叶子结点数,而一棵二叉树,除了叶子结点外,剩下的就是度为1或2的结点数了,我们设n1为度是1的结点数。则树T结点总数n=n0+n1+n2 。

二叉树性质4:具有n个结点的完全二叉树的深度为|log(2^n)+1|

由满二叉树的定义我们可以知道,深度为k的满二叉树的结点数n一定是2k-1。因为这是最多的结点个数。那么对于n=2k-1倒推得到满二叉树的深度为k=log2(n+1),比如结点数为15的满二叉树,深度为4。

二叉树性质5:如果对一棵有n个结点的完全二叉树(其深度为|log(2^n)+1|)的结点按层序编号(从第一层到第层,每层从左到右),对任一结点i(1<=i<=n),有

1.如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲是结点。
2.如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i。
3.如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1

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

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

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

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

(0)


相关推荐

  • JVM内存分配与管理详解

    JVM内存分配与管理详解概述了解C++的程序员都知道,在内存管理领域,都是由程序员维护与管理,程序员用于最高的管理权限,但对于java程序员来说,在内存管理领域,程序员不必去关心内存的分配以及回收,在jvm自动内存管理机制的帮助下,不需要想C++一样为每一个new操作去编写delete/free代码,这一切交给jvm,但正是这一切都交给了jvm,一旦出现内存泄漏与溢出,如果不了jvm,那么对于程序的编写与调试将会非常

  • C#的一些关键字的总结

    C#的一些关键字的总结

  • Matlab中的数据预处理-归一化(mapminmax)与标准化(mapstd)

    Matlab中的数据预处理-归一化(mapminmax)与标准化(mapstd)最近遇到数据预处理的一些问题,本来很简单的东西,但是却搞的烦烦的,痛定思痛,决定自己实现一下。一、mapminmaxProcessmatricesbymappingrowminimumandmaximumvaluesto[-11]意思是将矩阵的每一行处理成[-1,1]区间,此时对于模式识别或者其他统计学来说,数据应该是每一列是一个样本,每一行是多个样本的同一维,即

  • sql的日期格式化「建议收藏」

    sql的日期格式化「建议收藏」sql的日期格式化转化1.DATE_FORMAT()函数用于以不同的格式显示日期/时间数据。DATE_FORMAT(date,format)%a 缩写星期名%b 缩写月名%c 月,数值%D 带有英文前缀的月中的天%d 月的天,数值(00-31)%e 月的天,数值(0-31)%f 微秒%H 小时(00-23)%h 小时(01-12)%I 小时(01-12)%i 分钟,数值(00-59)%j 年的天(001-366)%k 小时(0-23)%l 小时(1-12)

  • python3 三种字符串(无前缀,前缀u,前缀b)与encode()「建议收藏」

    python3 三种字符串(无前缀,前缀u,前缀b)与encode()「建议收藏」假设读者已经了解了什么叫字符集,什么叫编码,什么叫解码。首先要明确,虽然有三种前缀(无前缀,前缀u,前缀b),但是字符串的类型只有两种(str,bytes),实验如下:根据程序以及以上运行结果,发现无前缀,和前缀u,构造出来的字符串常量,是一样的。类型一样是str,长度一样是3,==判断也是返回true。其实,这里是因为,python3中,字符串的存储方式都是以Unicode字符…

  • 自然语言处理之词袋模型Bag_of_words

    自然语言处理之词袋模型Bag_of_words文章目录读取训练数据BeautifulSoup处理获取词袋和向量预测结果使用随机森林分类器进行分类输出提交结果尝试使用xgb还是随机森林好用教程地址:https://www.kaggle.com/c/word2vec-nlp-tutorial/overview/part-1-for-beginners-bag-of-words读取训练数据训练数据的内容是2500条电影评论。impor…

发表回复

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

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