Cuente el número de árboles binarios posibles para una determinada longitud de secuencia de preorden n.
Ejemplos:
Input : n = 1 Output : 1 Input : n = 2 Output : 2 Input : n = 3 Output : 5
Fondo :
En Preorder traversal , primero procesamos el Node raíz, luego recorremos el Node secundario izquierdo y luego el Node secundario derecho.
Por ejemplo, el recorrido de pedido anticipado del árbol a continuación es 1 2 4 5 3 6 7
Encontrar el número de árboles con Preorder dado:
Número de árboles binarios posibles si se proporciona tal longitud transversal (digamos n).
Tomemos un ejemplo : Secuencia de preorden dada -> 2 4 6 8 10 (longitud 5).
- Suponga que solo hay 1 Node (es decir, 2 en este caso), por lo que solo es posible 1 árbol binario
- Ahora, suponga que hay 2 Nodes (es decir, 2 y 4), por lo que solo son posibles 2 árboles binarios:
- Ahora, cuando hay 3 Nodes (es decir, 2, 4 y 6), entonces el árbol binario posible es 5
- Considere 4 Nodes (que son 2, 4, 6 y 8), por lo que el árbol binario posible es 14.
Digamos que BT (1) denota el número de árbol binario para 1 Node. (Suponemos BT(0)=1)
BT(4) = BT(0) * BT(3) + BT(1) * BT(2) + BT(2) * BT(1) + BT(3) * BT(0)
BT(4) = 1 * 5 + 1 * 2 + 2 * 1 + 5 * 1 = 14 - Del mismo modo, considerando todos los 5 Nodes (2, 4, 6, 8 y 10). El número posible de árbol binario es:
BT(5) = BT(0) * BT(4) + BT(1) * BT(3) + BT(2) * BT(2) + BT(3) * BT(1) ) + BT(4) * BT(0)
BT(5) = 1 * 14 + 1 * 5 + 2 * 2 + 5 * 1 + 14 * 1 = 42
Por lo tanto, el árbol binario total para la secuencia de pedido anticipado de longitud 5 es 42.
Usamos programación dinámica para calcular el número posible de árboles binarios. Tomamos un Node a la vez y calculamos los árboles posibles usando árboles calculados previamente.
C++
// C++ Program to count possible binary trees
// using dynamic programming
#include <bits/stdc++.h>
using namespace std;
int countTrees(int n)
{
// Array to store number of Binary tree
// for every count of nodes
int BT[n + 1];
memset(BT, 0, sizeof(BT));
BT[0] = BT[1] = 1;
// Start finding from 2 nodes, since
// already know for 1 node.
for (int i = 2; i <= n; ++i)
for (int j = 0; j < i; j++)
BT[i] += BT[j] * BT[i - j - 1];
return BT[n];
}
// Driver code
int main()
{
int n = 5;
cout << "Total Possible Binary Trees are : "
<< countTrees(n) << endl;
return 0;
}
Java
// Java Program to count
// possible binary trees
// using dynamic programming
import java.io.*;
class GFG
{
static int countTrees(int n)
{
// Array to store number
// of Binary tree for
// every count of nodes
int BT[] = new int[n + 1];
for(int i = 0; i <= n; i++)
BT[i] = 0;
BT[0] = BT[1] = 1;
// Start finding from 2
// nodes, since already
// know for 1 node.
for (int i = 2; i <= n; ++i)
for (int j = 0; j < i; j++)
BT[i] += BT[j] *
BT[i - j - 1];
return BT[n];
}
// Driver code
public static void main (String[] args)
{
int n = 5;
System.out.println("Total Possible " +
"Binary Trees are : " +
countTrees(n));
}
}
// This code is contributed by anuj_67.
Python3
# Python3 Program to count possible binary
# trees using dynamic programming
def countTrees(n) :
# Array to store number of Binary
# tree for every count of nodes
BT = [0] * (n + 1)
BT[0] = BT[1] = 1
# Start finding from 2 nodes, since
# already know for 1 node.
for i in range(2, n + 1):
for j in range(i):
BT[i] += BT[j] * BT[i - j - 1]
return BT[n]
# Driver Code
if __name__ == '__main__':
n = 5
print("Total Possible Binary Trees are : ",
countTrees(n))
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C#
// C# Program to count
// possible binary trees
// using dynamic programming
using System;
class GFG
{
static int countTrees(int n)
{
// Array to store number
// of Binary tree for
// every count of nodes
int []BT = new int[n + 1];
for(int i = 0; i <= n; i++)
BT[i] = 0;
BT[0] = BT[1] = 1;
// Start finding from 2
// nodes, since already
// know for 1 node.
for (int i = 2; i <= n; ++i)
for (int j = 0; j < i; j++)
BT[i] += BT[j] *
BT[i - j - 1];
return BT[n];
}
// Driver code
static public void Main (String []args)
{
int n = 5;
Console.WriteLine("Total Possible " +
"Binary Trees are : " +
countTrees(n));
}
}
// This code is contributed
// by Arnab Kundu
PHP
<?php
// PHP Program to count possible binary
// trees using dynamic programming
function countTrees($n)
{
// Array to store number of Binary
// tree for every count of nodes
$BT[$n + 1] = array();
$BT = array_fill(0, $n + 1, NULL);
$BT[0] = $BT[1] = 1;
// Start finding from 2 nodes, since
// already know for 1 node.
for ($i = 2; $i <= $n; ++$i)
for ($j = 0; $j < $i; $j++)
$BT[$i] += $BT[$j] *
$BT[$i - $j - 1];
return $BT[$n];
}
// Driver code
$n = 5;
echo "Total Possible Binary Trees are : ",
countTrees($n), "\n";
// This code is contributed by ajit.
?>
Javascript
<script>
// Javascript Program to count
// possible binary trees
// using dynamic programming
function countTrees(n)
{
// Array to store number
// of Binary tree for
// every count of nodes
let BT = new Array(n + 1);
for(let i = 0; i <= n; i++)
BT[i] = 0;
BT[0] = BT[1] = 1;
// Start finding from 2
// nodes, since already
// know for 1 node.
for (let i = 2; i <= n; ++i)
for (let j = 0; j < i; j++)
BT[i] += BT[j] * BT[i - j - 1];
return BT[n];
}
let n = 5;
document.write("Total Possible " + "Binary Trees are : " + countTrees(n));
</script>
Producción:
Total Possible Binary Trees are : 42
Complejidad temporal: O(n 2 )
Espacio Auxiliar : O(n)
Alternativa:
¡ Esto también se puede hacer usando el número catalán Cn = (2n)!/(n+1)!*n!
Para n = 0, 1, 2, 3,… los valores de los números catalanes son 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,…. También lo son los números de árboles binarios de búsqueda .
Este artículo es una contribución de Shubham Rana . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA