предположим, что для двоичного дерева существует n узлов, сколько разных структур я могу построить?

Question

Рассмотрим двоичное дерево с n узлами. Сколько существует различных возможных структур бинарных деревьев?

Я пробовал что-то вроде:

n   number of different structure:

1        1
2        4
3        16

так же, как 4 (n-1) для n> 1; 1 для п == 1?

Answer 1

Предыдущий ответ Адриана Томана верен, когда значение узла не важно, учитывается только структура дерева (см. Ту же ссылку в Википедии).

Когда значение узла также важно, расчет другой.Каталонское число дает вам количество различных возможных структур дерева.Теперь вы можете расположить узлы в каждой из этих структур (перестановка).Следовательно, общее количество различных деревьев для n узлов, где значение узла важно, определяется по формуле -

n-е каталонское число * n!

nodes (n)    trees C(n) * n!
1            1
2            4 (= 2 * 2)
3            30 (= 5 * 6)
4            336 (= 14 * 24)

Answer 2

Количество различных двоичных деревьев, которые могут быть сформированы с использованием n узлов, определяется n-м каталонским числом.

number of nodes (n)   binary trees C(n)  
1                     1  
2                     2  
3                     5  
4                     14   

См:

http://en.wikipedia.org/wiki/Binary_tree
http://en.wikipedia.org/wiki/Catalan_number