Распечатать двоичное дерево

18

Вдохновленный недавним вопросом о SO ...

Напишите функцию для печати двоичного дерева в следующем формате:

   3
 /   \
1     5
 \   / \
  2 4   6
  1. Вывод должен состоять из строки узлов, за которой следуют строка /и \символы, обозначающие отношения, за которыми следует строка узлов и т. Д.
  2. Вы можете предположить, что все узлы представимы как один символ.
  3. Соседние узлы на самом низком уровне должны быть разделены хотя бы одним пробелом, узлы, расположенные дальше, должны быть разделены соответствующим образом
  4. Узлы с двумя детьми должны быть расположены точно посередине их прямых детей.
  5. Косая черта в отношениях должна быть на полпути между родителем и соответствующим ребенком (в зависимости от того, что вы хотите).

Входные данные:

Входные данные будут предоставлены в качестве аргумента вашей функции. Я не буду указывать точную структуру дерева, однако оно должно использоваться как фактическое двоичное дерево. Никакие «деревья не представлены в моей программе как строки, совпадающие с ожидаемым результатом».

Вы можете распечатать в выходной поток или вернуть строку, содержащую вывод, на ваш выбор.

Очки за самый короткий код, но я бы предпочел полностью работающее длинное решение, чем 90% работающее короткое.


Обновление для награды:

Для награды я (Оптимизатор) делаю небольшие изменения:

  • Ввод может быть из STDIN, ARGV или аргумента функции.
  • Вывод должен быть на STDOUT (или console.logдля JS)
  • Вы можете предположить, что ввод в виде массива, например. [1,2,3]или[1 2 3]

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

Anon.
источник
Должны ли мы использовать несколько косых черт отношения были уместны? Должны ли мы использовать минимальное количество слешей? Следует ли различать наличие одного левого ребенка и одного правого ребенка? Было бы хорошо иметь ведущие пробелы в каждой строке вывода?
Что нам делать, если дерево не является полным (2 ^ n-1 узлов для некоторого n)? Некоторые узлы (какие?) Имеют только один дочерний узел. Но если нам разрешено иметь узлы только с одним дочерним узлом, вырожденное дерево легко создать (скажем, 1-2-3-4-5-6 вниз и вправо).
Кит Рэндалл
Как вы рисуете это для больших чисел? Например30000,1000,499999
Мохсен

Ответы:

9

Фортран 77 - 1085 символов

      subroutine q(u,t)
      implicit integer(i-z)
      character*33 f,g
      dimension t(u)
      m=ceiling(log(real(u))/log(2.))
      v=2**(m+1)-1
      do l=1,m
         n=2**(l-1)
         k=2**(m-l+2)-3
         w=(3+k)*2**(l-1)-k
         p=1+(v-w)/2
         if(l.ne.1)then
            write(f,'(A,I3,A)')'(A',p,',$)'
            print f,' '
            write(f,'(A5,I3,A3)')'(A3,A',k,',$)'
            do j=2**(l-1),2**l-1
               if(t(j/2).lt.0.or.t(j).lt.0)then
                  print f,'   ',' '
               elseif(mod(j,2).eq.0)then
                  print f,'  /',' '
               else
                  print f,' \ ',' '
               endif
            enddo
            print*
         endif
         write(f,'(A,I3,A)')'(A',p,',$)'
         print f,' '
         write(f,'(A5,I3,A3)')'(I3,A',k,',$)'
         write(g,'(A2,I3,A3)')'(A',k+3,',$)'
         do j=2**(l-1),2**l-1
            if(t(j).ge.0)then
               print f,t(j),' '
            else 
               print g,' '
            endif
         enddo
         print*
      enddo
      end

Дерево представлено во входном массиве tобычным способом, root в 1, root-> left в 2, root-> right в 3 root-> left-> left в 4 ...

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

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

Полная программа с комментариями и стартовой леской:

      program tree

      parameter (l=8)          ! How many nodes to support
      dimension i(l)

c     Initialize the array to all empty nodes
      do j=1,l
         i(j)=-1
      end do
