Em informática, geralmente usamos árvores de muitas formas e representações diferentes. Os três principais métodos de serialização de árvores binárias são notação de prefixo, infixo e postfix. Por exemplo, a seguinte árvore binária:

  _{(fonte: Olimpíada Holandesa de Informática, finais, 2012/13)}

pode ser representado na notação de prefixo como abrxdbe, no infixo como rbxabdee no postfix como rxbbeda.

Nesse caso, você é confrontado com uma árvore binária completa representada na notação infix . Sua tarefa é converter essa árvore em notação de prefixo . Sua entrada no stdin será de 2 ⁿ -1 caracteres do alfabeto em minúsculas, az e não mais, terminada com um caractere de nova linha, para qualquer número inteiro n tal que 1 ≤ n ≤ 16. Portanto, o número máximo de caracteres que você obterá é 65535. Envie a árvore para stdout da mesma maneira, mas depois no formato de prefixo.

Este é o código golf, portanto o código mais curto, contado em bytes, vencerá. Os votos atuam como desempate e, se esses empates também, data e hora do envio.

GolfScript, 23 caracteres

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

Essa solução usa uma abordagem diferente da de Howard: basicamente, classifica os caracteres de entrada de acordo com a lista de ramificações necessárias para alcançar esse caractere a partir da raiz da árvore.

Observe que a nova linha no final da entrada é necessária (ou seja, o comprimento da entrada deve ser uma potência de dois). O n-no final do código é necessário para suprimir uma nova linha extra no início da saída; se essa nova linha for aceitável, esses caracteres poderão ser omitidos para uma pontuação de 21 caracteres.

Como de costume, você pode testar esse código online.

Explicação:

• .,\calcula o comprimento da entrada e a move abaixo da string de entrada na pilha. Será usado como o valor inicial do contador de loop usado para construir as chaves de classificação abaixo. (O código baseia-se em poder de dois; caso contrário, a manipulação de bits abaixo não produzirá os resultados esperados. Porém, qualquer poder suficientemente grande de dois funcionaria.)

• { }$ classifica os caracteres na sequência de entrada de acordo com a chave de classificação calculada dentro do bloco:

  • ;apenas joga fora o caractere dado como entrada para o bloco; não nos importamos com os valores reais dos caracteres aqui, apenas com suas posições dentro da string.

  • ). incrementa o contador de loop na pilha (que foi inicializada no comprimento da sequência de entrada) e faz uma cópia dela.

  • 2base converte essa cópia em uma matriz de bits (omitindo zeros à esquerda; é por isso que precisamos começar a contar com uma potência suficientemente grande de dois, em vez de simplesmente com zero).

  • {)!}docorta repetidamente o bit mais baixo da matriz até que o bit cortado seja a 1.

  Como as chaves de classificação resultantes são matrizes, as $compara lexicograficamente. Assim, por exemplo, a matriz [1](que corresponde ao nó raiz) é classificada antes [1 0](que corresponde ao filho esquerdo do nó raiz) e [1 1](o filho direito do nó raiz).

• No final, /elimina o contador de loop, usando-o como o comprimento dos pedaços para dividir a sequência de saída (obrigado, Peter!) E n-retira a nova linha da sequência de entrada classificada. (O intérprete GolfScript acrescentará outra linha nova à saída depois de imprimir o conteúdo da pilha.)

GolfScript, 28 caracteres

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

Você pode testar o código online .

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~

Demonstração online

Funciona com ou sem a nova linha à direita na entrada.

APL (48)

(Sim, o conjunto de caracteres APL cabe em um byte .)

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

Explicação:

• {... }⍞: leia a entrada, alimente para funcionar
• 1=⍴⍵:⍵: se o comprimento da entrada for um, terminamos
• ⋄: de outra forma:
• (⍳⍴⍵)∊1,0 1+⌈.5×⍴⍵: crie um campo de bits para dividir a entrada (primeiro caractere, caractere do meio e caractere após o caractere do meio)
• ⍵⊂⍨: divida a entrada nesses locais
• a←1⌽⌽: gire as sub-matrizes para que o caractere do meio seja o primeiro, a mão esquerda seja a segunda e a mão direita seja a terceira e armazene a.
• ⊃,/∇¨1↓a: execute a função novamente nos dois últimos elementos ae concatene os resultados
• (⊃a),: e concatenar isso para o primeiro item em 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

Meu código usa uma função recursiva, que sempre imprime o caractere no meio do buffer e se chama com a parte da string anterior e a parte da string após o caracter impresso. (Dividir e conquistar)

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));}

ungolfed:

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));
}