Imprimir un árbol binario

18

Inspirado por una pregunta reciente sobre SO ...

Escriba una función para imprimir un árbol binario en el siguiente formato:

   3
 /   \
1     5
 \   / \
  2 4   6
  1. La salida debe consistir en una línea de nodos, seguido de una línea de /y \caracteres que indican relaciones, seguida de una línea de nodos, etc.
  2. Puede suponer que todos los nodos son representables como un solo carácter.
  3. Los nodos adyacentes en el nivel más bajo deben estar separados por al menos un espacio, los nodos más arriba deben estar separados según corresponda.
  4. Los nodos con dos hijos deben colocarse precisamente en el medio de sus hijos directos.
  5. Las barras de relación deben estar a medio camino entre el padre y el niño apropiado (redondee de la forma que desee).

Entrada:

La entrada se proporcionará como argumento para su función. No especificaré la estructura exacta del árbol, sin embargo, debe ser utilizable como un árbol binario real. No hay "árboles representados en mi programa como cadenas que coinciden con el resultado esperado".

Puede imprimir en una secuencia de salida o devolver una cadena que contenga la salida, su elección.

Apunta por el código más corto, pero preferiría una solución larga que funcione completamente que una solución corta que funcione al 90%.


Actualización para la recompensa:

Para la recompensa, yo (Optimizer) estoy haciendo pequeños cambios:

  • La entrada puede ser de STDIN, ARGV o argumento de función.
  • La salida debe estar en STDOUT (o console.logpara JS)
  • Puede suponer que la entrada está en forma de matriz, por ejemplo. [1,2,3]o[1 2 3]

Actualización 2 : el árbol binario debería ser un árbol de búsqueda binario. Como no mencioné esto inicialmente, permitiré a los usuarios tratar la conversión de una matriz normal en una matriz de árbol de búsqueda binaria como un programa separado y el recuento final de bytes solo será para que el programa tome la matriz como argumento e imprima como un árbol binario

Luego.
fuente
¿Deberíamos usar varias barras de relación apropiadas? ¿Debemos usar el número mínimo de barras? ¿Se debe distinguir entre tener un solo hijo izquierdo y un solo hijo derecho? ¿Estaría bien tener espacios iniciales en cada línea de salida?
¿Qué hacemos si el árbol no está completo (2 ^ n-1 nodos para algunos n)? Algunos nodos (¿cuáles?) Tienen un solo hijo. Pero si se nos permite tener nodos con un solo hijo, el árbol degenerado es fácil de hacer (1-2-3-4-5-6 hacia abajo y hacia la derecha, por ejemplo).
Keith Randall
¿Cómo lo dibujas para grandes números? Por ejemplo30000,1000,499999
Mohsen

Respuestas:

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

El árbol se representa en la matriz de entrada tde la manera habitual, raíz en 1, raíz-> izquierda en 2, raíz-> derecha en 3 raíz-> izquierda-> izquierda en 4 ...

La salida debe caber en un terminal convencional de hasta 5 niveles de profundidad.

Utilizo exactamente una barra entre cada par de nodos, que se ve bastante tonto cerca de la parte superior una vez que hay cuatro o más niveles. Permití nodos de hasta tres dígitos.

Programa completo con comentarios y un andamio de lanzamiento:

      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

Salida con entrada equivalente al ejemplo:

$ ./a.out 
         3             
     /      \      
     1       5     
      \    /  \  
       2   4   7 
dmckee
fuente
AYUDA por qué este idioma?
tomsmeding
99
Porque es muy poco adecuado para el golf.
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];

La entrada debe ser una lista de caracteres, sin caracteres de control ASCII. Los nodos vacíos se denotan por un espacio. También debe ser un árbol binario perfecto con exactamente 2 n -1 nodos.

Ejemplo:

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

O simplemente use cadenas:

"63714 902 5  8 "

Salida:

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

Explicación

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 conversión

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

Acepta caracteres o números de un solo dígito.

Ejemplos (todos son iguales):

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

Salida:

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

Es una construcción sencilla de árbol cartesiano.

