AVA 2 - Busca em árvores binárias - UVA

Prévia do material em texto

UNIVERSIDADE VEIGA DE ALMEIDA 
GRADUAÇÃO EM ANÁLISE E DESENVOLVIMENTO DE SISTEMAS 
DISCIPLINA: ESTRUTURA DE DADOS 
PROF.: PAULO MÁRCIO SOUZA FREIRE 
 
 
 
 
 
 
 
 
EDUARDO FERREIRA TRINDADE 
 
 
 
TRABALHO DA DISCIPLINA (AVA2) 
BUSCA EM ÁRVORES BINÁRIAS 
 
 
 
 
 
 
 
 
 
NITERÓI 
2022 
2 
 
Trabalho da disciplina – AVA 2 
 
(Transcrição do enunciado) 
 
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 * * * 
 
1. Incluir nó. 
2. Remover nó. 
3. Buscar pré-ordem. 
4. Buscar em ordem. 
5. Buscar pós-ordem. 
Opção [0 para encerrar]1 
 
 
 
 
1 Enunciado da segunda avaliação disponível em: 
https://uva.instructure.com/courses/31426/assignments/89453?module_item_id=496574 acessado em: 
19/11/2022. 
https://uva.instructure.com/courses/31426/assignments/89453?module_item_id=496574
3 
 
BUSCA EM ÁRVORES BINÁRIAS 
 
 
#include <stdio.h> 
#include <stdlib.h> 
 
typedef struct no { 
 int valor; 
 struct no *esquerda, *direita; 
} NoArvore; 
 
NoArvore *inserir_no(NoArvore *raiz, int num) { 
 if (raiz == NULL) { 
 NoArvore *aux = malloc(sizeof(NoArvore)); 
 aux->valor = num; 
 aux->esquerda = NULL; 
 aux->direita = NULL; 
 printf("\n-------------------------\n"); 
 printf("No INSERIDO com sucesso!\n"); 
 printf("-------------------------\n"); 
 return aux; 
 } 
 else { 
 if (num < raiz->valor) { 
 raiz->esquerda = inserir_no(raiz->esquerda, num); 
 } 
 else { 
 raiz->direita = inserir_no(raiz->direita, num); 
 } 
 return raiz; 
 } 
} 
 
NoArvore* remover(NoArvore *raiz, int chave) { 
 if (raiz == NULL) { 
 printf("\n-------------------------\n"); 
 printf("Valor NAO ENCONTRADO na arvore !\n"); 
 printf("-------------------------\n"); 
 return NULL; 
 } 
 else { 
 if (raiz->valor == chave) { 
 // remover nó folha (sem filhos) 
4 
 
 if (raiz->esquerda == NULL && raiz->direita == NULL) 
{ 
 free(raiz); 
 printf("\n-------------------------\n"); 
 printf("No REMOVIDO com sucesso!\n"); 
 printf("-------------------------\n"); 
 return NULL; 
 } 
 else { 
 // remover nós com 2 filhos 
 if (raiz->esquerda && raiz->direita) { 
 NoArvore *aux = raiz->esquerda; 
 while (aux->direita) { 
 aux = aux->direita; 
 } 
 raiz->valor = aux->valor; 
 aux->valor = chave; 
 raiz->esquerda = remover(raiz->esquerda, 
chave); 
 return raiz; 
 } 
 else { 
 // remover nós com apenas 1 filho 
 NoArvore *aux; 
 if (raiz->esquerda) { 
 aux = raiz->esquerda; 
 } 
 else { 
 aux = raiz->direita; 
 } 
 free(raiz); 
 printf("\n-------------------------\n"); 
 printf("No REMOVIDO com sucesso!\n"); 
 printf("-------------------------\n"); 
 return aux; 
 } 
 } 
 } 
 else { 
 if (chave < raiz->valor) { 
 raiz->esquerda = remover(raiz->esquerda, chave); 
 } 
 else { 
 raiz->direita = remover(raiz->direita, chave); 
 } 
5 
 
 return raiz; 
 } 
 } 
} 
 
void busca_pre_ordem(NoArvore *raiz) { 
 if (raiz) { 
 printf("%d ", raiz->valor); 
 busca_pre_ordem(raiz->esquerda); 
 busca_pre_ordem(raiz->direita); 
 } 
} 
 
void busca_em_ordem(NoArvore *raiz) { 
 if (raiz) { 
 busca_em_ordem(raiz->esquerda); 
 printf("%d ", raiz->valor); 
 busca_em_ordem(raiz->direita); 
 } 
} 
 
void busca_pos_ordem(NoArvore *raiz) { 
 if (raiz) { 
 busca_pos_ordem(raiz->esquerda); 
 busca_pos_ordem(raiz->direita); 
 printf("%d ", raiz->valor); 
 } 
} 
 
int main() { 
 NoArvore *raiz = NULL; 
 int opcao, valor; 
 
 while (1) { 
 printf("\n\t[ 1 ] Inserir No\n" 
 "\t[ 2 ] Remover No\n" 
 "\t[ 3 ] Buscar Pre-ordem\n" 
 "\t[ 4 ] Buscar em ordem\n" 
 "\t[ 5 ] Buscar pos-ordem\n" 
 "\t[ 0 ] Sair\n\n"); 
 
 printf("Digite o numero da opcao: "); 
 scanf("%d", &opcao); 
 
 switch (opcao) { 
6 
 
 case 1: 
 printf("Digite um valor: "); 
 scanf("%d", &valor); 
 raiz = inserir_no(raiz, valor); 
 break; 
 
 case 2: 
 printf("Digite um valor a ser removido: "); 
 scanf("%d", &valor); 
 raiz = remover(raiz, valor); 
 break; 
 
 case 3: 
 if (raiz) { 
 printf("\n-------------------------\n" 
 "Busca Pre-ordem: "); 
 busca_pre_ordem(raiz); 
 printf("\n-------------------------\n"); 
 } 
 else { 
 printf("\n-------------------------\n"); 
 printf("Arvore Vazia!\n"); 
 printf("-------------------------\n"); 
 } 
 break; 
 
 case 4: 
 if (raiz) { 
 printf("\n-------------------------\n" 
 "Busca Pre-ordem: "); 
 busca_em_ordem(raiz); 
 printf("\n-------------------------\n"); 
 } 
 else { 
 printf("\n-------------------------\n"); 
 printf("Arvore Vazia!\n"); 
 printf("-------------------------\n"); 
 } 
 break; 
 
 case 5: 
 if (raiz) { 
 printf("\n-------------------------\n" 
 "Busca Pre-ordem: "); 
 busca_pos_ordem(raiz); 
7 
 
 printf("\n-------------------------\n"); 
 } 
 else { 
 printf("\n-------------------------\n"); 
 printf("Arvore Vazia!\n"); 
 printf("-------------------------\n"); 
 } 
 break; 
 
 case 0: 
 printf("\n-------------------------\n"); 
 printf("Programa Finalizado!\n"); 
 printf("-------------------------\n"); 
 exit(0); 
 
 default: 
 printf("\n-------------------------\n"); 
 printf("Opcao Invalida!\n"); 
 printf("-------------------------\n"); 
 break; 
 } 
 } 
 return 0; 
} 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
8 
 
Referências Bibliográficas: 
 
BOENTE, Alfredo Nazareno Pereira. Estrutura de dados [livro eletrônico]. Rio de 
Janeiro: UVA, 2019. 91 p. Disponível em: 
https://uva.instructure.com/courses/31426/modules/items/496561. Acesso em: 19 
nov. 2022. 
https://uva.instructure.com/courses/31426/modules/items/496561