С 'N' никакие из узлов, сколько различных Деревьев двоичного поиска и возможных Деревьев двоичного поиска?
Для Двоичных деревьев: нет никакой потребности рассмотреть древовидные значения узла, я только интересуюсь различными древовидными топологиями с узлами 'N'.
Для Дерева двоичного поиска: Мы должны рассмотреть древовидные значения узла.
2 ответа
Я рекомендую эту статью моего коллеги Ника Парланте (когда он еще учился в Стэнфорде). Подсчет структурно различных двоичных деревьев (проблема 12) имеет простое рекурсивное решение (которое в закрытой форме оказывается каталонской формулой, на которую уже упоминался ответ @codeka).
Я не уверен, как количество структурно различных бинарных поисковых деревьев (сокращенно BST) будет отличаться от количества «простых» бинарных деревьев - за исключением того, что, если "учитывать значения узлов дерева" "вы имеете в виду, что каждый узел может быть, например, любое число, совместимое с условием BST, то количество различных (но не всех структурно разных! -) BST бесконечно. Я сомневаюсь, что вы имеете в виду это, поэтому поясните, пожалуйста, что вы делаете на примере!
Эрик Липперт недавно опубликовал в блоге серию очень подробных сообщений об этом: « Каждое двоичное дерево существует » и « Каждое дерево существует ] "(плюс еще несколько после этого).
Отвечая на ваш конкретный вопрос, он говорит:
Количество двоичных деревьев с n узлами задается каталонскими числами , которые обладают многими интересными свойствами. N-е каталонское число определяется по формуле (2n)! / (n + 1)! n !, которая растет экспоненциально.