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

Раньше я описывал небольшой алгоритм, который делал небольшие операции на бинарными деревьями. Я хотел протестировать его. Я попробовал несколько небольших тестов и они прошли, но я не был доволен. Я был почти уверен, но возможно какая-то непонятная топология бинарного дерева могла привести к ошибке. Я сообразил, что существует конечное количество бинарных деревьев данного размера. Я решил попробовать их все.

Прежде, чем начать я нуждаюсь в удобной записи бинарного дерева. Вот вершина моего дерева:

class Node
{
  public Node Left { get; private set; }
  public Node Right { get; private set; }
  public Node(Node left, Node right)
  {
    this.Left = left;
    this.Right = right;
  }
}

* This source code was highlighted with Source Code Highlighter.

Всё очень просто: левый узел, правый узел и всё. Обратите внимание, что для большей понятности этой статьи я убрал из вершины данные, которые обычно хранятся в бинарном дереве. Давайте предположим, что это обычные числа. Я буду представлять дерево в виде компактной строки. Пустую ссылку в дереве обозначим x. Непустую вершину в моём «дереве без значений» будем обозначать (<левый потомок> <правый потомок>). Рассмотрим дерево:
  1
 / \
x   2
   / \
  x   x

Вершина 2 имеет два нулевых потомка и будет обозначена (xx). Вершина 1 имеет пустого левого потомка, а правым потомком является вершина 2. Таким образом дерево обозначится, как (x(xx)). Какой же в этом смысл? Мы можем написать небольшой рекурсивный код, который строит такие строки:

public static string BinaryTreeString(Node node)
{
  var sb = new StringBuilder();
  Action<Node> f = null;
  f = n =>
  {
    if (n == null)
      sb.Append("x");
    else
    {
      sb.Append("(");
      f(n.Left);
      f(n.Right);
      sb.Append(")");
    }
  };
  f(node);
  return sb.ToString();
}

* This source code was highlighted with Source Code Highlighter.

Как же пронумеровать все возможные бинарные деревья данного размера? Мы сделаем это рекурсивно.

Существует ровно одно дерево из 0 вершин. Оно обозначается x. Это база.

Теперь выберем номер. Например, четыре. Мы хотим пронумеровать все деревья из четырёх непустых вершин. Предположим, что мы уже пронумеровали все вершины из трёх, двух и одной вершины. Обозначим множество бинарных деревьев из n вершин как B(n). Положим, что мы создаём все возможные комбинации B(x) и B(y), имея ввиду, что B(x) соответствуют левому потомку корня, а B(y) – правому потомку корня. Я буду записывать B(x)B(y). В этой записи деревья с четырьмя непустыми вершинами могут быть разбиты на четыре множества: B(0)B(3), B(1)B(2), B(2)B(1), B(3)(0).

Это достаточно просто обобщить: мы можем пронумеровать все деревья с k вершинами, перебирая каждый раз k случаев, в которых мы рассматриваем задачи более мелкого размера. Замечательное рекурсивное решение. Рассмотрим код:

static IEnumerable<Node> AllBinaryTrees(int size)
{
  if (size == 0)
    return new Node[] { null };
  return from i in Enumerable.Range(0, size)
      from left in AllBinaryTrees(i)
      from right in AllBinaryTrees(size - 1 - i)
      select new Node(left, right);
}

* This source code was highlighted with Source Code Highlighter.

Заметим, что LINQ делает алгоритм более похожим на его описание, чем эквивалентная программа с большим количеством циклов.

И действительно, если мы запустим:

foreach (var t in AllBinaryTrees(4))
  Console.WriteLine(BinaryTreeString(t));

* This source code was highlighted with Source Code Highlighter.

То получим все деревья из четырёх непустых вершин.
(x(x(x(xx))))
(x(x((xx)x)))
(x((xx)(xx)))
(x((x(xx))x))
(x(((xx)x)x))
((xx)(x(xx)))
((xx)((xx)x))
((x(xx))(xx))
(((xx)x)(xx))
((x(x(xx)))x)
((x((xx)x))x)
(((xx)(xx))x)
(((x(xx))x)x)
((((xx)x)x)x)

Теперь у меня есть механизм, который строит все топологии деревьев, и я могу протестировать мой алгоритм.

Сколько таких деревьев? Похоже их может быть довольно много.

Количество бинарных деревьев из n вершин называется числом Каталана, которое обладает множеством интересных свойств. N-ое число Каталана считается по формуле (2n)! / (n+1)!n!, которая растёт экспоненциально. (В Википедии предложено несколько доказательств, что это форма числа Каталана.) Число бинарных деревьев данного размера

0 1
1 1
2 2
4 14
8 1430
12 208012
16 35357670

Поэтому мой план попробовать все деревья данного размера не очень хорош. Существует слишком много вариантов и нельзя проверить все в короткий промежуток времени.

Я озадачу Вас: положим мы забыли о бинарных деревьях и на текущий момент рассмотрим произвольные деревья. Произвольное дерево может иметь 0, 1 или любое конечное количество потомков. Пусть непустое произвольное дерево запишется списком потомков в скобках. Таким образом {{}{}{{}}} – это дерево

    1
   /|\
  2 3 4
      |
      5

Т.к. вершины 2, 3 и 5 не имеют потомков, то они будут записываться как {}. Какой смысл? Обратите внимание на порядок. {{}{}{{}}} и {{}{{}}{}} – это разные деревья с похожей структурой.

Моя первая задача: чего больше произвольных деревьев из n вершин или бинарных деревьев из n вершин.
Моя вторая задача: можете ли вы разработать механизм нумерации произвольных деревьев?