Para árboles binarios: No hay necesidad de considerar los valores de nodo de árbol, solo estoy interesado en diferentes topologías de árbol con nodos 'N'.Con 'N' no de nodos, ¿cuántos árboles de búsqueda binarios y binarios diferentes son posibles?
Para árbol de búsqueda binaria: Tenemos que considerar los valores de nodo de árbol.
Recomiendo this article por mi colega Nick Parlante (desde atrás cuando todavía estaba en Stanford). El recuento de árboles binarios estructuralmente diferentes (problema 12) tiene una solución recursiva simple (que en forma cerrada termina siendo la fórmula catalana que ya se mencionó en la respuesta de @codeka).
no estoy seguro de cómo el número de estructuras diferentes binarios de búsqueda árboles (BSTs para abreviar) sería diferente de la de los árboles binarios "simple" - excepto que, si por "considerar valores de nodo de árbol" que quiere decir que cada nodo puede ser, por ejemplo cualquier número compatible con la condición BST, luego el número de diferentes (pero no todos estructuralmente diferentes! -) BSTs es infinito. Dudo que lo diga, entonces, por favor aclare lo que haga significa con un ejemplo!
Eric Lippert recientemente tuvo una serie muy profunda de publicaciones en el blog sobre esto: "Every Binary Tree There Is" y "Every Tree There Is" (más algunos más después de eso).
En respuesta a su pregunta específica, que dice:
El número de árboles binarios con n nodos está dada por la Catalan numbers, que tienen muchas propiedades interesantes. ¡El enésimo número catalán está determinado por la fórmula (2n)!/(n + 1)! n !, que crece exponencialmente.
(2n)!/n!*(n+1)!
diferentes árboles binarios con n nodos:
(1/(n+1))*(2nCn)
donde C = combinación por ejemplo.
n=6,
possible binary trees=(1/7)*(12C6)=132
The number of possible binary search tree with n nodes (elements,items) is
=(2n C n)/(n+1) = (factorial (2n)/factorial (n) * factorial (2n - n))/(n + 1)
where 'n' is number of nodes (elements,items)
Example :
for
n=1 BST=1,
n=2 BST 2,
n=3 BST=5,
n=4 BST=14 etc
total no de los árboles binarios son = 
Sumando sobre i da el número total de árboles de búsqueda binaria con n nodos. 
El caso base es t (0) = 1 y t (1) = 1, es decir, hay una BST vacío y no es una BST con un nodo. 
Por lo tanto, en general, puede calcular el número total de árboles de búsqueda binaria utilizando la fórmula anterior. Me hicieron una pregunta en Google entrevista relacionada con esta fórmula. La pregunta fue cuántos total de árboles de búsqueda binaria son posibles con 6 vértices.Así respuesta es t (6) = 132
Creo que he dado una idea ...
Tenga en cuenta que 1 y 2 son en realidad formas diferentes de expresar la misma fórmula, no fórmulas para cantidades diferentes, en caso de que no sea clara. – TOB
@Black_Rider - Probé la fórmula anterior para calcular el no. de árboles posibles para 100 nodos únicos. Pero está fallando. Usé DP para resolver el problema. Puede encontrar el código [aquí] (https://github.com/dineshappavoo/ctgi/blob/master/src/com/ctgi/google/problems/MaximumPossibleWaysOfBST.java). La respuesta es incorrecta. La respuesta esperada es 25666077 pero la salida real es 7159379471982673992. ¿Podrían ayudarme en esto? – Dany
El número de árboles binarios se puede calcular utilizando la catalan number.
El número de árboles de búsqueda binarios se puede ver como una solución recursiva. es decir, número de árboles de búsqueda binaria = (Número de izquierda búsqueda binaria sub-árboles) * (Número de derecha binarios de búsqueda sub-árboles) * (maneras de elegir la raíz)
En un BST, solo importa el orden relativo entre los elementos. Entonces, sin ninguna pérdida en la generalidad, podemos suponer que los elementos distintos en el árbol son 1, 2, 3, 4, ...., n. Además, permita que el número de BST esté representado por f (n) para n elementos.
Ahora tenemos los casos múltiples para elegir la raíz.
...... mismo modo, para i-ésimo elemento como la raíz, i-1 elementos pueden ser de la izquierda y n-i a la derecha.
Estos sub-árboles son en sí BST, por lo tanto, podemos resumir la fórmula como:
f (n) = f (0) f (n-1) + f (1) f (n -2) + .......... + f (n-1) f (0)
casos base, f (0) = 1, ya que no es exactamente 1 manera de hacer una BST con 0 nodos. f (1) = 1, ya que hay exactamente 1 forma de hacer una BST con 1 nodo.
Si se les da ninguna. de Nodos son N Entonces.
diferente número de BST = Catalán (N)
diferente número de estructuras diferentes árboles binarios son = Catalán (N)
diferente número de árboles binarios son = N! * Catalán (N)
árbol binario:
No hay necesidad de considerar los valores, tenemos que mirar la estructura.
dado por (2 potencia n) - n
Ej: para tres nodos que es (2 POWER 3) -3 = 8-3 = 5 structrues diferentes
árbol binario de búsqueda:
Tenemos que considerar incluso los valores de nodo. Lo llamamos como número catalán
Dado por 2n C n/n + 1
Alex, Gracias asignar. – siva
Recomiendo este artículo, que aborda muy bien este problema y describe el enfoque utilizando la recursión, así como la programación dinámica. Contar árboles de búsqueda binarios creados a partir de N elementos únicos http://techieme.in/count-binary-search-trees/ – dharam
la solución proporcionada aquí http://cslibrary.stanford.edu/110/BinaryTrees.html # 12 doesn No coincide con la solución proporcionada por calculado por número catalán. Eso es countTres (4) debe ser 5 no 14, ¿verdad? Pero devuelve 14. (Esta es la serie 1, 1, 2, 5, 14, 42, 132) – Joyce