Imprimir uma árvore binária

18

Inspirado por uma pergunta recente sobre SO ...

Escreva uma função para imprimir uma árvore binária no seguinte formato:

   3
 /   \
1     5
 \   / \
  2 4   6
  1. A saída deve consistir em uma linha de nós, seguida por uma linha de /e \caracteres indicando relacionamentos, seguida por uma linha de nós, etc.
  2. Você pode assumir que todos os nós são representáveis ​​como um único caractere.
  3. Os nós adjacentes no nível mais baixo devem ser separados por pelo menos um espaço, os nós mais acima devem ser separados conforme apropriado.
  4. Nós com dois filhos devem ser colocados precisamente no meio de seus filhos diretos.
  5. As barras de relacionamento devem estar na metade do caminho entre o pai e o filho apropriado (arredondar da maneira que desejar).

Entrada:

A entrada será fornecida como argumento para sua função. Não especificarei a estrutura exata da árvore, no entanto, ela deve ser utilizável como uma árvore binária real. Nenhuma "árvore é representada no meu programa como seqüências coincidindo com a saída esperada".

Você pode imprimir em um fluxo de saída ou retornar uma sequência que contenha a saída, sua escolha.

Aponta para o código mais curto, mas eu prefiro uma solução longa que funcione totalmente do que uma solução curta que funciona 90%.


Atualização para a recompensa:

Para a recompensa, eu (Otimizador) estou fazendo pequenas alterações:

  • A entrada pode ser de STDIN, ARGV ou argumento de função.
  • A saída precisa estar no STDOUT (ou console.logno JS)
  • Você pode assumir que a entrada está em uma forma de matriz, por exemplo. [1,2,3]ou[1 2 3]

Atualização 2 - A árvore binária deve realmente ser uma árvore de pesquisa binária. Como não mencionei isso inicialmente, permitirei que os usuários tratem a conversão de uma matriz normal em uma matriz de árvore de pesquisa binária como um programa separado e a contagem final de bytes será apenas para o programa receber a matriz como argumento e imprimi-la como uma árvore binária.

Anon.
fonte
Devemos usar várias barras de relacionamento foram apropriadas? Devemos usar o número mínimo de barras? Deve-se distinguir entre ter um único filho esquerdo e um único filho direito? Seria bom ter espaços à esquerda em cada linha de saída?
O que fazemos se a árvore não estiver completa (2 ^ n-1 nós para alguns n)? Alguns nós (quais?) Têm apenas um filho. Mas se é permitido ter nós com apenas um filho, é fácil fazer a árvore degenerada (1-2-3-4-5-6 abaixo e à direita, digamos).
Keith Randall
Como você o desenha para grandes números? Por exemplo30000,1000,499999
Mohsen

Respostas:

9

Fortran 77-1085 caracteres

      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

A árvore é representada na matriz de entrada tda maneira usual, raiz em 1, raiz-> esquerda em 2, raiz-> direita em 3 raiz-> esquerda-> esquerda em 4 ...

A saída deve caber em um terminal convencional com até 5 níveis de profundidade.

Eu uso exatamente uma barra entre cada par de nós, que parece bem bobo perto do topo quando existem quatro ou mais níveis. Eu permiti até três nós de dígitos.

Programa completo com comentários e um andaime de lançamento:

      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

Saída com entrada equivalente ao exemplo:

$ ./a.out 
         3             
     /      \      
     1       5     
      \    /  \  
       2   4   7 
dmckee
fonte
AJUDA por que esse idioma?
tomsmeding
9
Porque é tão pouco adequado ao golfe.
dmckee
5

CJam, 100 99 bytes

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];

A entrada deve ser uma lista de caracteres, sem nenhum caractere de controle ascii. Nós vazios são indicados por um espaço. Também deve ser uma árvore binária perfeita com exatamente 2 n -1 nós.

Exemplo:

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

Ou simplesmente use strings:

"63714 902 5  8 "

Resultado:

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

Explicação

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. ";

Script de conversão

