Количество полных двоичных деревьев

Question

Рассмотрим двоичные деревья, где каждый узел является либо листом, либо имеет ровно два дочерних узла (левый и правый, которые мы считаем разными).Сколько разных деревьев существует на n узлах?
Например:
- 3 узла -> 1 дерево,
- 4-> 0 деревьев,
- 5 -> 2 дерева,
- 6 -> 0 деревьев,
- 7 -> 5 деревьев,
- и так далее ...
Есть ли какие-нибудь формулы для этой последовательности?Я нашел формуляр для всех возможных двоичных деревьев ( каталонское число ), но я ищу полное дерево.

Answer 1

В "полном" дереве есть нечетное количество узлов, и каждый второй узел по порядку является листом.

Если вы удалите все эти листья, у вас останется двоичное дерево, которое может небыть полным.Для любого (возможно, не полного) двоичного дерева существует ровно один способ добавить лист в начале, конце и между каждой парой узлов, чтобы создать полное двоичное дерево.

Таким образом, существует1-1 соответствие между двоичными деревьями с n узлами и полными деревьями с 2n + 1 кодами.

C (n) - каталонское число - это число бинарных деревьев с n узлами, а также, следовательно, число "полных" деревьев с 2n + 1 узлами.

Число полных двоичных деревьев с n узлами, следовательно, равно C ((n-1) / 2) .Поскольку у вас не может быть половины узла, ответ будет 0 , когда n чётно.