首页 > 试题广场 >

若 一棵完全二叉树有 768 个结点，则该二叉树中叶结点的个

[单选题]

若 一棵完全二叉树有 768 个结点，则该二叉树中叶结点的个数是 

  • 257
  • 258
  • 384
  • 385
查看正确选项
添加回答
梅老板的粉头像 梅老板的粉
完全二叉树的一个容易被忽略的特点，即度为1的结点的个数至多为1，因此，我们进行下列推导：
假设二叉树中度为0的结点个数为n0，度为1的结点个数为n1，度为2的结点个数为n2,
于是总结点数n = n0+n1+n2,同时，每一个度为2的节点都指向2个结点，每一个度为1的结点指向1个节点，而仅仅只有根结点1个没有结点指向它，于是总结点数n = 1+n1+2*n2,综合上面两个式子，我们可以得到n2 = n0-1
再结合完全二叉树的特点n0+n1+n0-1 = 768, 即2n0+n1=769,显然，这里必须让n1为1，得到n0的值为384。
编辑于 2017-06-16 22:41:24 回复(2)
此广告位出租头像 此广告位出租
不抓住这个点：任何一颗二叉树，若其终端结点数为n0，度为1的结点数为n2，则n0=n2+1，就很难能把题理清楚。
先假设本题的二叉树只有叶子结点(数量为n)和度为2的结点，那么n+n-1=768，但是n不为整数，所以这个二叉树存在度为1的结点，因为这是完全二叉树，所以它只会有1个度为1的结点，我们先给它补全右子结点，这是共有769个结点，使用n+n-1=769，计算得出n=385，减去刚才增加额那一叶子结点，所以该叔有384个叶子结点。
编辑于 2017-08-11 20:26:59 回复(0)
Mastema头像 Mastema
对于结点数为n的完全二叉树，其叶子结点个数为 n / 2（取上整）
发表于 2019-08-22 10:15:41 回复(2)
喵大人喵喵喵头像 喵大人喵喵喵

根据完全二叉树的性质，最后一个分支结点的序号为 ë n/2 û = ë 768/2 û =384 ，故叶子结点的个数为 768-384=384 。

【另解 1 】 由二叉树的性质 n=n0+n1+n2 和 n0=n2+1 可知， n=2n0 - 1+n1 ，及 2n0 - 1+n1=768 ，显然 n1=1 ， 2n0=768 ，则 n0=384 。

【另解 2 】 完全二叉树的叶子结点只可能出现在最下两层，由题可计算完全二叉树的高度为 10 。第 10 层的叶子结点数为 768 - ( 29 - 1)=257 ；第 10 层的叶子结点在第 9 层共有 é 257/2 ù =129 个父结点 ，第 9 层的叶子结点数为 ( 29 - 1) - 129=127 ，则叶子结点的总数为 257+127=384 。

发表于 2017-05-17 03:17:18 回复(0)
April丶头像 April丶
二叉树的性质之一，n0=n2+1;
因此，n0+n2为奇数，题中结点数为768，所以存在一个度为1的结点。减去度为1的结点之后结点数为767个。
故，n0+n2=n2+n2+1=2n2+1=767，解得n2为383，n0为384.
所以选C，384
发表于 2017-09-28 18:31:10 回复(1)
Fengzhi志头像 Fengzhi志
记住这个性质：n0=n2+1解决这道题非常简单，而且n0+n2的结果一定是奇数！
发表于 2018-03-16 09:55:01 回复(0)
提交观点

问题信息

树
上传者：喵大人喵喵喵
难度：
6条回答 9072浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号