jimmy23013
fuente
Simplemente puede agregar dos bytes más y hacer que la entrada del script de conversión sea un número entero adecuado en lugar de caracteres :)
Optimizer
@Optimizer Editado para admitir ambos. Creo que los caracteres tienen más sentido ya que solo admiten nombres de nodo con un solo carácter. Hay muchos más caracteres que números de un solo dígito.
jimmy23013
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: El primer nivel de sangría es 1 espacio, el segundo es una pestaña.

Llame fcon una lista de cadenas de un carácter o None's, por ejemplo. f(['1',None,'3']). La lista no puede estar vacía.

Esto debería obedecer las reglas de la recompensa.

Script de conversión:

Convierte y ordena al formato utilizado por la impresora de árbol binario. Ejemplo:

$ 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

Ejemplos:

Para ejecutar estos debe tener el archivo principal llamado bt.pyy el archivo convertidor llamado 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
fuente
En realidad no estás creando el árbol binario. Simplemente imprime la matriz como un árbol binario. El resultado de la ['1','2','3','4','5','6','7','8','9']matriz no es lo que mostraste. Debería tener 3como elemento 2secundario correcto el elemento secundario correcto del 1cual es un elemento raíz.
Optimizador
@Optimizer De la pregunta: "La entrada se proporcionará como un argumento para su función. No especificaré la estructura exacta del árbol, sin embargo, debe ser utilizable como un árbol binario real". No veo una definición específica del formato de matriz utilizado.
Tyilo
La pregunta original es acerca de imprimir un árbol binario . Sus salidas no son árboles binarios. El formato de la matriz no tiene nada que ver con eso.
Optimizador
@Optimizer, ¿cómo no son árboles binarios? De Wikipedia: un árbol binario es una estructura de datos de árbol en la que cada nodo tiene como máximo dos hijos. ¿Alguno de los nodos tiene más de dos hijos?
Tyilo
Ughh Ya lo veo. Creo que hay un término malentendido aquí. Incluso en los ejemplos iniciales, la salida es del formato del árbol de búsqueda binario . Y mi recompensa también es solo para un árbol de búsqueda binaria. Perdón por la confusión allí.
Optimizador
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(×,*)≡⍵}

Ejemplo:

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

Probado aquí.

jimmy23013
fuente
¿Es este el script de conversión también?
Optimizador
@Optimizer Toma el formato de entrada de matriz anidada, que probablemente puede usarse como árbol de búsqueda binario (pero no estoy seguro de la complejidad). Si debo usar algunos formatos más habituales ... tal vez lo haga más tarde.
jimmy23013
@Optimizer Ahora, leyendo la pregunta nuevamente, ¿"matriz de árbol de búsqueda binaria" significa la matriz de un árbol binario completo en orden de profundidad (o algo más)? No pensé que fuera algo específico. Y buscar este término no dio nada útil.
jimmy23013
@Optimizer Bueno, eso fue exactamente lo que quise decir. Pero no creo que generalmente se llame "matriz de árbol de búsqueda binaria", sino solo "un tipo de almacenamiento de matriz de árboles binarios". Es probable que tenga alguna aclaración ... Y probablemente voy a arreglar esto días después de respuesta, tal vez en otro idioma ...
jimmy23013
0

Rubí, 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

La versión @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

Explicación

La versión detallada:

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

Ejemplo

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

da:

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

(Todavía no he escrito el script de conversión).

AlexRath
fuente
sus barras no están exactamente en el medio
orgulloso haskeller
@proudhaskeller "redondo de la forma que quieras", pensé que se veía mejor de esta manera. Puede reemplazar s / 2 con (s + 1) / 2 si lo desea.
AlexRath
No, las barras en la primera fila no están exactamente en el medio, en esta fila esto no es cuestión de redondeo
orgulloso Haskeller
@proudhaskeller Si reemplaza s / 2 con (s + 1) / 2, están exactamente en el medio, pero aún así prefiero de esta manera porque hace que las ramas más a la izquierda y a la derecha se vean redondas.
AlexRath
está en contra de la especificación ...
haskeller orgullo