En informática, a menudo utilizamos árboles en muchas formas y representaciones diferentes. Los tres métodos principales para serializar árboles binarios son la notación de prefijo, infijo y postfijo. Por ejemplo, el siguiente árbol binario:

  _{(fuente: Olimpiada holandesa en informática, finales, 2012/13)}

se puede representar en notación de prefijo como abrxdbe, en infijo como rbxabdey en postfix como rxbbeda.

En este caso, se enfrenta a un árbol binario completo representado en notación infija . Su tarea es convertir este árbol a notación de prefijo . Su entrada en stdin será de 2 ⁿ -1 caracteres en minúscula del alfabeto, az y no más, terminados con un carácter de nueva línea, para cualquier número entero n tal que 1 ≤ n ≤ 16. Por lo tanto, el número máximo de caracteres que obtendrá es 65535. Salida del árbol a stdout de la misma manera, pero luego en formato de prefijo.

Este es el código de golf, por lo que el código más corto, contado en bytes, ganará. Los votos actuarán como un desempate, y si esos empatan también, la fecha y hora de envío.

GolfScript, 23 caracteres

.,\{;).2base{)!}do}$/n-

Esta solución utiliza un enfoque diferente al de Howard: básicamente, ordena los caracteres de entrada de acuerdo con la lista de ramas necesarias para alcanzar ese carácter desde la raíz del árbol.

Tenga en cuenta que se requiere la nueva línea al final de la entrada (es decir, la longitud de la entrada debe ser una potencia de dos). Se n-requiere al final del código para suprimir una nueva línea adicional al comienzo de la salida; Si dicha nueva línea es aceptable, esos caracteres se pueden omitir para obtener una puntuación de 21 caracteres.

Como de costumbre, puede probar este código en línea.

Explicación:

• .,\calcula la longitud de la entrada y la mueve debajo de la cadena de entrada en la pila. Se utilizará como el valor inicial del contador de bucle utilizado para construir las claves de clasificación a continuación. (El código se basa en que esto es una potencia de dos; de lo contrario, la manipulación de bits a continuación no producirá los resultados esperados. Sin embargo, cualquier potencia suficientemente grande de dos funcionaría).

• { }$ ordena los caracteres en la cadena de entrada de acuerdo con la clave de clasificación calculada dentro del bloque:

  • ;simplemente tira el carácter dado como entrada al bloque; Aquí no nos importan los valores reales de los caracteres, solo sus posiciones dentro de la cadena.

  • ). incrementa el contador de bucle en la pila (que se inicializó a la longitud de la cadena de entrada) y hace una copia de él.

  • 2base convierte esta copia en una matriz de bits (omitiendo los ceros iniciales; es por eso que debemos comenzar a contar desde una potencia lo suficientemente grande de dos, en lugar de simplemente desde cero).

  • {)!}docorta repetidamente el bit más bajo de la matriz hasta que el bit cortado sea a 1.

  Como las claves de clasificación resultantes son matrices, las $compara lexicográficamente. Así, por ejemplo, la matriz [1](que corresponde al nodo raíz) se ordena antes [1 0](que corresponde al hijo izquierdo del nodo raíz) y [1 1](el hijo derecho del nodo raíz).

• Al final, /se deshace del contador de bucles usándolo como la longitud de los fragmentos para dividir la cadena de salida en (¡gracias, Peter!), Y n-quita la nueva línea de la cadena de entrada ordenada. (El intérprete de GolfScript agregará otra nueva línea a la salida después de imprimir el contenido de la pila).

GolfScript, 28 caracteres

{.,1>{.,)2//([)\c]\~c+}*}:c~

Puede probar el código en línea .

Código anotado:

# define an operator c acting on the top of stack which does the conversion
{
  # if the input string is more than a single character
  .,1>{
    # split string into two halves (rounded up)
    .,)2//   
    # take first part last character
    ([)
    # take first part rest and call c recursively
    \c]
    # get second part
    \~
    # call c recursively on second part
    c
    # join all three together 
    +
  }*
}:c
# call c
~       

GolfScript (29 caracteres)

{.,1>{.,)2//~\[)](f@f++}*}:f~

Demostración en línea

Funciona con o sin la nueva línea final en la entrada.

APL (48)

(Sí, el juego de caracteres APL cabe en un byte ).

{1=⍴⍵:⍵⋄(⊃a),⊃,/∇¨1↓a←1⌽⌽⍵⊂⍨(⍳⍴⍵)∊1,0 1+⌈.5×⍴⍵}⍞

Explicación:

• {... }⍞: leer entrada, alimentar a función
• 1=⍴⍵:⍵: si la longitud de entrada es una, hemos terminado
• ⋄: de lo contrario:
• (⍳⍴⍵)∊1,0 1+⌈.5×⍴⍵: crea un campo de bits de lugares para dividir la entrada (primer carácter, carácter medio y carácter más allá del carácter medio)
• ⍵⊂⍨: dividir la entrada en estos lugares
• a←1⌽⌽: gire las matrices secundarias para que el carácter central sea el primero, la mano izquierda sea la segunda y la derecha la tercera, y almacene en a.
• ⊃,/∇¨1↓a: ejecute la función nuevamente en los dos últimos elementos ay concatene los resultados
• (⊃a),: y concatenar eso al primer elemento en a

Python 3 - 76

def f(x):a=len(x)//2;return x and x[a]+f(x[:a])+f(x[a+1:])
print(f(input()))

C, 108 caracteres

Mi código usa una función recursiva, que siempre imprime el carácter en el medio del búfer, y se llama a sí mismo con la parte de la cadena antes y la parte de la cadena después del carácter impreso. (Divide y conquistaras)

char b[65536];d(s,e){int c=s+(e-s)/2;putchar(b[c]);if(c^s)d(s,c-1),d(c+1,e);}main(){gets(b);d(0,strlen(b));}

sin golf:

char b[65536];
d(s,e){
    int c=s+(e-s)/2;
    putchar(b[c]);
    if(c^s)d(s,c-1),d(c+1,e);
}
main(){
    gets(b);
    d(0,strlen(b));
}