Uma estrutura de dados bastante comum sao as arvores. Temos de varios tipos (binarias, arvores B, arvores rubro-negra, etc), mas todas elas dispoem seus elementos de forma hierarquica: um elemento raiz tem ligacao com outros elementos - chamados de filhos, que por sua vez tem seus proprios filhos e assim por diante.Existem tambem varias formas de se percorrer os elementos de uma arvore. As mais intuitivas sao implementadas aqui:/*** MAC 2301 - Laboratorio de Programacao** Exercicio da aula 5* Assunto: Percursos (recursivos) em arvores binarias** Aplicacoes:* pre-ordem -> notacao polonesa* pos-ordem -> calcular altura de arveres* ordem simetrica -> parentizar uma expressao***/#include #include typedef struct node{ char info; struct node* filhoEsq; struct node* filhoDir;} noh;/*** Escrita de uma expressao aritmetica (dada numa arvore) em notacao polonesa,* percorrendo a arvore em pre-ordem.* Pseudo-codigo:* * pre-ordem(no)* {* visita(no)* pos-ordem(no.filhoEsq)* pos-ordem(no.filhoDir)* }**/void imprimeEmNotacaoPolonesa(noh raiz){ printf(" %c", raiz.info); if(raiz.filhoEsq != NULL) imprimeEmNotacaoPolonesa(*(raiz.filhoEsq)); if(raiz.filhoDir != NULL) imprimeEmNotacaoPolonesa(*(raiz.filhoDir));}/*** Calculo da altura de uma arvore percorrendo-a em pos-ordem.* Pseudo-codigo:* * pos-ordem(no)* {* pos-ordem(no.filhoEsq)* pos-ordem(no.filhoDir)* visita(no)* }**/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;}/* funcao auxiliar */int maximo(int um, int outro){ if(um > outro) return um; return outro;}/*** Parentizacao de uma expressao aritmetica dada* numa arvore percorrendo-a em ordem simetrica.* Pseudo-codigo:* * ordem-simetrica(no)* {* pos-ordem(no.filhoEsq)* visita(no)* pos-ordem(no.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 arvore: * ______+______ / \ __*__ __%__ / \ / \ + - + * / \ / \ / \ / \ 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 expressao aritmetica em duas formas: notacao polonesa e notacao parentizada. */ printf("\n\n"); printf(" Em notacao polonesa: "); printf("\n "); imprimeEmNotacaoPolonesa(*raiz); printf("\n\n"); printf(" Em notacao parentizada: "); printf("\n "); parentiza(*raiz); printf("\n\n"); printf(" Altura