เราได้รับความสูง H ของต้นไม้ไบนารี เป้าหมายคือการหาจำนวนต้นไม้ไบนารีที่สมดุล (Balanced Binary Trees) ที่เป็นไปได้ตามความสูงที่กำหนด
ต้นไม้ไบนารี (Binary Tree) - เป็นโครงสร้างข้อมูลแบบต้นไม้ที่แต่ละโหนดมีลูกได้สูงสุดสองตัว คือ ลูกซ้ายและลูกขวา
ต้นไม้ไบนารีที่สมดุลตามความสูง (Height-balanced Binary Tree) - ถูกกำหนดว่าเป็นต้นไม้ไบนารีที่ความลึกของสองต้นไม้อย่อยของทุกโหนดต่างกันได้สูงสุด 1 นั่นคือ ความสูงของต้นไม้อย่อยซ้ายและขวาทุกโหนดมีความต่างสูงสุด 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) รับความสูงและคืนจำนวนต้นไม้ไบนารีที่สมดุลที่เป็นไปได้
- ใช้วิธีเรียกซ้ำ (Recursive):
- ถ้าความสูงเป็น 1 (มีโหนดเดียว) จะมีต้นไม้เพียงต้นเดียวที่สมดุล (if h==1 return 1)
- อื่นๆ ความสูงจะเป็นผลรวมของต้นไม้อย่อยซ้ายและขวาที่มีความสูงต่างจากรูท 1 หรือ 2 (เพราะต้นไม้สมดุลต่างกันได้สูงสุด 1)
- ฟังก์ชันคืนค่าจำนวนเป็นผลลัพธ์
โค้ดตัวอย่าง
#include <iostream>
int countBTheight(int h) {
// มีต้นไม้ 1 ต้นสำหรับความสูง 0 หรือ 1
if (h == 0 || h == 1)
return 1;
return countBTheight(h-1) * (2 * countBTheight(h-2) + countBTheight(h-1));
}
int main() {
int H = 4;
cout << "Count of balanced binary trees of height H is: " << countBTheight(H);
}
ผลลัพธ์
Count of balanced binary trees of height H is: 315
