Mais percursos em árvores

Eis aqui mais alguns percursos básicos em árvores: busca em largura e versão iterativa do pré-ordem.

/**
* MAC 2301 - Laboratório de Programação
*
* Exercício extra da aula 5-b
*
* Assunto: Mais alguns percursos em árvores:
*          pré-ordem iterativo
*          busca em largura
*
**/

#include "pilha.h"
#include "fila.h"

void visita(noh *umNoh)
{
 if(umNoh != NULL)
   printf("  %c", umNoh->info);
 else
   printf(" [nulo]");
}

/**
* Versão não recursiva da pré-ordem
* Parecida com uma busca chamada de "busca em profundidade"
* A diferença é que na busca em profundidade, não há regras definidas
* sobre qual ramo explorar primeiro (direito ou esquerdo)
**/
void preOrdemIterativo(noh *raiz)
{
 pilha p;
 noh* varre;
 varre = malloc(sizeof(noh));

 if(raiz != NULL)
 {
   inicializaPilha(&p);
   empilha(*raiz, &p);
  
   while(!pilhaVazia(p))
   {
     desempilha(varre, &p);
     visita(varre);
    
     /* tenta empilhar filho direito */
     if(varre->filhoDir != NULL)
     {
       if(empilha(*(varre->filhoDir), &p) != OK)
       {
         printf("\n\n **Erro: espaço insuficiente\n");
         return;
       }
     }
    
     /* tenta empilhar filho esquerdo */
     if(varre->filhoEsq != NULL)
     {
       if(empilha(*(varre->filhoEsq), &p) != OK)
       {
         printf("\n\n **Erro: espaço insuficiente\n");
         return;
       }
     }
   }
 }
}


/**
* Percurso em nível, cujo código é quase idêntico ao da
* pré-ordem iterativoo, apenas substituindo a pilha por uma fila
* Também conhecido como busca em largura. Não tem versão recursiva
**/
void percursoEmNivel(noh *raiz)
{
 fila f;
 noh* varre = malloc(sizeof(noh));

 if(raiz != NULL)
 {
   inicializaFila(&f);
   enfileira(*(raiz), &f);
  
   while(!filaVazia(f))
   {
     desenfileira(varre, &f);
     visita(varre);
    
     /* tenta enfileirar o filho esquerdo */
     if(varre->filhoEsq != NULL)
     {
       if(enfileira(*(varre->filhoEsq), &f) != OK)
       {
         printf("\n\n **Erro: espaço insuficiente\n");
         return;
       }
     }
    
     /* tenta enfileirar o filho direito */
     if(varre->filhoDir != NULL)
     {
       if(enfileira(*(varre->filhoDir), &f) != OK)
       {
         printf("\n\n **Erro: espaço insuficiente\n");
         return;
       }
     }
   }
 }
}

int main()
{
 /**
  * vamos criar a seguinte árvore:
  *
             ______1______
            /             \
         __2__           __3__
        /     \         /     \
       4       5       6       7
      / \     / \     / \     / \
     8   9   A   B   C   D   E   F
 *
 **/

 noh *varre;
 noh *raiz = malloc(sizeof(noh));
 varre = raiz;
 varre->info = '1';
 varre->filhoEsq = malloc(sizeof(noh));
 varre->filhoDir = malloc(sizeof(noh));

 varre = varre->filhoEsq;
 varre->info = '2';
 varre->filhoEsq = malloc(sizeof(noh));
 varre->filhoDir = malloc(sizeof(noh));

 varre = varre->filhoEsq;
 varre->info = '4';
 varre->filhoEsq = malloc(sizeof(noh));
 varre->filhoDir = malloc(sizeof(noh));

 varre = varre->filhoEsq;
 varre->info = '8';
 varre->filhoEsq = NULL;
 varre->filhoDir = NULL;

 varre = ((raiz->filhoEsq)->filhoEsq)->filhoDir;
 varre->info = '9';
 varre->filhoEsq = NULL;
 varre->filhoDir = NULL;

 varre = (raiz->filhoEsq)->filhoDir;
 varre->info = '5';
 varre->filhoEsq = malloc(sizeof(noh));
 varre->filhoDir = malloc(sizeof(noh));

 varre = varre->filhoEsq;
 varre->info = 'A';
 varre->filhoEsq = NULL;
 varre->filhoDir = NULL;

 varre = ((raiz->filhoEsq)->filhoDir)->filhoDir;
 varre->info = 'B';
 varre->filhoEsq = NULL;
 varre->filhoDir = NULL;

 varre = raiz->filhoDir;
 varre->info = '3';
 varre->filhoEsq = malloc(sizeof(noh));
 varre->filhoDir = malloc(sizeof(noh));

 varre = varre->filhoEsq;
 varre->info = '6';
 varre->filhoEsq = malloc(sizeof(noh));
 varre->filhoDir = malloc(sizeof(noh));

 varre = varre->filhoEsq;
 varre->info = 'C';
 varre->filhoEsq = NULL;
 varre->filhoDir = NULL;

 varre = ((raiz->filhoDir)->filhoEsq)->filhoDir;
 varre->info = 'D';
 varre->filhoEsq = NULL;
 varre->filhoDir = NULL;

 varre = (raiz->filhoDir)->filhoDir;
 varre->info = '7';
 varre->filhoEsq = malloc(sizeof(noh));
 varre->filhoDir = malloc(sizeof(noh));

 varre = varre->filhoEsq;
 varre->info = 'E';
 varre->filhoEsq = NULL;
 varre->filhoDir = NULL;

 varre = ((raiz->filhoDir)->filhoDir)->filhoDir;
 varre->info = 'F';
 varre->filhoEsq = NULL;
 varre->filhoDir = NULL;

 /**
  * Agora imprimiremos na tela dois percursos nesta árvore,
  * partindo da raiz: em profundidade e em largura
  **/

 printf("\n\n");
 printf("  Profundidade: ");
 printf("\n             ");

 preOrdemIterativo(raiz);

 printf("\n\n");
 printf("       Largura: ");
 printf("\n             ");
  
 percursoEmNivel(raiz);

 printf("\n\n\n\n  ");

 system("pause");

 /*
 liberaArvore(raiz);  // to do (por fazer)
 */

 free(varre);

 return 0;
}

