首页 > 试题广场 >

⼀个完全⼆叉树中有330个叶子节点, 则在该⼆叉树中的节点

[单选题]
 ⼀个完全⼆叉树中有330个叶子节点, 则在该⼆叉树中的节点个数为（）？ 
  • 659
  • 660
  • 可能为659或者660
  • 不可能为659和660
查看正确选项
添加回答
Ethan520头像 Ethan520
前端怎么会有这种题
发表于 2018-08-19 07:00:06 回复(1)
不为取名烦恼头像 不为取名烦恼
完全二叉树除最后一层外都是满的，所以也可以这么算：第一层1个节点，令层数为n，除最后一层外，每层的节点个数为2^(n-1)，有330个叶子节点，所以倒数第二层为第9层，有256个节点，256+x=330得x=74,所以共有1+2+4+8+16+32+64+128+256+74*2=659个节点，又因为第659个节点是右子节点，所以节点个数也可以是660
发表于 2018-08-19 09:53:02 回复(0)
sincebreeze头像 sincebreeze
因为二叉树度为2的结点n2和叶子结点存在n0：n0=n2+1的关系，所以度为2的结点个数为329，又因为完全二叉树可能存在度为1的结点，所以结点个数为：330+329=659或330+329+1=660.
发表于 2018-08-19 14:40:54 回复(1)
顺风先森头像 顺风先森
二叉树的性质有一条:n0=n2+1。叶子节点度为0，所以n0=330,n2=329。又因为度为1的节点最多只能有一个，所以n1只能为0或者1。二叉树节点总数n=n0+n1+n2，所以n=660或者n=659
发表于 2018-09-17 09:35:16 回复(0)
你电瓶车头像 你电瓶车
背错公式了，hh
公式：
n0 + n1 + n2 = n;
n - 1 = 2*n2 + n1;
假设n为偶数：则有
n1 = 1;
n = 660;
假设n为奇数：则有
n1 = 0;
n = 659;


发表于 2019-08-13 16:47:53 回复(0)
后起之秀201807130946900头像 后起之秀201807130946900
完全二叉树解法一般都要考虑节点和度，应用公式既可以解决
发表于 2018-08-20 10:31:00 回复(0)
tim@washflow头像 tim@washflow
330 + 330 / 2 + (330/2/2) ....
最后得值在659和660之间
发表于 2018-08-17 11:51:43 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 商汤科技 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 技术支持 数据挖掘工程师 2018 产品 运营 大数据开发工程师 Java工程师
上传者：小小
难度：
7条回答 6564浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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