Tópico: Essa é pros feras! (Desafio de programação)

Pois bem, aqui está a solução:

[code:1:0d13be532a]procedure TTreeTask.Solve;
const
MaxN = 10000;
var
TestNumber, N, I: Cardinal;
ValuesByDepth: array[0..MaxN - 1] of Smallint;
Value, InsertPos: Cardinal;
Branch: Integer;
First: Boolean;
begin
TestNumber := 1;
repeat
// recebe o número de ítems
N := GetUInt;
if N = 0 then Exit;
// inicializa o vetor com flags
FillChar(ValuesByDepth, SizeOf(ValuesByDepth), -1);

// para cada elemento
for I := 1 to N do
begin
// lê o valor do ítem
Value := GetUInt;
// posição inicial, assume raíz
InsertPos := 0;

repeat
// verifica qual de ramo faz parte
Branch := GetInt;
// calcula a próxima posição
if Branch = -1 then
// filho esquerdo
InsertPos := InsertPos * 2 + 1
else if Branch = 1 then
// filho direito
InsertPos := InsertPos * 2 + 2;
until Branch = 0;

// insere o item
ValuesByDepth[InsertPos] := Value;
end;

// neste momento todos os nós já foram incluídos no array,
// nós de um nível sempre aparecendo antes que os do próximo nível

OutputLn([´Teste ´, TestNumber]);
First := True;
for I := 0 to MaxN do
begin
// testa se o nó existe na árvore
if ValuesByDepth[I] >= 0 then
begin
if First then
First := False
else
OutputText(´ ´);
// dá saída do valor
Output([ValuesByDepth[I]]);
end;
end;
OutputTextLn();
OutputTextLn();

Inc(TestNumber);
until False;
end;[/code:1:0d13be532a]

Vou tentar explicar:

O objetivo era ler os dados de entrada e gerar uma lista com os valores na ordem em que os níveis estão dispostos, isto é, o elemento raíz é o primeiro, seguido de seus dois filhos imediatos, os filhos do primeiro filho da raíz, os filhos do segundo, e assim por diante.

A árvore detalhada aqui não contém nada de especial, quando a ordenação e posicionamento de valores, é apenas uma estrutura formada por ´nós´, os quais contém de 0 a 2 filhos. Exibida, como de costume, com a raíz no topo(nível 0), e níveis posteriores abaixo.

A questão principal era escolher a representação da árvore. Árvores geralmente são implementadas via ponteiros de registros, mas dessa forma, os custos em espaço(na construção), e tempo(na ordenação) seriam maiores. A estrutura concreta em que o problema melhor se beneficiaria é um vetor(array, aqui indexados de 0 a N - 1), onde cada célula correponde a um nó na árvore. A raíz fica na posição zero, seus filhos esquerdo e direito nas posições 1 e 2, respectivamente. Cada nó, exceto a raíz, possui um nó pai, que está na posição chão(p / 2), onde p é a posição do nó na árvore. Os filhos de um nó estarão, se algum, nas posições 2p e 2p + 1.

A árvore linearizada, com o caminho do valor 2 até a raíz, em vermelho:

+-----------------------------------------------------+
| [color=red:0d13be532a]5[/color:0d13be532a] | [color=red:0d13be532a]4[/color:0d13be532a] | 8 | [color=red:0d13be532a]11[/color:0d13be532a] |   | 13 | 4 | 7 | [color=red:0d13be532a]2[/color:0d13be532a] |   |   |   | 1 |
+-----------------------------------------------------+
  0   1   2   3    4   5    6   7   8   9  10  11  12

Veja que a árvore não está compactada, pois há células vazias, que significam que não há um valor nesta posição na árvore(o nó não possui este filho).

Na implementação, um array[0..N - 1] of Smallint, mantém a árvore, com o valor -1 sendo usado para sinalizar nós não-existentes.

A partir da descrição do caminho do nó até a raíz, é possível realizar a inserção na posição correta. O processo dá-se por calcular a posição relativa do nó, começando da base em direção ao topo(raíz). A posição relativa r é iniciada em 0, e recalculada como 2r + 1 para nós esquerdos(-1), e como 2r + 2 para nós direitos(1). O processo acaba ao chegar na indicação 0, onde o valor é inserido no vetor na posição r.

Por fim, para obter a solução da tarefa, basta percorrer o vetor de 0 a N - 1, escolhendo o valor sempre que for diferente de -1.