本文概述
- C++
- Java
- Python3
- C#
- PHP
对于n = 0、1、2、3, ..., 加泰罗尼亚语值的值为1、1、2、5、14、42、132、429、1430、4862...。二叉搜索树的数目也是如此。
具有n个不同密钥的可能二叉树总数(countBT(n))= countBST(n)* n!
下面的代码用于查找具有n个数字的BST和二叉树的计数。查找第n个加泰罗尼亚语代码的代码取自这里.
C++
//See https://www.lsbin.org/program-nth-catalan-number/
//for reference of below code.#include <
bits/stdc++.h>
using namespace std;
//A function to find factorial of a given number
unsigned long int factorial(unsigned int n)
{
unsigned long int res = 1;
//Calculate value of [1*(2)*---*(n-k+1)] /[k*(k-1)*---*1]
for ( int i = 1;
i <
= n;
++i)
{
res *= i;
}return res;
}unsigned long int binomialCoeff(unsigned int n, unsigned int k)
{
unsigned long int res = 1;
//Since C(n, k) = C(n, n-k)
if (k>
n - k)
k = n - k;
//Calculate value of [n*(n-1)*---*(n-k+1)] /[k*(k-1)*---*1]
for ( int i = 0;
i <
k;
++i)
{
res *= (n - i);
res /= (i + 1);
}return res;
}//A Binomial coefficient based function to find nth catalan
//number in O(n) time
unsigned long int catalan(unsigned int n)
{
//Calculate value of 2nCn
unsigned long int c = binomialCoeff(2*n, n);
//return 2nCn/(n+1)
return c/(n+1);
}//A function to count number of BST with n nodes
//using catalan
unsigned long int countBST(unsigned int n)
{
//find nth catalan number
unsigned long int count = catalan(n);
//return nth catalan number
return count;
}//A function to count number of binary trees with n nodes
unsigned long int countBT(unsigned int n)
{
//find count of BST with n numbers
unsigned long int count = catalan(n);
//return count * n!
return count * factorial(n);
}//Driver Program to test above functions
int main()
{int count1, count2, n = 5;
//find count of BST and binary trees with n nodes
count1 = countBST(n);
count2 = countBT(n);
//print count of BST and binary trees with n nodes
cout<
<
"Count of BST with " <
<
n<
<
" nodes is " <
<
count1<
<
endl;
cout<
<
"Count of binary trees with " <
<
n<
<
" nodes is " <
<
count2;
return 0;
}Java
//See https://www.lsbin.org/program-nth-catalan-number/
//for reference of below code.
import java.io.*;
class GFG
{//A function to find
//factorial of a given number
static int factorial( int n)
{
int res = 1 ;
//Calculate value of
//[1*(2)*---*(n-k+1)] /
//[k*(k-1)*---*1]
for ( int i = 1 ;
i <
= n;
++i)
{
res *= i;
}return res;
}static int binomialCoeff( int n, int k)
{
int res = 1 ;
//Since C(n, k) = C(n, n-k)
if (k>
n - k)
k = n - k;
//Calculate value of
//[n*(n-1)*---*(n-k+1)] /
//[k*(k-1)*---*1]
for ( int i = 0 ;
i <
k;
++i)
{
res *= (n - i);
res /= (i + 1 );
}return res;
}//A Binomial coefficient
//based function to find
//nth catalan number in
//O(n) time
static int catalan( int n)
{//Calculate value of 2nCn
int c = binomialCoeff( 2 * n, n);
//return 2nCn/(n+1)
return c /(n + 1 );
}//A function to count number of
//BST with n nodes using catalan
static int countBST( int n)
{
//find nth catalan number
int count = catalan(n);
//return nth catalan number
return count;
}//A function to count number
//of binary trees with n nodes
static int countBT( int n)
{
//find count of BST
//with n numbers
int count = catalan(n);
//return count * n!
return count * factorial(n);
}//Driver Code
public static void main (String[] args)
{
int count1, count2, n = 5 ;
//find count of BST and
//binary trees with n nodes
count1 = countBST(n);
count2 = countBT(n);
//print count of BST and
//binary trees with n nodes
System.out.println( "Count of BST with " +
n + " nodes is " +
count1);
System.out.println( "Count of binary " +
"trees with " +
n + " nodes is " +
count2);
}
}//This code is contributed by ajitPython3
# See https:#www.lsbin.org/program-nth-catalan-number/
# for reference of below code. # A function to find factorial of a given number
def factorial(n) :
res = 1# Calculate value of [1*(2)*---*
#(n-k+1)] /[k*(k-1)*---*1]
for i in range ( 1 , n + 1 ):
res * = i
return res def binomialCoeff(n, k): res = 1# Since C(n, k) = C(n, n-k)
if (k>
n - k):
k = n - k # Calculate value of [n*(n-1)*---*(n-k+1)] /
# [k*(k-1)*---*1]
for i in range (k): res * = (n - i)
res //= (i + 1 ) return res # A Binomial coefficient based function to
# find nth catalan number in O(n) time
def catalan(n):# Calculate value of 2nCn
c = binomialCoeff( 2 * n, n) # return 2nCn/(n+1)
return c //(n + 1 ) # A function to count number of BST
# with n nodes using catalan
def countBST(n):# find nth catalan number
count = catalan(n) # return nth catalan number
return count # A function to count number of binary
# trees with n nodes
def countBT(n):# find count of BST with n numbers
count = catalan(n) # return count * n!
return count * factorial(n) # Driver Code
if __name__ = = '__main__' :n = 5# find count of BST and binary
# trees with n nodes
count1 = countBST(n)
count2 = countBT(n) # print count of BST and binary trees with n nodes
print ( "Count of BST with" , n, "nodes is" , count1)
print ( "Count of binary trees with" , n, "nodes is" , count2)# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)C#
//See https://www.lsbin.org/program-nth-catalan-number/
//for reference of below code.
using System;
class GFG
{//A function to find
//factorial of a given number
static int factorial( int n)
{
int res = 1;
//Calculate value of
//[1*(2)*---*(n-k+1)] /
//[k*(k-1)*---*1]
for ( int i = 1;
i <
= n;
++i)
{
res *= i;
}return res;
}static int binomialCoeff( int n, int k)
{
int res = 1;
//Since C(n, k) = C(n, n-k)
if (k>
n - k)
k = n - k;
//Calculate value of
//[n*(n-1)*---*(n-k+1)] /
//[k*(k-1)*---*1]
for ( int i = 0;
i <
k;
++i)
{
res *= (n - i);
res /= (i + 1);
}return res;
}//A Binomial coefficient
//based function to find
//nth catalan number in
//O(n) time
static int catalan( int n)
{//Calculate value
//of 2nCn
int c = binomialCoeff(2 * n, n);
//return 2nCn/(n+1)
return c /(n + 1);
}//A function to count
//number of BST with
//n nodes using catalan
static int countBST( int n)
{
//find nth catalan number
int count = catalan(n);
//return nth catalan number
return count;
}//A function to count number
//of binary trees with n nodes
static int countBT( int n)
{
//find count of BST
//with n numbers
int count = catalan(n);
//return count * n!
return count * factorial(n);
}//Driver Code
static public void Main ()
{
int count1, count2, n = 5;
//find count of BST
//and binary trees
//with n nodes
count1 = countBST(n);
count2 = countBT(n);
//print count of BST and
//binary trees with n nodes
Console.WriteLine( "Count of BST with " +
n + " nodes is " +
count1);
Console.WriteLine( "Count of binary " +
"trees with " +
n + " nodes is " +
count2);
}
}//This code is contributed
//by akt_mitPHP
<
?php
//See https://www.lsbin.org/program-nth-catalan-number/
//for reference of below code.
//A function to find factorial
//of a given number
function factorial( $n )
{
$res = 1;
//Calculate value of
//[1*(2)*---*(n-k+1)] /
//[k*(k-1)*---*1]
for ( $i = 1;
$i <
= $n ;
++ $i )
{
$res *= $i ;
}return $res ;
}function binomialCoeff( $n , $k )
{
$res = 1;
//Since C(n, k) = C(n, n-k)
if ( $k>
$n - $k )
$k = $n - $k ;
//Calculate value of
//[n*(n-1)*---*(n-k+1)] /
//[k*(k-1)*---*1]
for ( $i = 0;
$i <
$k ;
++ $i )
{
$res *= ( $n - $i );
$res = (int) $res /( $i + 1);
}return $res ;
}//A Binomial coefficient
//based function to find
//nth catalan number in
//O(n) time
function catalan( $n )
{
//Calculate value of 2nCn
$c = binomialCoeff(2 * $n , $n );
//return 2nCn/(n+1)
return (int) $c /( $n + 1);
}//A function to count
//number of BST with
//n nodes using catalan
function countBST( $n )
{
//find nth catalan number
$count = catalan( $n );
//return nth
//catalan number
return $count ;
}//A function to count
//number of binary
//trees with n nodes
function countBT( $n )
{
//find count of
//BST with n numbers
$count = catalan( $n );
//return count * n!
return $count *
factorial( $n );
}//Driver Code
$count1 ;
$count2 ;
$n = 5;
//find count of BST and
//binary trees with n nodes
$count1 = countBST( $n );
$count2 = countBT( $n );
//print count of BST and
//binary trees with n nodes
echo "Count of BST with " , $n , " nodes is " , $count1 , "\n" ;
echo "Count of binary trees with " , $n , " nodes is " , $count2 ;
//This code is contributed by ajit
?>
输出如下：
Count of BST with 5 nodes is 42
Count of binary trees with 5 nodes is 5040枚举证明
考虑所有可能的二进制搜索树, 每个元素都位于根目录。如果有n个节点, 则对于每个根节点选择, 都会有n – 1个非根节点, 并且这些非根节点必须划分为小于选定根的节点和大于选定根的节点。 。
假设节点i被选为根。然后是i –比i小1个节点和n –比i大的i节点。对于这两组节点中的每一个, 都有一定数量的可能子树。
令t(n)为具有n个节点的BST总数。以i为根的BST总数为t(i – 1)t(n – i)。由于左和右子树中的排列是独立的, 所以这两个项相乘在一起。也就是说, 对于左树中的每个排列和右树中的每个排列, 你将获得一个以i为根的BST。
对i求和得出具有n个节点的二叉搜索树的总数。
文章图片
基本情况是t(0)= 1和t(1)= 1, 即有一个空的BST, 有一个BST和一个节点。
文章图片
文章图片
文章图片
同样, 关系countBT(n)= countBST(n)* n!持有。至于每个可能的BST, 都可以有n!二叉树, 其中n是BST中的节点数。
【可能的二叉搜索树和具有n个键的二叉树的总数】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。
推荐阅读
- 检查是否有可能以相等的总和划分k个子数组
- 对称和非对称密钥加密之间有什么区别（）
- C中char数据类型和char数组的大小
- Java计算list元素的出现次数
- 如何使用正则表达式检查字符串是否为字母数字（）
- 算法题（2的出现次数（从0到n的数字））
- 什么是信息安全（有什么特征？）
- 递归与迭代之间有什么区别（）
- PHP Spreadsheet_Excel_Writer setFgColor()函数用法