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

二叉树的五个性质「建议收藏」性质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)


相关推荐

发表回复

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

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