programa en C ++ que encontrar el número de BSTs con N nodos (los números de Catalan)

Aquí, estamos implementando un programa C ++ para encontrar el número de BSTs con N nodos (números de Catalan) .

Planteamiento del problema: programa en C ++ para encontrar el número de árboles binarios de búsqueda con n nodos.

Formato de entrada: único entero n

restricciones: 0 = & lt; n & lt; = 15

de entrada de la muestra: 4

Resultado de muestra: 14 de búsqueda binaria árbol / árboles hay class 4 nodos

Problema explicación:

El número de BSTs con n vértices está dada por los números de Catalan. números for n = 0,1,2,3,4 … catalanes son 1,1,2,5,14 … y así sucesivamente.

números Catalan están dadas por Cn = (2n)! / (N + 1)! * N! = Recuento de BSTs con nodos n .

números catalanes se utilizan aquí para encontrar la cuenta de BSTs porque ambos satisfacen misma relación de recurrencia que es:

C++ program to find number of BSTs with N nodes (Catalan numbers) - 4

For n = 0 número de árboles es 1 decir árbol vacío. Los valores subsiguientes class:

C++ program to find number of BSTs with N nodes (Catalan numbers) - 5

Y así sucesivamente …

Solución:

Si consideramos raíz que la ITH nodo a continuación:

  1. i-1 nodos hay en subárbol izquierdo.
  2. n-i nodos hay en subárbol derecho.

recuento denotan Vamos de BST como Bn For n elementos

Los 2 subárboles aquí será independiente el uno del otro. Por lo tanto, será (B i-1 * B n-i) For Bi. class n nodos (como i tiene n opciones) que serán:

C++ program to find number of BSTs with N nodes (Catalan numbers) - 6

Puesto que la relación de recurrencia es el mismo que de los números de Catalan, por lo que contar de BST está dada por Cn.

Recurrencia relación:

C++ program to find number of BSTs with N nodes (Catalan numbers) - 7

Esto da complejidad O (4 ^ n). La complejidad puede ser reducida a O (n ^ 2) mediante el uso de DP.

implementación en C ++:

#include <iostream>
using namespace std;
int CN(int n){
int Cn =0;
// base case
if(n==0) // empty tree
{
return 1;
}
for(int i=1;i<n+1;i++)
{
Cn+= CN(i-1)*CN(n-i);
}
return Cn;
}
int main(){
int n;
cout<<"Enter number of nodes: ";
cin>>n;
cout<<n<<endl;
int trees=CN(n);
cout<<trees<<" binary search trees are there for "<<n<<" nodes"<<endl;
return 0;
}

salida

Enter number of nodes: 4
14 binary search trees are there for 4 nodes


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *