2019-gate-computer-science-and-it-practice.pdf/Q06-alg1

Вопрос: Q06-alg1-31d68c

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

Ответы

• 256
• 128
• Правильный ответ: 248
• 64

Объяснение

Непонятно.

Обычно число бинарных деревьев выводится через Числа Каталана.

• Бинарное дерево — структура где у каждого узла, не больше двух потомков (левый и правый).

База рекурсии

пустое дерево, 0 узлов, одно.

Рекурсия

Дерево на n-узлов делаем так

• выбираем один узел как корневой (выбор рута — n вариантов)
• дальше рекурсивно строим левое и правое дерево.
  • Левое поддерево — выбор k-узлов .
  • Правое поддерево — оставшиеся n-1-k

Получается рекурсивная формула , совпадающая с определением Чисел Каталана.

Но тут в ответе явно ждут формулу (как она выводится?), которая бьется до 4 с числами каталана, но начиная с 5 — расходится.

Исходники — вопрос 6 на 219 странице книги «2019-gate-computer-science-and-it-practice.pdf»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.