[[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<']+

Aceita caracteres ou números de um dígito.

Exemplos (todos são iguais):

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

Resultado:

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

É uma construção de árvore cartesiana direta.

jimmy23013
fonte
Você pode simplesmente adicionar mais dois bytes e fazer a entrada de script de conversão como inteiros adequados em vez de caracteres :)
Optimizer
@Optimizer Editado para suportar ambos. Eu acho que os personagens fazem mais sentido, pois apenas suportam nomes de nós com um único caractere. Existem muito mais caracteres do que números de um dígito.
precisa saber é o seguinte
2

Python 2, 411 bytes

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:])

Nota: O primeiro nível de recuo é de 1 espaço, o segundo é uma guia.

Ligue fcom uma lista de cadeias de caracteres de um ou Nonemais, por exemplo. f(['1',None,'3']). A lista não pode estar vazia.

Isso deve obedecer às regras da recompensa.

Script do conversor:

Converte e matriz para o formato usado pela impressora em árvore binária. Exemplo:

$ 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

Exemplos:

Para executá-los, você deve ter o arquivo principal nomeado bt.pye o arquivo conversor nomeado 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
fonte
Você não está realmente criando a árvore binária. Apenas imprimindo a matriz como uma árvore binária. A saída da ['1','2','3','4','5','6','7','8','9']matriz não é o que você mostrou. Deveria ter 3como filho certo o 2qual é filho certo e o 1qual é um elemento raiz.
Optimizer
@Optimizer Da pergunta: "A entrada será fornecida como argumento para sua função. Não especificarei a estrutura exata da árvore, no entanto, deve ser utilizável como uma árvore binária real". Não vejo uma definição específica do formato de matriz usado.
Tyilo
A questão originalmente é sobre a impressão de uma árvore binária . Suas saídas não são árvores binárias. O formato da matriz não tem nada a ver com isso.
Optimizer
@ Otimizador, como eles não são árvores binárias? Da Wikipedia: uma árvore binária é uma estrutura de dados de árvore na qual cada nó tem no máximo dois filhos. Algum dos nós tem mais de dois filhos?
Tyilo
Ughh. Eu vejo agora. Eu acho que há um termo mal-entendido aqui. Mesmo nos exemplos iniciais, a saída é do formato de árvore de pesquisa binária . E minha recompensa também é apenas para uma árvore de pesquisa binária. Desculpe pela confusão lá.
Optimizer
1

APL, 125 caracteres

{⍵{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(×,*)≡⍵}

Exemplo:

{⍵{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' ()())())))

Testado aqui.

jimmy23013
fonte
Esse também é o script de conversão?
Optimizer
@Optimizer É necessário o formato de entrada de matriz aninhada, que provavelmente pode ser usada como árvore de pesquisa binária (mas não tenho certeza sobre a complexidade). Se eu precisar usar alguns formatos mais comuns ... talvez eu faça isso mais tarde.
jimmy23013
@Optimizer Agora, lendo a pergunta novamente, "matriz de árvore de pesquisa binária" significa a matriz de uma árvore binária completa em ordem de profundidade (ou outra coisa)? Não achei que fosse algo específico. E pesquisar esse termo não deu nada de útil.
jimmy23013
@ Optimizer Bem, isso foi exatamente o que eu quis dizer. Mas eu não acho que isso geralmente seja chamado de "matriz de árvore de pesquisa binária", mas apenas "um tipo de armazenamento de matriz de árvores binárias". Ele provavelmente precisa de algum esclarecimento ... E eu provavelmente vou corrigir esta resposta dias depois, talvez em outro idioma ...
jimmy23013
0

Ruby, 265 bytes

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

A versão @proudhaskeller, 269 bytes

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

Explicação

A versão detalhada:

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

Exemplo

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
])

dá:

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

(Ainda não escrevi o script de conversão.)

AlexRath
fonte
suas barras não estão exatamente no meio
proud haskeller
@proudhaskeller "do jeito que você quiser", achei que fica mais legal desse jeito. Você pode substituir s / 2 por (s + 1) / 2, se desejar.
AlexRath
Não, as barras na primeira linha não são exatamente em que ele média, nesta linha isso não é uma questão de arredondamento
haskeller orgulhoso
@proudhaskeller Se você substituir s / 2 por (s + 1) / 2, eles estarão exatamente no meio, mas ainda assim prefiro assim, pois faz com que os galhos mais à esquerda e à direita olhem em volta.
AlexRath
é contra as especificações ... #
21316 proud haskeller