количество различных бинарных деревьев, которые могут быть сформированы?

Question

двоичное дерево, где каждый узел имеет не более двух дочерних узлов, дочерние узлы могут содержать ссылки на своих родителей.

we do not differentiate the nodes and all nodes are considered identical. Как мы можем найти количество различных двоичных деревьев, которые можно сформировать с помощью Nидентичные узлы.

Например: если 3 узла, то 5 различных деревьев
, если 7 узлов, то 429 деревьев

Answer 1

(2n)! / [(П + 1)! * П!]

взгляните на:

http://www.theory.csc.uvic.ca/~cos/inf/tree/BinaryTrees.html

Answer 2

рекурсия - твой друг!

псевдо-код:

numOfTrees(n):
  return trees(n).size();

trees(n):
  if (n==1)
    return new list of single node;

  big_trees = new empty list;

  for (small_tree : trees(n-1))
    for (big_tree : addSingleNode(tree))
      big_trees.insert(big_tree);

  return big_trees;

addSingleNode(tree):
  trees = new empty list;

  for (leaf : getLeaves(tree)) {
    trees.insert(tree.clone().addLeftChild(leaf, node));
    trees.insert(tree.clone().addRightChild(leaf, node));
  }

  return trees;

getLeaves () зависит от реализации, если у вас есть связанный список со всеми листьями, он будет быстрым, в противном случае вам, возможно, придется пройти проверку дерева на наличие листьев (что равно O (n) in_order).

не очень эффективно использует память, но решает проблему с помощью простой рекурсии, где на каждом этапе я беру деревья, перебираю все листья и всячески добавляю свой новый узел.

Answer 3

Теперь, если вы действительно хотите понять это, вместо того, чтобы просто получить (или экспериментировать, чтобы найти) ответ, вы можете проверить «Искусство компьютерного программирования», том 4, глава 4: Генерация всех деревьев.