15 мая 2010 в 10:14

Эрик Липперт — Генерация всех произвольных деревьев перевод

В прошлый раз мы говорили о том, что число бинарных деревьев с n вершинами равно C(n), где C(n) – это n-ое число Каталана. Я заинтересовался чего больше: произвольных деревьев из n вершин или бинарных деревьев из n вершин. Ответ может вас удивить, он не лежит на поверхности.


Распространённый ответ на этот вопрос я получу сразу: «Разумеется, произвольных деревьев больше, т.к. бинарное дерево – это частный случай произвольного дерева». Можете ли вы сказать, почему это неверно? Бинарных деревьев больше, чем произвольных деревьев! Существует два бинарных дерева из двух вершин: одно с левым потомком ребёнком корня, а другое – с правым потомком корня. Но есть только одно произвольное дерево с двумя вершинами, в нём нет разницы между «левым» и «правым» потомком.
Source Code Highlighter.

Для получения всех деревьев размера 5, мы переберём все бинарные деревья размера 4 и выведем соответствующие произвольные деревья размера 5.
foreach (var n in AllBinaryTrees(4))
  Console.WriteLine(TreeString(n));

* This source code was highlighted with Source Code Highlighter.
и мы получим
{{}{}{}{}}
{{}{}{{}}}
{{}{{}}{}}
{{}{{}{}}}
{{}{{{}}}}
{{{}}{}{}}
{{{}}{{}}}
{{{}{}}{}}
{{{{}}}{}}
{{{}{}{}}}
{{{}{{}}}}
{{{{}}{}}}
{{{{}{}}}}
{{{{{}}}}}


Обратите внимание, что если вы уберёте крайние скобки, то мы получим решение задачи «напечатать все правильные комбинации из четырёх пар скобок»! Если вы пронумеруете все бинарные деревья, тогда вы пронумеруете все решения множества различных эквивалентных задач.

В следующий раз: что мы можем сгенерировать ещё?

Перевод: Eric Lippert