資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中平衡二叉樹的數量
給定二叉樹的高度 H。目標是找到給定高度的平衡二叉樹的數量/計數。
二叉樹 - 是一種樹形資料結構，其中每個節點最多有兩個子節點，分別是左子節點和右子節點。
高度平衡二叉樹 - 定義為二叉樹，其中每個節點的兩個子樹的深度之差僅為 1 或 0。即每個節點的左子樹和右子樹的高度差最大為 1。
下圖包含了高度 h=3 的所有可能的平衡二叉樹。
輸入
Height H=2
輸出
Count of Balanced Binary Trees of Height H is : 3
解釋 - 給定圖包含了高度 H=2 的所有可能的平衡樹
輸入
Height H=3
輸出
Count of Balanced Binary Trees of Height H is : 15
下面程式中使用的思路如下
整數 H 用於表示二叉樹的高度。
函式 countBTheight(int h) 以樹的高度作為輸入，並返回高度為 h 的所有可能的平衡二叉樹的數量。
我們使用遞迴方法。
如果樹的高度為 1，即它只有一個節點，則只有一個具有單個節點的樹存在且它是平衡的。（if(h==1)，返回 1）
否則，高度是左子樹和右子樹的高度之和，其高度比根節點小一或二。（平衡樹的高度差為 1）。
函式返回計數作為結果。
示例
#include <iostream>
int countBTheight(int h){
// One tree is possible with height 0 or 1
if (h == 0 || h == 1)
return 1;
return countBTheight(h-1) * (2 *countBTheight(h-2) + countBTheight(h-1));
}
int main(){
int H = 4;
std::cout << "Count of balanced binary trees of height H is: "<<countBTheight(H);
}輸出
Count of balanced binary trees of height H is: 315
更新於: 2020-07-28
339 次瀏覽
廣告