Os testes para as listas de exercícios serão feitos via arquivos.
Seguem abaixo as especificações deles.

 
 

       O arquivo de entrada consiste de vários conjuntos de dados. Cada conjunto de dados contém duas linhas: a primeira linha contém o número de elementos a serem inseridos e a segunda linha contém os elementos que serão inseridos, na ordem em que aparecem, na árvore AVL. O conjunto de dados que iniciar com 0 (zero) como número de elementos indica fim de execução e esse conjunto não deve ser processado.
 

Entrada exemplo:
3
2 3 1
5
1 2 3 4 5
10
2 1001 5 13 14 15 9 10 102 103
20
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
1
10000
0

Saída exemplo correspondente à entrada acima:
Conjunto #1
      3
2
      1
 

Conjunto #2
            5
      4
            3
2
      1
 

Conjunto #3
            1001
                  103
      102
            15
14
                  13
            10
                  9
      5
            2
 

Conjunto #4
                  20
            19
                  18
      17
                  16
            15
                  14
13
                        12
                  11
                        10
            9
                        8
                  7
                        6
      5
                  4
            3
                  2
                        1
 

Conjunto #5
10000
 

Obs.:

• Não se esqueçam de desalocar todos os nós da árvore entre cada processamento;
• Não serão inseridos valores iguais;
• O formato dos arquivos de saída deverá seguir EXATAMENTE o padrão estabelecido nos exemplos acima. Para tanto segue a função de impressão (in-order).

Exemplo (referência) de código fonte para impressão:

// Um exemplo simples de uma árvore binária
struct arvore
{
      int valor;
      struct arvore * dir;
      struct arvore * esq;
}

...

void imprimir(struct arvore * no, int l)
{
      int i;

      // Imprime a sub-árvore a direita
      imprimir(no->dir,l+1);

      // Imprime o espa&ccetil;amento do elemento - reparem que são 6 (seis) espaços
      for(i=0;i<l;++i)
            fprintf(fpout,"      ");

      fprintf(fpout,"%d\n",no->valor);

      // Imprime a sub-árvore a esquerda
      imprimir(no->esq,l+1);
}

       A primeira linha do arquivo de entrada irá conter o número natural K de instâncias que serão usadas no teste. As linhas subseqüentes conterão K blocos de instâncias de Mergesort. Cada instância contém uma linha com a quantidade N (2 <= N <= 1024) de números a serem ordenados, seguida de N números naturais (a partir da linha seguinte à que contém N). Só serão ordenados números maiores que 0 (zero) e menores que 30.000.
 

Entrada exemplo:
5
10
3 5 2 6 7 20 19 22 100 1
7
6 7 20 19 22 100 1
15
3 5 2 6 7 20 19 22 100 1 101 102 202 303 404
2
2 1
4
4 3 2 1

Saída exemplo correspondente à entrada acima:
1 2 3 5 6 7 19 20 22 100
1 6 7 19 20 22 100
1 2 3 5 6 7 19 20 22 100 101 102 202 303 404
1 2
1 2 3 4

Obs.:

• O formato dos arquivos de saída deverá seguir EXATAMENTE o padrão estabelecido nos exemplos acima.
• Dica: o algoritmo é mais facilmente implementado quando a entrada tem tamanho potência de 2.
• Trabalhem com a primeira potência de 2 maior que o número de elementos a serem ordenados. (Ex. para ordenar 10 números, trabalhe com 16 posições).

       A resposta deste exercício deve ser entregue em papel impresso junto com o disquete que contém as questões (1) e (2).
       Para cada um dos itens, dê uma justificativa baseada na definição formal dada em sala.
       Seja objetivo (vá direto ao ponto, sem divagações) e rigoroso na sua justificativa.