C++에서 높이 h의 균형 이진 트리 계산

이진 트리의 높이 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 또는 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