设为首页 - 加入收藏
广告 1000x90
您的当前位置:78345黄大仙救世网挂牌 > 结点 > 正文

告诉了一棵完全二叉树的总结点个数求叶子结点个数怎么计算?谢谢

来源:未知 编辑:admin 时间:2019-06-25

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  由于第十层的叶子结点是从第九层延伸的,所以应该去掉第九层中还有子树的结点。

  所以,第九层的叶子结点个数是256-94=162,加上第十层有188个,最后结果是350个。

  一棵深度为k,且有2^k-1个节点的二叉树,称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中,除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点,则此二叉树为完全二叉树。

  具有n个节点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树,至少有2k-1个叶子节点,至多有2k-1个节点。

  完全二叉树有一个性质: 具有n个结点的完全二叉树的深度为log2n(2是下标)+1。

  10层满二叉树的总结点数为1023,最后一层的结点数应该是2的9次方为512,所以肯定699个结点肯定不是满二叉树。。。叶子节点出现在最后两层上。。。

  不确定有没有算对。。。大概思路应该是这样的。。。希望对你有帮助。。。。仍有问题可以HI我。。。。

  在任意一棵二叉树中,叶子结点比度为2的结点多一个,完全二叉树中最多有一个度为1的结点,所以有如下结论:

  设一棵完全二叉树有N个结点.如果N为偶数,则在该二叉树中有N/2个叶子结点以及N/2-1个度为2的结点,还有一个是度为1的结点,如果N为奇数,则在该二叉树中有(N/2)+1个叶子结点以及(N/2)个度为2的结点,没有度为1的结点~

  假设n0是度为0的结点总数(即叶子结点数),n1是度为1的结点总数,n2是度为2的结点总数,由二叉树的性质可知:n0=n2+1,则n= n0+n1+n2(其中n为完全二叉树的结点总数),由上述公式把n2消去得:n= 2n0+n1-1,由于完全二叉树中度为1的结点数只有两种可能0或1,由此得到n0=(n+1)/2或n0=n/2,合并成一个公式:n0=(n+1)/2 ,就可根据完全二叉树的结点总数计算出叶子结点数。

本文链接:http://anicburst.com/jiedian/352.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top