การแจงนับต้นไม้ไบนารีใน C++

การแจงนับของไบนารีทรี กำลังนับจำนวนรวมของต้นไม้ไบนารีที่ไม่มีป้ายกำกับชัดเจนในขนาดที่กำหนด (จำนวนโหนดที่ระบุ) ในบทความนี้ เราจะสร้างโปรแกรมเพื่อนับจำนวน Binary Trees ของ n nodes

ตามการติดฉลากของโหนดของไบนารีทรี มีสองประเภท:

• ต้นไม้ไบนารีที่มีป้ายกำกับ
• ต้นไม้ไบนารีที่ไม่มีป้ายกำกับ

ต้นไม้ไบนารีที่มีป้ายกำกับ: เป็นไบนารีทรีที่โหนดของต้นไม้มีป้ายกำกับด้วยค่า

ประเภทที่แตกต่างกันของต้นไม้ไบนารีที่มีป้ายกำกับสำหรับจำนวนโหนดที่กำหนด :

จำนวนโหนด N =2

ในทำนองเดียวกัน เราสามารถหาจำนวนของไบนารีทรีที่มีป้ายกำกับชัดเจนสำหรับจำนวนโหนด N

N =1 นับ =1

N =2 นับ =4
N =3 นับ =30

N =4 นับ =336

ในที่นี้ เราจะเห็นได้ว่าโหนดที่ติดป้ายกำกับแต่ละโหนดมีการจัดเรียงทุกประเภทที่ทำขึ้นสำหรับโหนดที่ไม่มีป้ายกำกับ ดังนั้นการนับจะเป็น n! * จำนวนต้นไม้ไบนารีที่ไม่มีป้ายกำกับ

C(N) =น! * ( (2n!) / (n+1)! * n! ) )

โปรแกรมแสดงจำนวนไบนารีทรีที่ไม่ระบุชื่ออย่างชัดเจนสำหรับจำนวนโหนดที่กำหนด N

ตัวอย่าง

#include <iostream>
using namespace std;

int fact(int n){
   if(n == 1)
      return 1;
   return n * fact(n - 1);
}

int distinctCountLabeledTree(int N){
   return ( (fact(N))*( fact(2*N) / ( fact(N+1)*fact(N)) ) ) ;
}

int main(){
   
   int N = 6;
   cout<<"The number of Distinct labeled Binary Tree is "<<distinctCountLabeledTree(N);
   return 0;
}

ผลลัพธ์ -

The number of Distinct labeled Binary Tree is 95040

ต้นไม้ไบนารีที่ไม่มีป้ายกำกับ: เป็นไบนารีทรีซึ่งโหนดของต้นไม้ไม่มีป้ายกำกับด้วยค่า

ต้นไม้ไบนารีที่ไม่มีป้ายกำกับชนิดต่างๆ สำหรับจำนวนโหนดที่กำหนด:

จำนวนโหนด N =2

จำนวนของต้นไม้ไบนารีที่ไม่มีป้ายกำกับชัดเจน =2

ในทำนองเดียวกัน เราสามารถหาจำนวนของต้นไม้ไบนารีที่ไม่มีป้ายกำกับชัดเจนสำหรับ N.

N =1 นับ =1
N =2 นับ =2
N =3 นับ =5
N =4 นับ =14

เมื่อใช้สิ่งนี้ เราสามารถกำหนดจำนวนของไบนารีทรีที่ไม่มีป้ายกำกับที่ชัดเจนสำหรับโหนด N

มันถูกกำหนดโดยหมายเลขคาตาลัน

สูตรอื่นก็ได้

C(N) =(2n!) / (n+1)! * n!

โปรแกรมค้นหาจำนวนไบนารีทรีที่ไม่ติดป้ายกำกับสำหรับจำนวนโหนดที่กำหนด N

ตัวอย่าง

#include <iostream>
using namespace std;

int fact(int n){
   if(n == 1)
      return 1;
   return n * fact(n - 1);
}

int distinctCount(int N){
   return ( fact(2*N) / ( fact(N+1)*fact(N) ) );
}

int main(){
   
   int N = 7;
   cout<<"The number of Distinct unlabeled Binary Tree is "<<distinctCount(N);
   return 0;
}

ผลลัพธ์ -

The number of Distinct unlabeled Binary Tree is 6