С " N " нет узлов, сколько различных двоичных и двоичных деревьев поиска возможно?

1. всего нет двоичных деревьев=

2. суммирование по i дает общее количество двоичных деревьев поиска с n узлами.

базовый случай T(0) = 1 и t (1) = 1, т. е. есть один пустой BST и есть один BST с одним узлом.

таким образом, в общем случае вы можете вычислить общее количество деревьев двоичного поиска, используя приведенную выше формулу. Мне задали вопрос в Google интервью связано по этой формуле. Вопрос был в том, сколько всего нет бинарных деревьев поиска возможно с 6 вершинами. Поэтому ответ t (6) = 132

Я думаю, что я дал вам некоторые идеи...

количество двоичных деревьев можно вычислить с помощью количество каталанский.

число бинарных деревьев поиска можно рассматривать как рекурсивное решение. т. е. количество двоичных деревьев поиска = (количество левый двоичный поиск поддеревьев) * (количество право двоичный поиск поддеревьев) * (способы выбора корня)

в BST имеет значение только относительное упорядочение между элементами. Таким образом, без каких-либо потерь на общность, мы можем предположим, что различные элементы в дереве являются 1, 2, 3, 4, ...., n. Кроме того, пусть число BST будет представлено f (n) для n элементов.

теперь у нас есть несколько вариантов для выбора корня.

1. выбрать 1 как root, нет элемент может быть вставлен в левое поддерево. n-1 элементы будут вставлены в правом поддереве.
2. выбрать 2 как root, 1 элемент может быть вставляется в левое поддерево. n-2 элементы могут быть вставлены в правом поддереве.
3. выбрать 3 как root, 2 элемент может быть вставлен в левое поддерево. n-3 элементы могут быть вставлены в правом поддереве.

...... Аналогично для i-й элемент как корень,i-1 элементы могут быть слева, а n-i справа.

эти поддеревья являются сам БСТ, таким образом, можно суммировать по формуле:

f(n) = f(0)f(n-1) + f(1)f (n-2) + .......... + f(n-1)f (0)

базовые случаи, f (0) = 1, так как существует ровно 1 способ сделать BST с 0 узлами. f (1) = 1, так как существует ровно 1 способ сделать BST с 1 узлом.

Если данного нет. узлов N, затем.

Другой Нет. BST=каталонский (N)
Другой Нет. из структурно различных бинарных деревьев = Catalan (N)

Другой Нет. бинарных деревьев = N!*Каталонский(Н)

У Эрика Липперта недавно была очень глубокая серия сообщений в блоге об этом:"Каждое Двоичное Дерево Есть" и "Каждое Дерево Есть" (плюс еще несколько после этого).

в ответ на ваш конкретный вопрос, он говорит:

число двоичных деревьев с n узлами задается цифры каталанский, которые имеют много интересных свойств. N-е каталонское число определяется по формуле (2n)! / (n+1)!Н!, который расти экспоненциально.

различные бинарные деревья с n узлами:

(1/(n+1))*(2nCn)

где C = комбинация, например.

n=6,
possible binary trees=(1/7)*(12C6)=132

(2n)!/n!*(n+1)!

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

бинарное дерево :

нет необходимости рассматривать значения, нам нужно посмотреть на structrue.

задано (2 мощность n) - n

например: для трех узлов (мощность 2 3) -3 = 8-3 = 5 разными structrues

бинарное дерево поиска:

мы должны рассмотреть даже значения узлов. Мы называем его каталонским числом

задано 2n C n / n+1

правильный ответ должен быть 2nCn/(n+1) для немаркированных узлов и если узлы помечены потом (2nCn)*n!/(n+1).