事业单位考试计算机基础知识:二叉树的基本特性(1)
【导语】在事业单位考试中,计算机专业知识的复习向来是考生复习备考阶段的一大重点,其中中公事业单位考试网为计算机基础知识的复习为考生提供知识点梳理,帮助考生备考!
性质1:
在二叉树的第i层上至多有2i-1个结点。(i≥1)
证明:用归纳法证明之
①i=1时,只有一个根结点,2i-1=20=1是对的;
②假设对所有j(1≤jj-1个结点
那么,第i-1层至多有2i-2个结点
又二叉树每个结点的度至多为2
所以第i层上最大结点数是第i-1层的2倍,即2×2i-2=2i-1
故命题得证
例题
试求有n个叶结点的非满的完全二叉树的高度?
【解析】设完全二叉树中叶子结点数为n,则根据完全二叉树的性质,度为2的结点数是n-1,而完全二叉树中,度为1的结点数至多为1,所以具有n个叶子结点的完全二叉树结点数是n+(n-1)+1=2n或2n-1(有或无度为1的结点)。由于具有2n(或2n-1)个结点的完全二叉树的深度是[log2(2n)]+1([log2(2n-1)]+1,即[log2n]+1,故n个叶结点的非满的完全二叉树的高度是[log2n]+1。(最下层结点数>=2)。
以上是中公事业单位考试网为考生梳理计算机基础知识点,供大家学习识记!
更多相关信息请访问事业单位考试资料网
欢迎关注(中公教育事业单位招聘考试频道)
及时掌握事业单位招聘考试信息
回复“2022”领取备考大礼包
声明:本站点发布的来源标注为“中公教育”的文章,版权均属中公教育所有,未经允许不得转载。
如果对你有帮助的话,就点个赞吧!





