数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究给定高度，使用 C++ 计算 AVL 树中的最小节点数。
问题陈述
给定 AVL 树的高度，任务是找出该树可能具有的最小节点数。
If height = 0 then AVL tree can have one 1 node If height = 5 then AVL tree can have minimum 20 nodes
算法
在 AVL 树中，我们必须保持高度平衡属性，即每个节点的左右子树的高度差不能大于 -1、0 或 1。利用这个属性，我们可以创建以下递推关系：
1. If height = 0 then return 1 2. If height = 1 then return 2 3. If height > 1 then return (1 + getMinAVLNodes(h – 1) + getMinAVLNodes(h – 2))
示例
#include <iostream>
using namespace std;
int getMinAVLNodes(int h){
if (h < 0) {
return 0;
}
if (h == 0 || h == 1) {
return h + 1;
}
return 1 + getMinAVLNodes(h - 1) + getMinAVLNodes(h -2);
}
int main(){
int h = 5;
cout << "Minimum nodes for " << h << " height = " << getMinAVLNodes(h) << endl;
return 0;
}输出
编译并执行以上程序时，它会生成以下输出：
Minimum nodes for 5 height = 20
更新于：31-Oct-2019
262 浏览量
广告