Перечислите все двоичные деревья с n узлами

Дано целое число n, перечислить все возможные полные двоичные деревья с n внутренними узлами. (Полные двоичные деревья имеют ровно 2 дочерних элемента на каждом внутреннем узле). Древовидная структура должна быть выведена в виде обхода дерева по предварительному порядку: 1 представляет внутренний узел, а 0 - внешний узел (ноль).

Вот примеры для первых нескольких n:

0:
0

1:
100

2:
11000
10100

3:
1110000
1101000
1100100
1011000
1010100

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

Perl - 125 79 символов

Граф включает в себя 4 символа для " -ln" вариантов. Берет из стандартного ввода.

Новый конструктивный подход:

@a=0;map{%a=();map{$a{"$`100$'"}=1while/0/g;}@a;@a=keys%a}1..$_;print for@a

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

(Я обязан этой концепцией другим решениям, которые используют внутренний узел для листинга [100-> 0] подстановки для проверки последовательностей, сгенерированных последовательно, и я полагаю, что увидел - после написания моего ответа на основе этой концепции - тот же самый 0- > 100 методов построения в чьем-то промежуточном редактировании.)

Предыдущий рекурсивный подход:

sub t{my$n=shift;if($n){--$n;for$R(0..$n){for$r(t($R)){for$l(t($n-$R)){push@_,"1$l$r"}}}}else{push@_,"0"}@_}print for t$_

Рекурсивный негольф:

sub tree {
  my ($n) = @_;
  my @result = ();
  if ( $n ) {
    for $right_count ( 0 .. $n-1 ) {
      for $right ( tree( $right_count ) ) {
        for $left ( tree( ($n-1) - $right_count ) ) {
          push @result, "1$left$right";
        }
      }
    }
  }
  else {
    push @result, "0";
  }
  return @result;
}
foreach $tree ( tree($_) ) {
  print $tree;
}

PHP (142) (138) (134) (113)

Запускается из командной строки, т.е. «php golf.php 1» выводит «100».

РЕДАКТИРОВАТЬ: вырезать 4 символа с помощью альтернативного метода, создавая строки из 0, а не повторяя вниз от $ n. Использует PHP 5.3 для сокращенного троичного оператора; в противном случае требуется еще 2 символа.

РЕДАКТИРОВАТЬ 2: Сохранено еще 4 символа с некоторыми изменениями в петлях.

РЕДАКТИРОВАТЬ 3: я пытался другой подход, и я, наконец, получил его ниже старого метода.

Все деревья могут рассматриваться как двоичные представления целых чисел между 4 ^ n (или 0, когда n = 0) и 2 * 4 ^ n. Эта функция перебирает этот диапазон и получает двоичную строку каждого числа, затем многократно уменьшает ее, заменяя «100» на «0». Если последняя строка равна «0», то это допустимое дерево, поэтому выведите его.

for($i=$p=pow(4,$argv[1])-1;$i<=2*$p;){$s=$d=decbin($i++);while($o!=$s=str_replace(100,0,$o=$s));echo$s?:"$d\n";}

Рубин, 99 94 92 89 87 символов

(n=4**gets.to_i).times{|i|s=(n+i-1).to_s 2;t=s*1;0while s.sub!'100',?0;puts t if s==?0}

Ввод читается из стандартного ввода.

> echo 2 | ruby binary_trees.rb
10100
11000

Редактировать 1: Изменен IO (см. Комментарии Lowjacker)

b=->n{n==0?[?0]:(k=[];n.times{|z|b[z].product(b[n-1-z]){|l|k<<=?1+l*''}};k)}
puts b[gets.to_i]

Редактировать 2: измененный алгоритм.

b=->n{n==0?[?0]:(k=[];b[n-1].map{|s|s.gsub(/0/){k<<=$`+'100'+$'}};k.uniq)}
puts b[gets.to_i]

Редактировать 3: версия теперь использует третий подход (используя идею migimaru).

Изменить 4: снова два символа. Спасибо Мигимару.

Рубин 1,9 (80) (79)

Использование нерекурсивного, конструктивного подхода, используемого DCharness.

РЕДАКТИРОВАТЬ: Сохранено 1 символ.

s=*?0;gets.to_i.times{s.map!{|x|x.gsub(?0).map{$`+'100'+$'}}.flatten!}
puts s&s

Haskell 122 символа

main=do n<-readLn;mapM putStrLn$g n n
g 0 0=[['0']]
g u r|r<u||u<0=[]
g u r=do s<-[1,0];map((toEnum$s+48):)$g(u-s)(r-1+s)

Поскольку IO является нетривиальной частью кода в haskell, возможно, кто-то может использовать подобное решение на другом языке. По существу случайные прогулки в квадрате от левого нижнего к верхнему правому остановке, если диагональ пересечена. Эквивалентно следующему:

module BinTreeEnum where

import Data.List
import Data.Monoid

data TStruct = NonEmpty | Empty deriving (Enum, Show)
type TreeDef = [TStruct]

printTStruct :: TStruct -> Char
printTStruct NonEmpty = '1'
printTStruct Empty = '0'

printTreeDef :: TreeDef -> String
printTreeDef = map printTStruct

enumBinTrees :: Int -> [TreeDef]
enumBinTrees n = enumBinTrees' n n where
  enumBinTrees' ups rights | rights < ups = mempty
  enumBinTrees' 0   rights = return (replicate (rights+1) Empty)
  enumBinTrees' ups rights = do
    step <- enumFrom (toEnum 0)
    let suffixes =
          case step of
            NonEmpty -> enumBinTrees' (ups - 1) rights
            Empty -> enumBinTrees' ups (rights - 1)
    suffix <- suffixes
    return (step:suffix)

mainExample = do
  print $ map printTreeDef $ enumBinTrees 4

Golfscript, 60 83

~[1,]\,{;{[:l.,,]zip{({;}{~:a;[l a<~1 0.l a)>~]}if}/}%}/{n}%

Я разработал режим Golfscript для Emacs, если кому-то интересно.