二叉树2 – 数据结构和算法44

二叉树2

让编程改变世界

Change the world by program

二叉树的性质

二叉树的性质一:在二叉树的第i层上至多有2^(i-1)个结点(i>=1)

这个性质其实很好记忆,考试的时候懂得画出二叉树的图便可以推出

宽客网,量化投资,宽客俱乐部

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

这里一定要看清楚哦,是2^k再-1,老方法理解!

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

这个就比较困难了,需要推导获得

首先我们再假设度为1的结点数为n1,则二叉树T的结点总数n=n0+n1+n2

其次我们发现连接数总是等于总结点数n-1,并且等于n1+2*n2

所以n-1=n1+2*n2

所以n0+n1+n2-1=n1+n2+n2

最后n0=n2+1

二叉树的性质四:具有n个结点的完全二叉树的深度为?log?n?+1

涉及到一些数学知识了,专门针对要考试的学生,只为学编程的路过即可

由满二叉树的定义结合性质二我们知道,深度为k的满二叉树的结点树n一定是2^k-1

那么对于满二叉树我们可以通过n=2^k-1倒推得到满二叉树的深度为k=log?(n+1)

由于完全二叉树前边我们已经提到,它的叶子结点只会出现在最下面的两层,我们可以同样如下推导

那么对于倒数第二层的满二叉树我们同样很容易回推出它的结点数为n=2^(k-1)-1

所以完全二叉树的结点数的取值范围是:2^(k-1)-1

由于n是整数,n

同理2^(k-1)-1

所以2^(k-1)

不等式两边同时取对数,得到k-1

由于k是深度,必须取整,所以k=?log?n?+1

二叉树的性质五:如果对一棵有n个结点的完全二叉树(其深度为?log?n?+1)的结点按层序编号,对任一结点i(1

如果i = 1,则结点 i 是二叉树的根,无双亲;如果i > 1,则其双亲是结点?i/2?

如果2i > n,则结点 i 无做左孩子(结点 i 为叶子结点);否则其左孩子是结点2i

如果2i+1 > n,则结点 i 无右孩子;否则其右孩子是结点2i+1

文字描述太折腾,直接看图听小甲鱼分析:

宽客网,量化投资,宽客俱乐部

视频下载

备用视频下载
技术, IT技术, 数据结构和算法, 结点

风险提示及免责条款

市场有风险,投资需谨慎。本文不构成个人投资建议,也未考虑到个别用户特殊的投资目标、财务状况或需要。用户应考虑本文中的任何意见、观点或结论是否符合其特定状况。据此投资,责任自负。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场,不承担相关法律责任。如若转载,请注明出处。 如若内容造成侵权/违法违规/事实不符,请点击下方“内容举报”进行投诉反馈!
立即
投稿

微信公众账号

微信扫一扫加关注

返回
顶部