นับต้นไม้ไบนารีที่สมดุลสูง h ใน 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), return 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