AVA2 - Busca em árvores binárias ESTRUTURA DE DADOS UVA UNIVERSIDADE VEIGA DE ALMEIDA

Prévia do material em texto

UVA – UNIVERSIDADE VEIGA DE ALMEIDA 
 
 
 
 
 
ESTRUTURA DE DADOS 
AVA2 – Busca em árvores binárias 
 
 
 
 
 
 
 
 
PROFESSOR: Paulo Márcio Souza Freire 
NOME: Rodrigo Maia Diniz 
MATRÍCULA: 20191301456 
CURSO: Sistema de Informação 
 
 
 
 
 
 
 
 
Rio de Janeiro 
2022.4 
2 
 
Índice 
 
Índice........................................................................................................ 2 
Busca em árvores binárias....................................................................... 3 
Desenvolvimento.......................................................................................3 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3 
 
BUSCA EM ÁRVORES BINÁRIAS 
 
As árvores binárias de busca são estruturas de dados de árvore binária 
baseada em nós em que todos os nós da subárvore esquerda possuem um valor 
numérico inferior ao nó raiz e todos os nós da subárvore direita possuem um 
valor superior ao nó raiz (FORBELLONE; EBERSPACHER, 2005). 
A Empresa Renalf S/A solicita a você, membro da equipe de 
programadores de computador em linguagem C, que desenvolva um programa 
que seja capaz de manipular uma árvore binária (inclusão e remoção de nós), 
admitindo a escolha dos três processos de busca em profundidade. 
Procedimentos para elaboração do TD 
Nesse contexto, escreva um programa em linguagem C que apresente um 
menu de opções que possibilite executar as seguintes opções: 
* * * MENU DE OPÇÕES * * * 
Incluir nó. 
Remover nó. 
Buscar pré-ordem. 
Buscar em ordem. 
Buscar pós-ordem. 
Opção [0 para encerrar]. 
 
DESENVOLVIMENTO 
 
#include <stdlib.h> 
#include <stdio.h> 
#include <conio.h> 
#include <locale.h> 
/* Comentario: Declaração da Estrutura do Registro */ 
struct produto 
{ 
char nome[30]; 
float preco; 
}; 
/* Comentario: Declaração da Estrutura da Árvore */ 
4 
 
struct No 
{ 
 
int numero; 
struct produto x; 
struct No *esquerda; 
struct No *direita; 
}; 
typedef struct No No; 
/* Comentario: Criar Árvore */ 
void criarArvore(No **pRaiz) 
{ 
*pRaiz = NULL; 
} 
/* Comentario: Inserir Elemento */ 
void inserir(No **pRaiz, int numero, struct produto x) 
{ 
if(*pRaiz == NULL) 
{ 
*pRaiz = (No *) malloc(sizeof(No)); 
(*pRaiz)->esquerda = NULL; 
(*pRaiz)->direita = NULL; 
(*pRaiz)->numero = numero; 
(*pRaiz)->x = x; 
} 
else 
{ 
 
if(numero < (*pRaiz)->numero) 
inserir(&(*pRaiz)->esquerda, numero, x); 
if(numero > (*pRaiz)->numero) 
inserir(&(*pRaiz)->direita, numero, x); 
} 
} 
5 
 
