Eis aqui mais alguns percursos basicos em arvores: busca em largura e versao iterativa do pre-ordem./*** MAC 2301 - Laboratorio de Programacao** Exercicio extra da aula 5-b** Assunto: Mais alguns percursos em arvores:* pre-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]");}/*** Versao nao recursiva da pre-ordem* Parecida com uma busca chamada de "busca em profundidade"* A diferenca e que na busca em profundidade, nao ha 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: espaco insuficiente\n"); return; } } /* tenta empilhar filho esquerdo */ if(varre->filhoEsq != NULL) { if(empilha(*(varre->filhoEsq), &p) != OK) { printf("\n\n **Erro: espaco insuficiente\n"); return; } } } }}/*** Percurso em nivel, cujo codigo e quase identico ao da* pre-ordem iterativoo, apenas substituindo a pilha por uma fila* Tambem conhecido como busca em largura. Nao tem versao 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: espaco insuficiente\n"); return; } } /* tenta enfileirar o filho direito */ if(varre->filhoDir != NULL) { if(enfileira(*(varre->filhoDir), &f) != OK) { printf("\n\n **Erro: espaco insuficiente\n"); return; } } } }}int main(){ /** * vamos criar a seguinte arvore: * ______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 arvore, * 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");