資料結構
網路
關係型資料庫管理系統
作業系統
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 瀏覽量
廣告