/* Comentario: Teste Nó Maior Direita */ 
No *MaiorDireita(No **no) 
{ 
if((*no)->direita != NULL) 
return MaiorDireita(&(*no)->direita); 
else 
{ 
No *aux = *no; 
if((*no)->esquerda != NULL) 
*no = (*no)->esquerda; 
else 
*no = NULL; 
return aux; 
} 
} 
/* Comentario: Teste Nó Maior Esquerda */ 
No *MenorEsquerda(No **no) 
{ 
 
if((*no)->esquerda != NULL) 
return MenorEsquerda(&(*no)->esquerda); 
else 
{ 
No *aux = *no; 
if((*no)->direita != NULL) 
*no = (*no)->direita; 
else 
*no = NULL; 
return aux; 
} 
} 
/* Comentario: Remover Elemento */ 
void remover(No **pRaiz, int numero) 
{ 
6 
 
if(*pRaiz == NULL) 
{ 
printf("\nNumero nao existe na arvore\n"); 
return; 
} 
if(numero < (*pRaiz)->numero) 
remover(&(*pRaiz)->esquerda, numero); 
else 
if(numero > (*pRaiz)->numero) 
 
remover(&(*pRaiz)->direita, numero); 
else 
{ 
No *pAux = *pRaiz; 
if (((*pRaiz)->esquerda == NULL) && ((*pRaiz)->direita == NULL)) 
{ 
free(pAux); 
printf("\nRemovido com Sucesso! \n"); 
(*pRaiz) = NULL; 
} 
else 
{ 
if ((*pRaiz)->esquerda == NULL) 
{ 
(*pRaiz) = (*pRaiz)->direita; 
pAux->direita = NULL; 
free(pAux); pAux = NULL; 
printf("\nRemovido com Sucesso! \n"); 
} 
else 
{ 
if ((*pRaiz)->direita == NULL) 
{ 
(*pRaiz) = (*pRaiz)->esquerda; 
7 
 
 
pAux->esquerda = NULL; 
free(pAux); pAux = NULL; 
printf("\nRemovido com Sucesso! \n"); 
} 
else 
{ 
pAux = MaiorDireita(&(*pRaiz)->esquerda); 
pAux->esquerda = (*pRaiz)->esquerda; 
pAux->direita = (*pRaiz)->direita; 
(*pRaiz)->esquerda = (*pRaiz)->direita = NULL; 
free((*pRaiz)); *pRaiz = pAux; pAux = NULL; 
printf("\nRemovido com Sucesso! \n"); 
} 
} 
} 
} 
} 
/* Comentario: Percurso Pre Ordem */ 
void mostrarPreOrdem(No **pRaiz) 
{ 
if((*pRaiz) != NULL) 
{ 
printf("%i\n", (*pRaiz)->numero); 
mostrarPreOrdem(&(*pRaiz)->esquerda); 
 
mostrarPreOrdem(&(*pRaiz)->direita); 
} 
} 
/* Comentario: Percurso Em Ordem */ 
void mostrarEmOrdem(No **pRaiz) 
{ 
if((*pRaiz) != NULL) 
{ 
8 
 
mostrarEmOrdem(&(*pRaiz)->esquerda); 
printf("%i\n", (*pRaiz)->numero); 
mostrarEmOrdem(&(*pRaiz)->direita); 
} 
} 
/* Comentario: Percurso Pós-Ordem */ 
void mostrarPosOrdem(No **pRaiz) 
{ 
if((*pRaiz) != NULL) 
{ 
mostrarPosOrdem(&(*pRaiz)->esquerda); 
mostrarPosOrdem(&(*pRaiz)->direita); 
printf("%i\n", (*pRaiz)->numero); 
} 
} 
/* Comentario: Verifica Quem é o Maior */ 
 
int maior(int a, int b){ 
if(a > b) 
return a; 
else 
return b; 
} 
/* Comentario: Imprimir Árvore */ 
int imprimir(No **pRaiz) 
{ 
if((*pRaiz) != NULL) 
{ 
if((*pRaiz) != NULL) 
printf("\nPai %i\n",(*pRaiz)->numero); 
if((*pRaiz)->esquerda != NULL) 
printf("Esq: %i\t",(*pRaiz)->esquerda->numero); 
else 
printf("Esq: NULL\t"); 
9 
 
if((*pRaiz)->direita != NULL) 
printf("Dir: %i\t",(*pRaiz)->direita->numero); 
else 
printf("Dir: NULL\t"); 
if((*pRaiz)->esquerda != NULL) 
imprimir(&(*pRaiz)->esquerda); 
if((*pRaiz)->direita != NULL) 
 
imprimir(&(*pRaiz)->direita); 
} 
else 
printf("A árvore está vazia! \n"); 
} 
/* Programa Principal */ 
int main () 
{ 
struct produto ca; 
int c; 
No *pRaiz; 
criarArvore(&pRaiz); 
setlocale(LC_ALL, "portuguese"); 
int op; 
do{ 
system("CLS"); 
printf("* * * FAÇA SUA ESCOLHA * * *\n\n"); 
printf("1. Inserir produto: \n"); 
printf("2. Remover produto: \n"); 
printf("3. Mostrar PRÉ-ORDEM: \n"); 
printf("4. Mostrar EM ORDEM: \n"); 
printf("5. Mostrar PÓS-ORDEM: \n"); 
printf("6. Imprimir Árvore \n"); 
printf("\nOpção [0 para Sair]: "); 
 
scanf("%d", &op); 
10 
 
switch(op) 
{ 
case 1: 
system("CLS"); 
printf("\nproduto: "); 
scanf("%s", &ca.nome); 
printf("\nPreço do produto: "); 
scanf("%f", &ca.preco); 
printf("\nDigite um Número (Referência na Árvore): "); 
scanf("%d",&c); 
inserir(&pRaiz,c,ca); 
system("PAUSE"); 
break; 
case 2: 
system("CLS"); 
printf("\nDigite um Número: "); 
scanf("%d",&c); 
remover(&pRaiz,c); 
system("PAUSE"); 
break; 
case 3: 
system("CLS"); 
mostrarPreOrdem(&pRaiz); 
 
system("PAUSE"); 
break; 
case 4: 
system("CLS"); 
mostrarEmOrdem(&pRaiz); 
system("PAUSE"); 
break; 
case 5: 
system("CLS"); 
mostrarPosOrdem(&pRaiz); 
11 
 
system("PAUSE"); 
break; 
case 6: 
system("CLS"); 
imprimir(&pRaiz); 
printf("\n"); 
system("PAUSE"); 
break; 
case 0: 
break; 
default: 
printf("\n\nOpção Inválida. \n"); 
system("PAUSE"); 
break; 
 
} 
}while(op!=0); 
return 0; 
}