一棵完全二叉树上有1001个结点,其中叶子结点的个数是

 我来答
梨花菏雨
2018-11-11 · TA获得超过227个赞
知道答主
回答量:41
采纳率:0%
帮助的人:1.3万
展开全部

首先,一楼回答是正确的,我来给他通俗一下,使它的回答更容易理解。

答:想象着对完全二叉树进行编号(从1开始,从上到下,从左到右)。

完全二叉树中第一个非叶子结点的编号=树中最后一个节点的编号 / 2

第一个非叶子结点编号为2,即非叶子节点有两个。那么,叶子节点个数 = 总节点个数 - 非叶子结点个数    3 = 5 - 2;

题目: 叶子结点 = 1001 - 1001  /  2 = 501

百度网友0ebcc3a
推荐于2018-01-14 · TA获得超过606个赞
知道答主
回答量:30
采纳率:100%
帮助的人:2万
展开全部
n = n。+ n1 + n2
( 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
本回答被网友采纳
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
chiconysun
2015-12-23 · TA获得超过2.2万个赞
知道大有可为答主
回答量:5410
采纳率:92%
帮助的人:2606万
展开全部
设二叉树中度为0的叶子结点个数为n0,度为1结点个数为n1,度为2结点个数为n2,于是n0 + n1 + n2 = 1001
根据二叉树性质:n0 = n 2 + 1,代入得到,2n2 + 1+ n1 = 1001
由于完全二叉树的n1 只能是0或者1,为满足2n2 + 1 + n1 = 1001,n1 =0,因此n2 = 500
所以n0 = 501,即叶子个数是501个
本回答被网友采纳
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
H爱不绝迹
2018-03-31 · TA获得超过7.6万个赞
知道大有可为答主
回答量:60
采纳率:85%
帮助的人:3.9万
展开全部

完全二叉树性质可知,若给每个结点依次序标上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 层所有的结点都连续集中在最左边,这就是完全二叉树。

本回答被网友采纳
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
944826941
2023-10-05 · TA获得超过1141个赞
知道小有建树答主
回答量:95
采纳率:100%
帮助的人:14.6万
展开全部
换种思路:
跟这个同一深度的满二叉树的结点数为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,感谢下面的朋友提醒,现在改过来了,笑哭)
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
收起 更多回答(13)
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式