数据结构
网络
关系数据库管理系统 (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 次浏览
广告