c     Fill in some values
      i(1)=3
      i(2)=1
      i(3)=5
      i(5)=2
      i(6)=4
      i(7)=7
c      i(14)=6
c      i(15)=8
c     Call the printing routine
      call q(l,i)

      stop
      end

c     Print an ASCII representation of the tree
c
c     u the length of the array containing the tree
c     t an integer array representing the tree.
c
c     The array contains only non-negative values, and empty nodes are
c     represented in the array with -1.
c
c     The printed representation uses three characters for every node,
c     and places the (back) slash equally between the two node-centers.
      subroutine q(u,t)
      implicit integer(i-z)
      character*33 f,g
      dimension t(u)
      m=ceiling(log(real(u))/log(2.)) ! maximum depth of the tree
      v=2**(m+1)-1              ! width needed for printing the whole tree
                                ! Optimized from 3*2**m + 1*((2**m)-1) at
                                ! the bottom level
      do l=1,m
         n=2**(l-1)             ! number of nodes on this level
         k=2**(m-l+2)-3         ! internode spacing
         w=(3+k)*2**(l-1)-k     ! width needed for printing this row
                                ! Optimized from 3*2**l + k*((2**l)-1) at
                                ! the bottom level
         p=1+(v-w)/2            ! padding for this row
c     Print the connecting lines associated with the previous level
         if(l.ne.1)then         ! Write the connecting lines
            write(f,'(A,I3,A)')'(A',p,',$)'
            print f,' '
            write(f,'(A5,I3,A3)')'(A3,A',k,',$)'
            do j=2**(l-1),2**l-1
               if(t(j/2).lt.0.or.t(j).lt.0)then
                  print f,'   ',' '
               elseif(mod(j,2).eq.0)then
                  print f,'  /',' '
               else
                  print f,' \ ',' '
               endif
            enddo
            print*
         endif
c     Print the nodes on this level
         write(f,'(A,I3,A)')'(A',p,',$)'
         print f,' '
         write(f,'(A5,I3,A3)')'(I3,A',k,',$)'
         write(g,'(A2,I3,A3)')'(A',k+3,',$)'
         do j=2**(l-1),2**l-1
            if(t(j).ge.0)then
               print f,t(j),' '
            else 
               print g,' '
            endif
         enddo
         print*
      enddo
      end

Вывод с вводом, эквивалентным примеру:

$ ./a.out 
         3             
     /      \      
     1       5     
      \    /  \  
       2   4   7 
dmckee
источник
ПОМОГИТЕ, почему этот язык?
Томсминг
9
Потому что он так плохо подходит для игры в гольф.
dmckee
5

CJam, 100 99 байтов

q~_,2b,)2\#:Q1@{_2$<Q(S*:T*TQ2/:Q@ts[N+_0@{@1$' >{2$St2$_Q3*&2/^_4$>"\/"=t}*@)}/;U*o]o1:U$>\2*\}h];

Входные данные должны быть списком символов без каких-либо управляющих символов ascii. Пустые узлы обозначаются пробелом. Это также должно быть идеальное двоичное дерево с ровно 2 n -1 узлами.

Пример:

