首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
一颗完全二叉树的节点总数为2000,它的叶子节点数为:
[单选题]
一颗完全二叉树的节点总数为2000,它的叶子节点数为:
977
985
993
1000
查看答案及解析
添加笔记
求解答(0)
邀请回答
收藏(22)
分享
纠错
1个回答
添加回答
2
一笑而过2222
下面简单说说二叉树相关关系推导: 1. 二叉树边数和节点数关系:除根节点外每个节点有一条边指向它,设边数为e,节点总数为n,则e = n - 1。 2. 边的产生:边由度为1和度为2的节点产生,度为1的节点引出1条边,度为2的节点引出2条边。设度为1节点数为n1,度为2节点数为n2,所以e = n1 + 2n2。 3. 由e = n - 1和e = n1 + 2n2,可得n - 1 = n1 + 2n2。 4. 节点总数组成:节点总数n由叶子节点数n0、度为1节点数n1、度为2节点数n2组成,即n = n0 + n1 + n2。 5. 把n = n0 + n1 + n2代入n - 1 = n1 + 2n2,化简后得n0 = n2 + 1,即二叉树中叶子节点数比度为2的节点数多1。 6. 完全二叉树情况: - 若总节点数n是奇数,度为1节点数n1 = 0。把n1 = 0和n0 = n2 + 1代入n = n0 + n1 + n2,得出n0 = (n + 1) / 2。 - 若总节点数n是偶数,度为1节点数n1 = 1。把n1 = 1和n0 = n2 + 1代入n = n0 + n1 + n2,得出n0 = n / 2。 这样就推出了完全二叉树中叶子节点数和总节点数的关系。
发表于 2025-03-07 15:23:33
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
树
来自:
2023年4399游戏...
难度:
1条回答
22收藏
1314浏览
热门推荐
相关试题
从树中查找元素的时间复杂度不可能为:
树
评论
(1)
来自
2023年4399游戏秋...
HTTP和FTP协议属于OSI网络...
网络基础
评论
(1)
来自
2023年4399游戏秋...
IP地址172.16.11.110...
网络基础
评论
(1)
来自
2023年4399游戏秋...
评论
(0)
来自
2023年4399游戏秋...
关于进程状态(State)跳转,以...
操作系统
评论
(1)
来自
2023年4399游戏秋...
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题