/* arquivo base.h */

#ifndef JA_INCLUIU_ESTA_BASE

 #include 
 #include 

 #define JA_INCLUIU_ESTA_BASE 1
 #define OVERFLOW 1
 #define UNDERFLOW -1
 #define OK 0
 #define MAX 100

 typedef struct node
 {
    char info;
    struct node *filhoEsq;
    struct node *filhoDir;
 } noh;

/* arquivo fila.h */

#include "base.h"

typedef struct queue
{
 int primeiro;
 int ultimo;
 noh f[MAX];
} fila;

/**
* função booleana que devolve um valor diferente
* de zero se a fila está vazia e zero c.c.
**/
int filaVazia(fila sobInvestigacao);

void inicializaFila(fila *umaFila);

int enfileira(noh novo, fila *umaFila);

/* arquivo pilha.h */

#include "base.h"

typedef struct stack
{
 int topo;
 noh p[MAX];
} pilha;

/**
* função booleana que devolve um valor diferente
* de zero se a pilha está vazia e zero c.c.
**/
int pilhaVazia(pilha sobInvestigacao);

void inicializaPilha(pilha *umaPilha);

int empilha(noh novo, pilha *umaPilha);

/* arquivo fila.c */

#include "fila.h"

/**
* função booleana que devolve um valor diferente
* de zero se a fila está vazia e zero c.c.
**/
int filaVazia(fila sobInvestigacao)
{
 return (sobInvestigacao.primeiro == -1 &&
         sobInvestigacao.ultimo == -1);
}

void inicializaFila(fila *umaFila)
{
 if(umaFila == NULL)
   umaFila = malloc(sizeof(fila));
 umaFila->primeiro = -1;
 umaFila->ultimo = -1;
}

int enfileira(noh novo, fila *umaFila)
{
 int temp;
 if(filaVazia(*umaFila))
 {
   umaFila->primeiro = 0;
   umaFila->ultimo = 0;
   umaFila->f[0] = novo;
   return OK;
 }
 else
 {
   temp = (umaFila->ultimo + 1) % MAX;
   if(temp == umaFila->primeiro)
     return OVERFLOW;
   else
   {
     umaFila->ultimo = temp;
     umaFila->f[temp] = novo;
     return OK;
   }
 }
}

int desenfileira(noh *desenfileirado, fila *umaFila)
{
 if(filaVazia(*umaFila))
   return UNDERFLOW;
 else
 {
   *desenfileirado = (umaFila->f)[umaFila->primeiro];
   if(umaFila->primeiro == umaFila->ultimo)
   {
     inicializaFila(umaFila);
   }
   else
     umaFila->primeiro = (umaFila->primeiro +1) % MAX ;
   return OK;
 }
}


/* arquivo pilha.c */
#include "pilha.h"

/**
* função booleana que devolve um valor diferente
* de zero se a pilha está vazia e zero c.c.
**/
int pilhaVazia(pilha sobInvestigacao)
{
 return (sobInvestigacao.topo == 0);
}

void inicializaPilha(pilha *umaPilha)
{
 if(umaPilha == NULL)
   umaPilha = malloc(sizeof(pilha));
 umaPilha->topo = 0;
}

int empilha(noh novo, pilha *umaPilha)
{
 if(umaPilha != NULL)
 {
   if(umaPilha->topo == MAX)
     return OVERFLOW;
   else
   {
     (umaPilha->p)[umaPilha->topo] = novo;
     (umaPilha->topo)++;
     return OK;
   }
 }
 else
   return OVERFLOW;
}

int desempilha(noh *desempilhado, pilha *umaPilha)
{
 if(umaPilha != NULL)
 {
   if(umaPilha->topo == 0)
     return UNDERFLOW;
   else
   {
     (umaPilha->topo)--;
     *desempilhado = (umaPilha->p)[umaPilha->topo];
     return OK;
   }
 }
 else
   return UNDERFLOW;
}



int desempilha(noh *desempilhado, pilha *umaPilha);


int desenfileira(noh *desenfileirado, fila *umaFila);

#endif