AVA2 - ESTRUTURA DE DADOS

Prévia do material em texto

UNIVERSIDADE VEIGA DE ALMEIDA – UVA 
 
 
 
 
 
 
 
AVA 2 – ESTRUTURA DE DADOS 
 
 
 
 
 
 
 
 
 
 
ALUNO: RAFAEL DA SILVA ORTOLÁ 
MATRÍCULA: 20211303306 
PROFESSOR: PAULO MÁRCIO SOUZA FREIRE 
 
 
 
 
Questão 1: 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] 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
RESPOSTA: 
/****************************************************************************
** 
 
 Online C Compiler. 
 Code, Compile, Run and Debug C program online. 
Write your code in this editor and press "Run" button to compile and execute it. 
 
*****************************************************************************
**/ 
 
#include<stdio.h> 
 
typedef struct NO* ArvoreBinaria; 
 
struct NO { 
 
 int info; 
 
 struct NO *esquerda; 
 
 struct NO *direita; 
 
}; 
 
 
 
ArvoreBinaria* cria_Arvorebinaria() { 
 
 ArvoreBinaria* raiz = (ArvoreBinaria*) malloc(sizeof(ArvoreBinaria)); 
 
 if(raiz != NULL){ 
 
 *raiz = NULL; 
 
 } 
 
 return raiz; 
 
} 
 
 
 
 
 
void libera_ArvoreBinaria(ArvoreBinaria* raiz){ 
 
 if(raiz == NULL) return ; 
 
 liberaNO(*raiz); 
 
 free(raiz); 
 
} 
 
void liberaNO(struct NO* no){ 
 
 if(no == NULL) return; 
 
 liberaNO(no->esquerda); 
 
 liberaNO(no->direita); 
 
 free(no); 
 
 no = NULL; 
 
} 
 
 
 
int incluirNo(ArvoreBinaria* raiz, int valor){ 
 
 if(raiz == NULL) return 0; 
 
 struct NO* novo; 
 
 novo = (struct NO*) malloc(sizeof(struct NO)); 
 
 if(novo == NULL) return 0; 
 
 novo->info = valor; 
 
 novo->direita = NULL; 
 
 novo->esquerda = NULL; 
 
 if(*raiz == NULL){ 
 
 *raiz = novo; 
 
 }else{ 
 
 struct NO* atual = *raiz; 
 
 struct NO* anterior = NULL; 
 
 while(atual != NULL){ 
 
 anterior = atual; 
 
 if(valor == atual->info){ 
 
 free(novo); 
 
 return 0; 
 
 } 
 
 if(valor > atual->info){ 
 
 atual = atual->info; 
 
 }else{ 
 
 atual = atual->esquerda; 
 
 } 
 
 } 
 
 if(valor > anterior->info){ 
 
 anterior->direita = novo; 
 
 }else{ 
 
 anterior->esquerda = novo; 
 
 } 
 
 } 
 
 return 1; 
 
} 
 
 
 
 
 
struct NO* removeAtual(struct NO* atual){ 
 
 struct NO *no1, *no2; 
 
 if(atual->esquerda == NULL){ 
 
 no2 = atual->direita; 
 
 free(atual); 
 
 return no2; 
 
 } 
 
 no1 = atual; 
 
 no2 = atual->esquerda; 
 
 while(no2->direita != NULL){ 
 
 no1 = no2; 
 
 no2 = no2->direita; 
 
 } 
 
 if(no1 != atual){ 
 
 no1->direita = no2->esquerda; 
 
 no2->esquerda = atual->esquerda; 
 
 } 
 
 no2->direita = atual->direita; 
 
 free(atual); 
 
 return no2; 
 
}; 
 
void removerNo(ArvoreBinaria* raiz, int valor){ 
 
 if(raiz == NULL) return 0; 
 
 struct NO* atual = *raiz; 
 
 struct NO* anterior = NULL; 
 
 while(atual != NULL){ 
 
 if(valor == atual->info){ 
 
 *raiz = removeAtual(atual); 
 
 }else{ 
 
 if(anterior->direita == atual){ 
 
 anterior->direita = removeAtual(atual); 
 
 }else{ 
 
 anterior->esquerda = removeAtual(atual); 
 
 } 
 
 } 
 
 return 1; 
 
 } 
 
 if(valor > atual->info){ 
 
 atual = atual->info; 
 
 }else{ 
 
 atual = atual->esquerda; 
 
 } 
 
} 
 
 
 
 
 
int preOrdem(ArvoreBinaria *raiz){ 
 
 if(raiz == NULL) return ; 
 
 if(*raiz != NULL){ 
 
 printf("%d\n", (*raiz)->info); 
 
 preOrdem(&((*raiz)->esquerda)); 
 
 preOrdem(&((*raiz)->direita)); 
 
 } 
 
} 
 
int emOrdem(ArvoreBinaria *raiz){ 
 
 if(raiz == NULL) return; 
 
 if(*raiz != NULL){ 
 
 emOrdem(&((*raiz)->esquerda)); 
 
 printf("%d\n", (*raiz)->info); 
 
 emOrdem(&((*raiz)->direita)); 
 
 } 
 
} 
 
int posOrdem(ArvoreBinaria *raiz){ 
 
 if(raiz == NULL) return; 
 
 if(*raiz != NULL){ 
 
 posOrdem(&((*raiz)->esquerda)); 
 
 posOrdem(&((*raiz)->direita)); 
 
 printf("%d\n", (*raiz)->info); 
 
 } 
 
} 
 
void main(){ 
 
 int valor; 
 
 int opcao; 
 
 ArvoreBinaria *raiz = cria_Arvorebinaria(); 
 
 while(1){ 
 
 printf("** MENU DE OPÇÕES **\n"); 
 
 printf("1 - Incluir nó.\n"); 
 
 printf("2 - Remover nó.\n"); 
 
 printf("3 - Buscar em pré-ordem.\n"); 
 
 printf("4 - Buscar em ordem.\n"); 
 
 printf("5 - Buscar pós-ordem.\n"); 
 
 printf("0 - Cancelar.\n"); 
 
 printf("Digite a opção: "); 
 
 scanf("%d", &opcao); 
 
 switch(opcao){ 
 
 case 1: 
 
 printf("Função incluir nó\n"); 
 
 printf("Digite um valor numérico: "); 
 
 scanf("%d", &valor); 
 
 incluirNo(raiz,valor); 
 
 break; 
 
 case 2: 
 
 printf("Função remover nó\n"); 
 
 printf("Digite um valor numérico: "); 
 
 scanf("%d", &valor); 
 
 removerNo(raiz,valor); 
 
 break; 
 
 case 3: 
 
 printf("Função Buscar em pré-ordem \n"); 
 
 preOrdem(raiz); 
 
 break; 
 
 case 4: 
 
 printf("Função Buscar em ordem \n"); 
 
 emOrdem(raiz); 
 
 break; 
 
 case 5: 
 
 printf("Função Buscar pós-ordem \n"); 
 
 posOrdem(raiz); 
 
 break; 
 
 default: 
 
 printf("Saindo...\n"); 
 
 libera_ArvoreBinaria(raiz); 
 
 break; 
 
 } 
 
 } 
 
}