# 可能的二叉搜索树和具有n个键的二叉树的总数

2021年4月15日19:06:05 发表评论 635 次浏览

## 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 ajit``````

## Python3

``````# 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_mit``````

## PHP

``````<?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``````