一棵完全二叉树上有1001个结点,其中叶子结点的个数是
( n: 总结点个数
n。:无孩纸的结点个数(即叶子结点)
n1:有一个孩纸的结点个数
n2:有两个孩纸的结点个数
结点要么有两个孩纸,要么一个,要么没有)
由完全二叉树性质可知,若给每个结点依次序标上1~n序号,序号为 i 的结点(假设有两个孩纸存在)其左孩纸序号为 2i(皆为偶数),右孩纸序号为 2i + 1 (皆为奇数)
故 1001 为右孩子,其父结点序号为 500 ( 2i + 1 = 1001 解得 i = 500 )
故n2 = 500 (按规律501的孩纸序号应为501 * 2 = 1002 和 1003, 此题一共只有1001个结点,故501 没有孩纸)
n1要么为 0 要么为 1 ,奇数个结点时为最后一个叶子结点为右孩纸,偶数个结点时最后一个为左孩纸
此时 n1 = 0 (1001是右孩纸)
n = n。+ n1 + n2
1001 = n。+ 0 + 500
n。= 501
根据二叉树性质:n0 = n 2 + 1,代入得到,2n2 + 1+ n1 = 1001
由于完全二叉树的n1 只能是0或者1,为满足2n2 + 1 + n1 = 1001,n1 =0,因此n2 = 500
所以n0 = 501,即叶子个数是501个
由完全二叉树性质可知,若给每个结点依次序标上1~n序号,序号为 i 的结点(假设有两个孩纸存在)其左孩纸序号为 2i(皆为偶数),右孩纸序号为 2i + 1 (皆为奇数),故 1001 为右孩子,其父结点序号为 500 ( 2i + 1 = 1001 解得 i = 500 ),故n2 = 500 (按规律501的孩纸序号应为501 * 2 = 1002 和 1003, 此题一共只有1001个结点,故501 没有孩纸),n1要么为 0 要么为 1 ,奇数个结点时为最后一个叶子结点为右孩纸,偶数个结点时最后一个为左孩纸。
具体如下:
1、简介
完全二叉树的定义、性质以及算法见正文。这里补充一点:完全二叉树是效率很高的数据结构,堆是一种完全二叉树或者近似完全二叉树,所以效率极高,像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化,几乎每次都要考到的二叉排序树的效率也要借助平衡性来提高,而平衡性基于完全二叉树。
2、判断完全二叉树
完全二叉树:叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
3、完全二叉树定义
若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
跟这个同一深度的满二叉树的结点数为1023,其中最后一行512个
而这个1001个少了22个,少在了最后一行,所以这缺失的22个的父结点都是叶子,共22/2=11个
而这一行剩下512-22 = 490个叶子,
所以总共490+11=501个叶子结点
或者直接想"原本应该度为2的22个结点变成了叶子结点相当于少了22/2个叶子结点"所以512-22/2 = 501
(第一次回答的时候答案算错了512-22/2=490,感谢下面的朋友提醒,现在改过来了,笑哭)