C++で高さhのバランスの取れた二分木を数える

二分木の高さHが与えられます。目標は、指定された高さのバランスの取れたバイナリツリーの数/数を見つけることです。

二分木 −は、各ノードに最大2つの子（左の子と右の子）を持つツリーデータ構造です。

高さバランスのとれた二分木 −は、すべてのノードの2つのサブツリーの深さが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の場合、つまりノードが1つしかない場合は、ノードが1つだけのツリーが1つだけ存在し、バランスが取れています。 （if（h ==1）、return 1）

• それ以外の場合、高さは、ルートより1つまたは2つ低い高さの左右のサブツリーの合計です。 （バランスの取れた木は、高さの差が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