首页 > 常见问题 > 完全二叉树的叶子节点数

完全二叉树的叶子节点数

步履不停
发布: 2019-06-20 14:06:24
原创
17803 人浏览过

完全二叉树的叶子节点数

一个具有n个节点的完全二叉树,其叶子节点的个数n0为: n/2 向上取整,或者(n+1)/2 向下取整

扩展资料:

完全二叉树

完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

定义

若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

(1)所有的叶结点都出现在第k层或k-l层(层次最大的两层)

(2)对任一结点,如果其右子树的最大层次为L,则其左子树的最大层次为L或L+l。

一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树,并且最下层上的结点都集中在该层最左边的若干位置上,而在最后一层上,右边的若干结点缺失的二叉树,则此二叉树成为完全二叉树。

更多常见问题的相关技术文章,请访问常见问题栏目进行学习!

以上是完全二叉树的叶子节点数的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
来源:php.cn
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
作者最新文章
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板