['6 '3 '7 '1 '4 '  '9 '0 '2 '  '5 '  '  '8 ' ]

Или просто используйте строки:

"63714 902 5  8 "

Выход:

                6              
            /       \          
        3               7      
      /   \               \    
    1       4               9  
   / \       \             /   
  0   2       5           8    

объяснение

q~                        " Read input. ";
_,2b,                     " Get tree height. ";
)2\#:Q                    " Get (displayed) tree width and save it in Q. ";
1@                        " Push X=1 and rotate the input to top. ";
{                         " Do: ";
    _2$<                  " Get first X characters from the input. ";
    Q(S*:T                " T = (Q-1) spaces. ";
    *                     " Separate the X characters by T. ";
    TQ2/:Q@t              " Put the string in the middle of T, and divide Q by 2. ";
    s                     " Concatenate everything into a string.
                            This is the line of node labels. ";
    [
        N+                " Append a newline. ";
        _                 " Duplicate. ";
        0@                " Push a 0 and rotate the original string to top. ";
        {                 " For each character: ";
            @             " Rotate the duplicate to top. ";
            1$' >         " Test if the current character is greater than a space. ";
            {             " If true: ";
                2$St      " Set the current character in the duplicate to space. ";
                2$        " Copy the current position I (the number initialized with 0). ";
                _Q3*&2/^  " Calculate I ^ ((I & (3*Q))>>1),
                            the position of the relationship character. ";
                _4$>      " Test if it is greater than the current position. ";
                "\/"=     " Select the relationship character. ";
                t         " Change the character in the duplicate. ";
            }*
            @)            " Increment the current position. ";
        }/
                          " The last two items are the line of relationship characters
                            and the tree width. ";
        ;                 " Discard the tree width. ";
        U*                " If it is the first line, empty the line of
                            relationship characters. ";
        o                 " Output. ";
    ]o                    " Output the line of node labels. ";
    1:U                   " Mark it not the first line. ";
    $>                    " Remove the first X characters from the input. ";
    \2*\                  " Multiply X by 2. ";
}h                        " ...while the input is not empty. ";
];                        " Discard everything in the stack. ";

Конверсионный скрипт

