資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中二叉樹的列舉
二叉樹的列舉是指計算給定大小（特定數量的節點）的不同無標記二叉樹的總數。在這篇文章中，我們將建立一個程式來計算n個節點的二叉樹的數量。
根據二叉樹節點的標記，它分為兩種型別
- 標記二叉樹
- 無標記二叉樹
標記二叉樹：它是一個二叉樹，其中樹的節點用值標記。
給定節點數的不同型別的標記二叉樹
節點數 N = 2
類似地，我們可以找到N個節點的不同標記二叉樹的數量，
N = 1, 數量 = 1
N = 2, 數量 = 4
N = 3, 數量 = 30
N = 4, 數量 = 336
在這裡，我們可以看到對於每個標記的節點，都進行了無標記節點的所有型別的排列。因此，計數將是n! * 無標記二叉樹的數量。
C(N) = 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
更新於：2021年1月22日
384 次瀏覽
廣告