Для двоичного дерева, предположим, что существует 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-м каталонским числом.

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

Answer 2

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

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

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

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