Количество способов заполнения двоичного дерева, чтобы сделать его лучшим

Question

Нам дан набор из n различных элементов и немаркированное двоичное дерево с n узлами. Сколько можно заполнить дерево заданным набором, чтобы оно стало бинарным деревом поиска?

Answer 1

, если для программы будет задано «дерево» (на любом языке) - это означает, что адрес корневого узла будет предоставлен для обхода.Следовательно, по моему мнению, поскольку «корневой узел» предоставлен, это означает, что древовидная структура уже построена и зафиксирована в одном типе.

, поэтому я думаю, что может быть только один возможный путь

Answer 2

Если под немаркированным подразумевается отсутствие указанного корневого узла, пусть G = {G[1]..G[n]} будет набором графов исходного немеченого дерева с корнями в вершинах 1 ... n соответственно.

Тогда для каждого графа G[i] существует ровно один способ заполнить дерево (почему? - подумайте, какое значение должно быть в корне дерева, и рекурсивно спуститься).

Как только вы можете показать это, ответ должен быть k, число взаимно неизоморфных графов в наборе G