[[0LL]W]
[q~{_a_:i={'0+}*}%La2*f+
_,,]z$
1$a+
{
    {
        1$1=1$1=>:T
        {
            ~@0=2 3$1=t
            @1@ta\+
        }*
        T
    }g
}*
0=1=a
{
    {
        (M\+:M;
        La[' LL]aer~
    }%
    _[' LL]a-
}g
];
M0+`-3<']+

Он принимает либо символы, либо однозначные числа.

Примеры (все одинаковые):

['6 '7 '9 '3 '1 '2 '8 '4 '0 '5]
[6 7 9 3 1 2 8 4 0 5]
"6793128405"

Выход:

['6 '3 '7 '1 '4 ' '9 '0 '2 ' '5 ' ' '8 ' ]

Это простая декартова конструкция дерева.

jimmy23013
источник
Вы можете просто добавить еще два байта и сделать ввод сценария преобразования в виде целых чисел вместо символов :)
Optimizer
@Optimizer Отредактировано для поддержки обоих. Я думаю, что символы имеют больше смысла, так как он поддерживает имена узлов только с одним символом. Здесь гораздо больше символов, чем однозначных чисел.
jimmy23013
2

Python 2, 411 байт

import math
def g(a,o,d,l,b):
 if l<0:
    return
 c=2*b+1
 k=2*l+1
 o[k]=' '*b
 n=d-l
 p=1 if n==0 else 3*2**n-1
 o[k-1]=p/2*' '
 i=0
 for v in a[2**l-1:2**l*2-1]:
    v=' ' if v==None else v
    o[k]+=v+' '*c
    m=' ' if v==' ' else '/' if i%2==0 else '\\'
    o[k-1]+=m+max(1,b)*' ' if i%2==0 else m+p*' '
    i+=1

 g(a,o,d,l-1,c)
def f(a):
 d=int(math.log(len(a),2))
 o=['']*(d*2+2)
 g(a,o,d,d,0)
 print '\n'.join(o[1:])

Примечание. Первый уровень отступа - 1 пробел, второй - одна вкладка.

Вызов fсо списком односимвольных строк или None, например. f(['1',None,'3']), Список не может быть пустым.

Это должно подчиняться правилам для щедрости.

Скрипт конвертера:

Преобразует и массив в формат, используемый принтером бинарного дерева. Пример:

$ python conv.py [3,5,4,6,1,2]
['3', '1', '5', None, '2', '4', '6']

-

import sys

def insert(bt, i):
    if i < bt[0]:
        j = 0
    else:
        j = 1

    n = bt[1][j]
    if n == [None]:
        bt[1][j] = [i, [[None], [None]]]
    else:
        insert(bt[1][j], i)

def insert_empty(bt, i):
    if i == 0:
        return
    if bt == [None]:
        bt += [[[None], [None]]]

    insert_empty(bt[1][0], i - 1)
    insert_empty(bt[1][1], i - 1)

def get(l, level):
    if level == 0:
        if type(l) == list:
            return ([], l)
        else:
            return ([l], [])
    elif type(l) != list:
        return ([], [])

    res = []
    left = []

    for r, l in  [get(i, level - 1) for i in l]:
        res += r
        left += l

    return (res, left)

if __name__ == '__main__':
    l = eval(sys.argv[1])
    bt = [l[0], [[None], [None]]]
    map(lambda x: insert(bt, x), l[1:])

    depth = lambda l: 0 if type(l) != list else max(map(depth, l)) + 1
    d = (depth(bt) + 1) / 2

    insert_empty(bt, d - 1)

    flat = []
    left = bt
    i = 0
    while len(left) > 0:
        f, left = get(left, 1)
        flat += f

        i += 1

    for i in range(len(flat) - 1, -1, -1):
        if flat[i] == None:
            flat.pop()
        else:
            break

    flat = map(lambda x: None if x == None else str(x), flat)

    print flat

Примеры:

Для их запуска вы должны иметь имя основного файла bt.pyи имя файла конвертера conv.py.

$ python conv.py [3,5,4,6,1,2] | python -c 'import bt; bt.f(input())'
   3
  / \
 1   5
  \ / \
  2 4 6
$ python conv.py [5,4,3,7,9] | python -c 'import bt; bt.f(input())'
   5
  / \
 4   7
/     \
3     9
$ python conv.py [1,2,3,4,5,6] | python -c 'import bt; bt.f(input())'
                               1
                                       \
                                               2
                                                   \
                                                       3
                                                         \
                                                           4
                                                            \
                                                             5
                                                              \
                                                              6
$ python conv.py [6,5,4,3,2,1] | python -c 'import bt; bt.f(input())'
                                   6
                       /
               5
           /
       4
     /
   3
  /
 2
/
1
Tyilo
источник
Вы на самом деле не создаете двоичное дерево. Просто печатать массив в виде двоичного дерева. Вывод ['1','2','3','4','5','6','7','8','9']массива не тот, который вы показали. Он должен иметь 3в качестве правого потомка того, 2чей правый потомок 1является корневым элементом.
Оптимизатор
@Optimizer Из вопроса: «Входные данные будут предоставлены в качестве аргумента для вашей функции. Я не буду указывать точную структуру дерева, однако он должен использоваться в качестве фактического двоичного дерева». Я не вижу конкретного определения используемого формата массива.
Tyilo
Первоначально речь идет о печати двоичного дерева . Ваши выводы не бинарные деревья. Формат массива не имеет к этому никакого отношения.
Оптимизатор
@ Оптимизатор, как они не бинарные деревья? Из Википедии: бинарное дерево - это древовидная структура данных, в которой каждый узел имеет не более двух дочерних элементов. Есть ли у какого-либо из узлов более двух детей?
Tyilo
Ughh. Я вижу сейчас. Я думаю, что здесь есть термин недопонимание. Даже в исходных примерах вывод имеет формат двоичного дерева поиска . И моя награда также за двоичное дерево поиска. Извините за путаницу там.
Оптимизатор
1

APL, 125 символов

{⍵{x←⍵[0;d←⌈2÷⍨1⌷⍴⍵]←↑⍺
2 1∇{x[2↓⍳↑⍴x;(⍳d)+d×⍺-1]←⍵(⍺⍺⍣t←0≠⍴⍵)2↓x[;⍳d]
x[1;d+(⌈d÷4)ׯ1*⍺]←' /\'[t×⍺]}¨⍺[2 1]
x}' '⍴⍨2(×,*)≡⍵}

Пример:

{⍵{x←⍵[0;d←⌈2÷⍨1⌷⍴⍵]←↑⍺
2 1∇{x[2↓⍳↑⍴x;(⍳d)+d×⍺-1]←⍵(⍺⍺⍣t←0≠⍴⍵)2↓x[;⍳d]
x[1;d+(⌈d÷4)ׯ1*⍺]←' /\'[t×⍺]}¨⍺[2 1]
x}' '⍴⍨2(×,*)≡⍵}('1' ('2' ('3' ('4' ()()) ('5' ()())) ('6' ()('7' ()())))('8' ()('9' ('0' ()())())))

Проверено здесь.

jimmy23013
источник
Это тоже скрипт конвертации?
Оптимизатор
@Optimizer Он принимает формат ввода вложенного массива, который, вероятно, можно использовать в качестве бинарного дерева поиска (но я не уверен насчет сложности). Если мне нужно использовать более привычные форматы ... возможно, я сделаю это позже.
jimmy23013
@Optimizer Теперь, снова читая вопрос, означает ли «массив двоичного дерева поиска» массив полного двоичного дерева в порядке глубины (или что-то еще)? Я не думал, что это было что-то конкретное. И поиск этого термина не дал ничего полезного.
jimmy23013
@ Оптимизатор Ну, это как раз то, что я имел в виду. Но я не думаю, что его обычно называют «бинарным массивом дерева поиска», а лишь «своего рода хранилищем бинарных деревьев». Это, вероятно, нуждается в некотором уточнении ... И я, вероятно, исправлю этот ответ несколько дней спустя, может быть, на другом языке ...
jimmy23013
0

Рубин, 265 байт

def p(t);h=Math.log(t.length,2).to_i;i=-1;j=[];0.upto(h){|d|s=2**(h-d)-1;c=2**d;if d>0;m=' '*(s+s/2)+'I'+' '*(s-s/2);1.upto(d){m+=' '+m.reverse};w=i;puts m.gsub(/I/){|o|t[w+=1]?(w%2==0?'\\':'/'):' '};end;puts (0...c).map{' '*s+(t[i += 1]or' ').to_s+' '*s}*' ';};end

Версия @proudhaskeller, 269 байтов

def p(t);h=Math.log(t.length,2).to_i;i=-1;j=[];0.upto(h){|d|s=(z=2**(h-d))-1;c=2**d;if d>0;m=' '*(s+z/2)+'I'+' '*(s-z/2);1.upto(d){m+=' '+m.reverse};w=i;puts m.gsub(/I/){|o|t[w+=1]?(w%2==0?'\\':'/'):' '};end;puts (0...c).map{' '*s+(t[i += 1]or' ').to_s+' '*s}*' ';};end

Explaination

Подробная версия:

def p(t)
  depth = Math.log(t.length, 2).floor
  i = -1
  j = []
  (0..depth).each do |d|
    s = 2 ** (depth-d)-1
    c = 2 ** d

    if d > 0
      m = ' '*(s+s/2) + '|' + ' '*(s-s/2)
      w = i
      1.upto(d) { m += ' ' + m.reverse }
      puts m.gsub(/\|/) { |o| t[w+=1] ? (w%2==0 ? '\\' : '/') : ' ' }
    end

    puts (0...c).map{' '*s+(t[i += 1]or' ').to_s+' '*s}*' '
  end
end

пример

n = nil
p([
  1, 2, 3, 4, 5,
  n, 7, 8, 9, 0,
  1, n, n, 4, 5,
  6, 7, 8, 9, 0,
  1, 2, 3, n, n,
  n, n, 8, 9, n,
  n
])

дает:

               1               
          /         \          
       2               3       
    /     \               \    
   4       5               7   
 /   \   /   \           /   \ 
 8   9   0   1           4   5 
/ \ / \ / \ / \         / \    
6 7 8 9 0 1 2 3         8 9   

(Я еще не написал скрипт конвертации.)

AlexRath
источник
ваши косые черты точно не посередине
гордый хаскеллер
@Proudhaskeller "круглый, как вы хотите", я думал, что это выглядит круче. Вы можете заменить s / 2 на (s + 1) / 2, если хотите.
AlexRath
Нет, косые черты в первом ряду не точно посередине, в этом ряду это не вопрос округления
гордый haskeller
@proudhaskeller Если вы замените s / 2 на (s + 1) / 2, они окажутся точно посередине, но я все же предпочитаю этот способ, потому что это делает крайние левые и правые ветви круглыми.
AlexRath
это против спецификации ...
гордый haskeller