URI PROBLEMA 1466 - Percurso em Árvore por Nível SOLUÇÃO EM C

URI Online Judge | 1466

Percurso em Árvore por Nível

Por Neilor Tonin, URI  Brasil

Timelimit: 2

Em uma árvore binária, o percurso por nível é um percurso denominado breadth first search (BFS) ou em português, busca em largura, a qual seria não-recursiva por natureza. Este percurso utiliza uma fila ao invés de pilha para armazenar os próximos 2 nodos que devem ser pesquisados (filho à esquerda e à direita). Esta é a razão pela qual você deve percorrer os nodos na ordem FIFO ao invés da ordem LIFO, obtendo desta forma a recursão.

Portanto nossa tarefa aqui, após algumas operações de inserção sobre uma árvore binária de busca (pesquisa), é imprimir o percurso por nível sobre estes nodos. Por exemplo, uma entrada com a sequência de valores inteiros: 8 3 10 14 6 4 13 7 1 resultará na seguinte árvore:

Com a saída de uma listagem por nível: 8 3 10 1 6 14 4 7 13.

Entrada

A entrada contém vários casos de teste. A primeira linha da entrada contém um inteiro C (C ≤ 1000), indicando o número de casos de teste que virão a seguir. Cada caso de teste é composto por 2 linhas. A primeira linha contém um inteiro N (1 ≤ N ≤ 500) que indica a quantidade de números que deve compor cada árvore e a segunda linha contém N inteiros distintos e não negativos, separados por um espaço em branco.

Saída

Para cada caso de teste de entrada você deverá imprimir a mensagem "Case n:", onde n indica o número do caso de teste seguido por uma linha contendo a listagem por nível dos nodos da árvore, conforme o exemplo abaixo.

Obs: Não deve haver espaço em branco após o último item de cada linha e há uma linha em branco após cada caso de teste, inclusive após o último. A árvore resultante não terá nodos repetidos e também não terá mais do que 500 níveis.

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

#include <string.h>

#include <ctype.h>

#include <math.h>

#include <time.h>

#define MIN(a, b) ((a) < (b) ?  (a) : (b))

#define MAX(a, b) ((a) > (b) ?  (a) : (b))

#define ABS(a) ((a) <  0  ? -(a) : (a))

#define IMPAR(a) ((a)&1)

#define CTOI(a) ((a) - '0')

#define ITOC(a) ((a) + '0')

#define TRUE 1

#define FALSE 0

struct RFolha {

struct RFolha *esq, *dir;

int valor;

};

typedef struct RFolha TFolha;

void Imprimir(TFolha *);

void Destruir(TFolha *);

TFolha *AcharPai(TFolha *, int);

int main()

{

TFolha *raiz, *aux, *pai;

int C, N, i, valor;

#ifdef DEBUG

double tI_ = clock();

#endif

scanf("%d", &C);

for(i = 1; i <= C; i++)

{

raiz = NULL;

scanf("%d", &N);

while(N--)

{

scanf("%d", &valor);

aux = (TFolha *) malloc(sizeof(TFolha));

aux->valor = valor;

aux->esq = NULL;

aux->dir = NULL;

pai = AcharPai(raiz, valor);

if(pai == NULL)

raiz = aux;

else

if(valor <= pai->valor)

pai->esq = aux;

else

pai->dir = aux;

}

printf("Case %d:\n", i);

Imprimir(raiz);

Destruir(raiz);

}

#ifdef DEBUG

printf("Tempo: %.1lf %.1lf\n", clock() - tI_, (clock() - tI_) / CLK_TCK);

#endif

return 0;

}

void Imprimir(TFolha *raiz)

{

TFolha *fila[500];

int i = -1, n = 0;

if(raiz == NULL)

return;

fila[++i] = raiz;

while(n <= i)

{

if(fila[n]->esq != NULL)

fila[++i] = fila[n]->esq;

if(fila[n]->dir != NULL)

fila[++i] = fila[n]->dir;

if(n > 0)

printf(" ");

printf("%d", fila[n++]->valor);

}

printf("\n\n");

}

void Destruir(TFolha *raiz)

{

if(raiz != NULL)

{

Destruir(raiz->esq);

Destruir(raiz->dir);

free(raiz);

}

}

TFolha *AcharPai(TFolha *raiz, int valor)

{

if(raiz == NULL)

return NULL;

else

if(valor <= raiz->valor)

if(raiz->esq == NULL)

return raiz;

else

return AcharPai(raiz->esq, valor);

else

if(raiz->dir == NULL)

return raiz;

else

return AcharPai(raiz->dir, valor);

}