使用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