Вычисление количества 2-3 деревьев, если задано количество узлов

Question

Я пытаюсь выяснить количество доступных деревьев, если дано количество данных. Ex) Если существует 8 разных данных, сколько деревьев можно сделать?

Answer 1

Вопрос не совсем понятен. Я предполагаю, что вам нужно количество полных двоичных (соответственно троичных) деревьев с ровно n листьями (если вы скорее ищете всего n узлов, вы сможете найти его по моему результату; если вы хотите количество деревьев, которые могут хранить данный набор из n различных данных, т.е. учитывать все способы хранения ваших данных в таком дереве, тогда вы также должны иметь возможность легко их получить).

Давайте рассмотрим случай полных двоичных деревьев. Если вы хотите, чтобы n листьев было в нем, вы можете назвать k количеством листьев в левом поддереве, у вас будет nk справа. Эти поддеревья имеют соответственно N(k) и N(nk) возможностей. Тогда у вас есть N(n)=sum(N(k)*N(n-k), k=1..n-1), С N(1)=1.

Это (a?) Определение каталонских номеров: https://en.wikipedia.org/wiki/Catalan_number

N(n)=C(n-1)

Вы можете сделать что-то подобное для тройных деревьев