Auxílio a prova de ARVORES BINÁRIAS E RECURSIVIDADE
Postando um exemplo de arvores aonde criamos 2 arvores com o intúito de auxiliar a prova.
Primeiro temos uma forma de revisarmos como fazer o script de criar uma arvore específica.
Segundo caso é o de criar uma arvore defeituosa e em seguida deixar-la perfeita (seria pegar os espaços em branco, pedaços aonde não possuem folhas e adicionar aonde falta).
- main.c
#include <stdio.h>
#include <stdlib.h>
#include “arvore.h”
int main()
{
int maior=NULL;
int menor=NULL;
arvore auxDaArvore;
arvore novaArvore;
system(“cls”);
novaArvore = inicializa();
auxDaArvore = novaArvore ;
// criando a raiz da árvore
novaArvore = constroi(1);
// criando 2 folhas esquerda e direita
criafilhoesquerdo(novaArvore,2);
criafilhodireito(novaArvore,3);
//vamos andar um nível(esquerda) para baixo da árvore, para andarmos na árvore usamos o Auxiliar da Arvore(auxDaArvore)
// local aonde vai receber a posicao = função do lado a se locomover ( posicao atual );
auxDaArvore = filhoesq(novaArvore);
// agora que nos locomovemos para esqueda e um nivel a mais podemos criar os outros elementos (4,5)
criafilhoesquerdo(auxDaArvore,4);
criafilhodireito(auxDaArvore,5);
//agora que acabamos de locomovermos pelo lado esquerdo da árvore temos que voltar a raiz para podermos
//ir para o lado direito da árvore
auxDaArvore = novaArvore;
//temos que locomovermos uma posicao para continuar a adição de elementos pois já existe o elemento da
//direita da arvore(folha direita da raiz)
auxDaArvore=filhodir(novaArvore);
//agora estamos prontos para criar os filhos esquerdo e direito (7,6)
criafilhoesquerdo(auxDaArvore,7);
criafilhodireito(auxDaArvore,6);
//agora vamos imprimir em todos os tipos, informaremos como argumento a árvore (novaArvore)
printf(“Imprimindo em PREORDEM \n”);
preordem(novaArvore);
printf(“\n\nImprimindo em INORDEM\n”);
inordem(novaArvore);
printf(“\n\nImprimindo em POSORDEM\n”);
posordem(novaArvore);
printf(“\n\n\n\n”);
verificaSeMaiorOuMenor(novaArvore,&maior,&menor);
printf(“Item de maior valor : %d \n”,maior);
printf(“Item de menor valor : %d \n”,menor);
printf(“\n\n\n\n\n\n\n\n\n”);
printf(“Criando esta arvore \n”
“ 3 \n”
“ / \\ \n”
“ 5 6 \n”
“ / \\ / \\ \n”
“ 11 2 9 21 \n”
“ \\ \\ \n”
“ 40 22 \n”);
arvore arv;
arvore aux;
arv = inicializa();
arv = constroi(3);
aux = arv;
criafilhoesquerdo(aux,5);
criafilhodireito(aux,6);
aux = filhoesq(arv);
criafilhoesquerdo(aux,11);
criafilhodireito(aux,2);
aux = filhodir(aux);
criafilhodireito(aux,40);
aux = filhodir(arv);
criafilhoesquerdo(aux,9);
criafilhodireito(aux,21);
aux = filhodir(aux);
criafilhodireito(aux,22);
printf(“Imprimindo em PREORDEM \n”);
preordem(arv);
printf(“\n\nImprimindo em INORDEM\n”);
inordem(arv);
printf(“\n\nImprimindo em POSORDEM\n”);
posordem(arv);
printf(“\n\n\n\n”);
verificaSeMaiorOuMenor(arv,&maior,&menor);
printf(“Item de maior valor : %d \n”,maior);
printf(“Item de menor valor : %d \n”,menor);
printf( “\nDepois tornando ela perfeita\n”
“ 3 \n”
“ / \\ \n”
“ 5 6 \n”
“ / \\ / \\ \n”
“ 11 2 9 21 \n”
“ / \\ / \\ / \\ / \\ \n”
“ 12 13 39 40 10 12 23 22 \n”);
aux = filhoesq(arv);
aux = filhoesq(aux);
criafilhoesquerdo(aux,12);
criafilhodireito(aux,13);
aux = filhoesq(arv);
aux = filhodir(aux);
criafilhoesquerdo(aux,39);
aux = filhodir(arv);
aux = filhoesq(aux);
criafilhoesquerdo(aux,10);
criafilhodireito(aux,12);
aux=filhodir(arv);
aux =filhodir(aux);
criafilhoesquerdo(aux,23);
printf(“Imprimindo em PREORDEM \n”);
preordem(arv);
printf(“\n\nImprimindo em INORDEM\n”);
inordem(arv);
printf(“\n\nImprimindo em POSORDEM\n”);
posordem(arv);
printf(“\n\n\n\n”);
verificaSeMaiorOuMenor(arv,&maior,&menor);
printf(“Item de maior valor : %d \n”,maior);
printf(“Item de menor valor : %d \n”,menor);
return 0;
}
- arvore.c
#include “arvore.h”
noarv* inicializa(void) {
return NULL;
}
//Verificar se a árvore está vazia
int vazia(arvore arv) {
return (arv == NULL);
}
//Criação de um nó da árvore
/* cria um novo no do tipo arvore e retorna um ponteiro para a arvore criada */
noarv* constroi(int info){
noarv *novo;
if ((novo = aloca()) == NULL)
return NULL;
novo->dado = info;
novo->esq = NULL;
novo->dir = NULL;
return(novo);
}
//Criar filho esquerdo
/* Verifica se a arvore nao esta nula ou se se tem filho esquerdo.
Caso nao tenha filho esquerdo, sera construido um novo no a partir da
arvore passada como parametro */
int criafilhoesquerdo(arvore arv, int info){
noarv *novo;
if (arv == NULL)
return ERRO;
else if (arv->esq != NULL)
return ERRO;
else {
novo = constroi(info);
arv->esq = novo;
}
return OK;
}
//Alocar um nodo para a árvore
noarv* aloca(void) {
return ( (noarv*) malloc(sizeof(noarv)));
}
//Criar filho direito
/* Verifica se a arvore nao esta nula ou se se tem filho direito. Caso nao
tenha filho direito, sera construido um novo no a partir da arvore passada
como parametro */
int criafilhodireito(arvore arv, int info){
noarv *novo;
if (arv == NULL)
return ERRO;
else if (arv->dir != NULL)
return ERRO;
else {
novo = constroi(info);
arv->dir = novo;
}
return OK;
}
//Ir para o filho esquerdo
/* Caminha para o filho esquerdo da arvore passada como parametro, retornando
o endereco deste no’ */
noarv* filhoesq(arvore arv) {
if (vazia(arv))
return NULL;
else
return ( arv->esq );
}
//Ir para o filho direito de uma árvore
/* Caminha para o filho direito da arvore passada como parametro, retornando
o endereco deste no’ */
noarv* filhodir(arvore arv) {
if (vazia(arv))
return NULL;
else
return ( arv->dir );
}
//Pesquisar um nodo
int busca( arvore arv, int info ) {
if (vazia(arv))
return ERRO; // Nao encontrou o nodo
if ( info == arv->dado)
return OK;
else if (busca(arv->esq, info))
return OK;
else
return busca(arv->dir, info);
}
//Imprimir a árvore em pré-ordem
/* Esta procedure deve percorrer recursivamente a arvore, visitando todos
os nos e imprimindo sua informação, segundo o percurso em pré-ordem */
void preordem(arvore arv) {
if (!vazia(arv)) {
printf(“%d\t”, arv->dado);
preordem(arv->esq);
preordem(arv->dir);
}
}
//Imprimir a árvore em in-ordem
/* Esta procedure deve percorrer recursivamente a arvore, visitando todos
os nos e imprimindo sua informação, segundo o percurso em in-ordem */
void inordem(arvore arv) {
if (!vazia(arv)) {
inordem(arv->esq);
printf(“%d\t”, arv->dado);
inordem(arv->dir);
}
}
//Imprimir a árvore em pós-ordem
/* Esta procedure deve percorrer recursivamente a arvore, visitando todos
os nos e imprimindo sua informação, segundo o percurso em pós-ordem */
void posordem(arvore arv) {
if (!vazia(arv)) {
posordem(arv->esq);
posordem(arv->dir);
printf(“%d\t”, arv->dado);
}
}
int buscarMaior(arvore arv , int *maior){
if (vazia(arv)) return 0;
if (maior ==NULL)
maior = arv->dado;
if (*maior < arv->dado)
*maior = arv->dado;
buscarMaior(arv->esq,maior);
buscarMaior(arv->dir,maior);
return 1;
}
int verificaSeMaiorOuMenor(arvore novaArvore,int *maior,int *menor){
if(vazia(novaArvore))
return 0;
if (*maior == NULL && *menor==NULL){
*maior = *menor = novaArvore ->dado;
}
if(novaArvore->dado > *maior){
*maior= novaArvore->dado;
}else{
if(novaArvore->dado < *menor){
*menor= novaArvore->dado;
}
}
verificaSeMaiorOuMenor(novaArvore->esq, maior,menor);
verificaSeMaiorOuMenor(novaArvore->dir,maior,menor);
return 1;
}
- Arvore.h
#include<malloc.h>
#include<stdio.h>
#define ERRO 0
#define OK 1
typedef struct stnoarvore {
int dado;
struct stnoarvore *esq;
struct stnoarvore *dir;
}noarv;
typedef noarv* arvore;
noarv* inicializa(void);
int vazia(arvore);
noarv* constroi(int);
int criafilhoesquerdo(arvore,int);
noarv* aloca(void);
int criafilhodireito(arvore,int);
noarv* filhoesq(arvore);
noarv* filhodir(arvore);
int busca(arvore,int);
void preordem(arvore);
void inordem(arvore);
void posordem(arvore);
int verificaSeMaiorOuMenor(arvore,int *,int *);
int buscarMaior(arvore,int*);
Deixe uma resposta