Percurso em árvores

Uma estrutura de dados bastante comum são as árvores. Temos de vários tipos (binárias, árvores B, árvores rubro-negra, etc), mas todas elas dispõem seus elementos de forma hierárquica: um elemento raiz tem ligação com outros elementos - chamados de filhos, que por sua vez têm seus próprios filhos e assim por diante.

Existem também várias formas de se percorrer os elementos de uma árvore. As mais intuitivas são implementadas aqui:

/**
* MAC 2301 - Laboratório de Programação
*
* Exercício da aula 5
* Assunto: Percursos (recursivos) em árvores binárias
*
* Aplicações:
*    pré-ordem -> notação polonesa
*    pós-ordem -> calcular altura de árveres
*    ordem simétrica -> parentizar uma expressão
*
**/

#include 
#include 

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

/**
* Escrita de uma expressão aritmética (dada numa árvore) em notação polonesa,
* percorrendo a árvore em pré-ordem.
* Pseudo-código:
*              
*    pré-ordem(nó)
*    {
*       visita(nó)
*       pos-ordem(nó.filhoEsq)
*       pos-ordem(nó.filhoDir)
*    }
**/
void imprimeEmNotacaoPolonesa(noh raiz)
{
 printf(" %c", raiz.info);
 if(raiz.filhoEsq != NULL)
   imprimeEmNotacaoPolonesa(*(raiz.filhoEsq));
 if(raiz.filhoDir != NULL)        
   imprimeEmNotacaoPolonesa(*(raiz.filhoDir));
}

/**
* Cálculo da altura de uma árvore percorrendo-a em pós-ordem.
* Pseudo-código:
*              
*    pós-ordem(nó)
*    {
*       pos-ordem(nó.filhoEsq)
*       pos-ordem(nó.filhoDir)
*       visita(nó)
*    }
**/
int altura(noh raiz)
{
 int alturaDir;
 int alturaEsq;

 alturaDir = 0;
 alturaEsq = 0;

 if(raiz.filhoEsq != NULL)
   alturaEsq = altura(*(raiz.filhoEsq));
 if(raiz.filhoDir != NULL)
   alturaDir = altura(*(raiz.filhoDir));

 return maximo(alturaEsq, alturaDir) + 1;
}

/* função auxiliar */
int maximo(int um, int outro)
{
 if(um > outro)
   return um;
 return outro;
}

/**
* Parentização de uma expressão aritmética dada
* numa árvore percorrendo-a em ordem simétrica.
* Pseudo-código:
*              
*    ordem-simétrica(nó)
*    {
*       pos-ordem(nó.filhoEsq)
*       visita(nó)
*       pos-ordem(nó.filhoDir)
*    }
**/
void parentiza(noh raiz)
{
 if(raiz.filhoEsq != NULL)
 {
   printf("(");
   parentiza(*(raiz.filhoEsq));
 }

 printf("%c", raiz.info);

 if(raiz.filhoDir != NULL)
 {
   parentiza(*(raiz.filhoDir));
   printf(")");
 }
}

int main()
{
 /* vamos criar a seguinte árvore:
  *
          ______+______
         /             \
      __*__           __%__
     /     \         /     \
    +       -       +       *
   / \     / \     / \     / \
  4   3   1   1   4   5   1   3
 
  */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 /* Agora imprimiremos na tela esta expressão aritmética em duas formas:
  notação polonesa e notação parentizada. */

 printf("\n\n");
 printf("  Em notação polonesa: ");
 printf("\n             ");

 imprimeEmNotacaoPolonesa(*raiz);

 printf("\n\n");
 printf("  Em notação parentizada: ");
 printf("\n             ");

 parentiza(*raiz);

 printf("\n\n");
 printf("  Altura da árvore: %d ", altura(*raiz));

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

 /* esse free está meia boca, pois não apaga a árvore inteira */
 free(varre);
 free(raiz);

 system("pause");

 return 0;
}

/**
* Note que esses percursos foram implementados usando recursividade. Mas
* qualquer algoritmo recursivo pode ser implementado numa versão iterativa,
* basta usar uma pilha. E a complexidade continua a mesma. Isso porque, no
* fundo, os procedimentos recursivos usam uma pilha, que é a pilha de execução.
**/