Per alberi binari: Non è necessario considerare i valori del nodo dell'albero, sono interessato solo a diverse topologie di alberi con nodi "N".Con "N" di nodi, quanti diversi alberi di ricerca binaria e binaria sono possibili?
Per albero di ricerca binario: Dobbiamo considerare i valori del nodo dell'albero.
Suggerisco il this article dal mio collega Nick Parlante (di ritorno quando era ancora a Stanford). Il conteggio di alberi binari strutturalmente diversi (problema 12) ha una semplice soluzione ricorsiva (che in forma chiusa finisce per essere la formula catalana che la risposta di @ codeka già menzionata).
io non sono sicuro di come il numero di strutturalmente differenti binari ricerca alberi (BST in breve) può essere diverso da quello di "semplici" alberi binari - eccetto che, se per "prendere in considerazione i valori dei nodi degli alberi" si intende che ogni nodo può essere eg qualsiasi numero compatibile con la condizione BST, quindi il numero di diversi (ma non tutti i strutturalmente diversi! -) BST è infinito. Dubito che tu voglia dire questo, quindi, per favore chiarisci cosa stai facendo con un esempio!
Eric Lippert ha recentemente pubblicato una serie molto approfondita di post di blog su questo argomento: "Every Binary Tree There Is" e "Every Tree There Is" (più alcuni altri dopo).
In risposta alla tua domanda specifica, egli dice:
Il numero di alberi binari con n nodi è data dalla Catalan numbers, che hanno molte proprietà interessanti. L'ennesimo numero di catalano è determinato dalla formula (2n)!/(n + 1)! n !, che cresce in modo esponenziale.
(2n)!/n!*(n+1)!
diversi alberi binari con n nodi:
(1/(n+1))*(2nCn)
dove C = combinazione es.
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
totale non di alberi binari sono = 
Sommando sui dà il numero totale di alberi binari di ricerca con n nodi. 
Il caso base è t (0) = 1 e t (1) = 1, cioè non v'è uno BST vuoto ed è presente un BST con un nodo. 
Quindi, in generale, si può calcolare non totale di alberi binari di ricerca che utilizzano sopra formula. Mi è stata posta una domanda in Google intervista relativa a questa formula. Domanda era il numero totale di alberi di ricerca binaria possibili con 6 vertici. Così risposta è t (6) = 132
penso che ti ho dato qualche idea ...
Si noti che 1 e 2 sono in realtà diversi modi di esprimere la stessa formula, non le formule per quantità diverse, nel caso in cui non fosse chiaro. – TOB
@Black_Rider - Ho provato la formula precedente per calcolare il no. di possibili alberi per 100 nodi unici. Ma sta fallendo. Ho usato DP per risolvere il problema. Puoi trovare il codice [qui] (https://github.com/dineshappavoo/ctgi/blob/master/src/com/ctgi/google/problems/MaximumPossibleWaysOfBST.java). La risposta è sbagliata. La risposta prevista è 25666077 ma l'output effettivo è 7159379471982673992. Potresti aiutarmi in questo? – Dany
Il numero di alberi binari può essere calcolata utilizzando l'catalan number.
Il numero di alberi di ricerca binaria può essere visto come una soluzione ricorsiva. cioè, numero di alberi binari di ricerca = (numero di Sinistra ricerca binaria sotto-alberi) * (Numero di destra sotto-alberi binari di ricerca) * (modi per scegliere la radice)
In un BST, solo l'ordine relativo tra gli elementi importa. Quindi, senza alcuna perdita di generalità, possiamo supporre che gli elementi distinti nell'albero siano 1, 2, 3, 4, ...., n. Inoltre, lascia che il numero di BST sia rappresentato da f (n) per n elementi.
Ora abbiamo i casi multipli per la scelta della radice.
...... Analogamente, per i-esimo elemento come radice, i-1 elementi possono essere a sinistra e n-i sulla destra.
Questi sotto-alberi sono stessa BST, quindi, possiamo riassumere la formula come:
f (n) = f (0) f (n-1) + f (1) f (n -2) + .......... + f (n-1) f (0)
casi Base, f (0) = 1, in quanto v'è esattamente 1 modo per fare un BST con 0 nodi. f (1) = 1, in quanto vi è esattamente 1 modo per creare un BST con 1 nodo.
Se dato alcuna. dei nodi sono N allora.
Diverso Numero BST = catalana (N)
Diverso Numero strutturalmente differenti alberi binari sono = catalano (N)
Diverso Numero di alberi binari sono = N! * Catalana (N)
albero binario:
Non c'è bisogno di considerare i valori, dobbiamo guardare lo structrue.
data da (2 potenza n) - n
Ad esempio: per tre nodi che è (2 Potenza 3) -3 = 8-3 = 5 diversi structrues
ricerca binaria albero:
Dobbiamo considerare anche i valori del nodo. Lo chiamiamo come numero catalano
Dato da 2n C n/n + 1
Alex, grazie assegnare. – siva
Raccomando questo articolo che affronta davvero questo problema e descrive l'approccio usando la ricorsione e la programmazione dinamica. Conteggio degli alberi di ricerca binaria creati da N elementi unici http://techieme.in/count-binary-search-trees/ – dharam
la soluzione fornita qui http://cslibrary.stanford.edu/110/BinaryTrees.html # 12 doesn abbinare la soluzione fornita calcolata dal numero di catalano. Questo è countTrees (4) dovrebbe essere 5 non 14, giusto? Ma restituisce 14. (Questa è la serie 1, 1, 2, 5, 14, 42, 132) – Joyce