首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
高度为5的平衡二叉树最少需要多少个节点
[单选题]
高度为5的平衡二叉树最少需要多少个节点
10
9
11
12
其他都不对
查看答案及解析
添加笔记
求解答(6)
邀请回答
收藏(42)
分享
纠错
4个回答
添加回答
4
adfsgkkjkj
平衡二叉树
(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
最小二叉平衡树的节
点的公式如下 F(n)=F(n-1)+F(n-2)
+1 这个类似于一个递归的数列,可以参考Fibonacci数列,1是根节点,F(n-1)是左子树的节点数量,F(n-2)是右子树的节点数量。
其中F(2) = 2, F(1) = 1;
故而:
F(5)
= 3F(2) + 2F(1) + 4 = 12.
发表于 2019-03-30 00:43:47
回复(0)
1
马丘
设f(n)为高度为n的平衡二叉树最少含有的节点数,则:f(1) = 1;f(2) = 2; f(3) = 4;f(4) = 7;……
这些可以通过画图就能得到,但是当n很大时呢?其实有如下结论:f(n) = f(n-1) + f(n-2) +1,(n>=3)。这个递推结论如何得到的呢?
————————————————
版权声明:本文为CSDN博主「w57w57w57」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:
https://blog.csdn.net/w57w57w57/article/details/5921598
发表于 2020-04-12 15:45:37
回复(0)
0
Offer正在向你奔来
F(h+2)-1
1,1,2,3,5,8,13
发表于 2019-03-29 21:38:55
回复(0)
0
Kumori
动态规划,f(1)=1,f(2)=2
f(n)=f(n-1)+f(n-2)+1
f(5)=f(4)+f(3)+1
f(3)=4
f(4)=7
f(5)=4+7+1=12
发表于 2018-12-11 18:39:42
回复(3)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
C++工程师
iOS工程师
快手
安卓工程师
运维工程师
前端工程师
算法工程师
测试工程师
PHP工程师
2019
游戏研发工程师
Java工程师
上传者:
小小
难度:
4条回答
42收藏
6551浏览
热门推荐
相关试题
若要尽可能地完成对实数数组的排序,...
Java工程师
C++工程师
iOS工程师
安卓工程师
运维工程师
前端工程师
算法工程师
PHP工程师
测试工程师
快手
2019
评论
(4)
(verbal)最近的研究显示,许...
言语理解与表达
2019
普华永道
人力资源
审计
税务服务
风险管理
管理咨询
行政管理
评论
(3)
来自
职能类模拟题14
下面关键字中,哪一个不是用于异常处...
哔哩哔哩
游戏研发工程师
2020
评论
(1)
分页系统的逻辑地址结构是一维的,分...
操作系统
评论
(1)
关于分段系统与分页系统的区别,描述...
操作系统
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题