AVA 2 ESTRUTURA DE DADOS

Prévia do material em texto

Estrutura de Dados
Nome do Aluno: Jefferson de Oliveira da Costa Teixeira
Matrícula: 20202301045
Curso: Análise e Desenvolvimento de Sistemas
Busca em árvores binárias
CABO FRIO – RJ
2022
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include <conio.h>
struct Valor
{
 char prefixo[11] ;
};
typedef struct codigo
{
 int digito;
 struct codigo *direita;
 struct codigo *esquerda;
} Cod;
void criaCODIGO(Cod **T)
{
 *T = NULL;
}
int CodisEmpty(Cod* T)
{
 return T == NULL;
}
void inserirCod(Cod **t, int digito)
{
 if(*t == NULL)
 {
 *t = (Cod*)malloc(sizeof(Cod));
 (*t)->esquerda = NULL;
 (*t)->direita = NULL;
 (*t)->digito = digito;
 }
 else
 {
 if(digito < (*t)->digito)
 {
 inserirCod(&(*t)->esquerda, digito);
 }
 if(digito > (*t)->digito)
 {
 inserirCod(&(*t)->direita, digito);
 }
 }
}
Cod *PraDireita(Cod **cod)
{
 if((*cod)->direita != NULL)
 {
 return PraDireita(&(*cod)->direita);
 }
 else
 {
 Cod *aux = *cod;
 if((*cod)->esquerda != NULL)
 {
 *cod = (*cod)->esquerda;
 }
 else
 {
 *cod = NULL;
 return aux;
 }
 }
}
Cod *PRAESQUERDA(Cod **cod)
{
 if((*cod)->esquerda != NULL)
 {
 return PRAESQUERDA(&(*cod)->esquerda);
 }
 else
 {
 Cod *aux = *cod;
 if((*cod)->direita != NULL)
 {
 *cod = (*cod)->direita;
 }
 else
 {
 *cod = NULL;
 return aux;
 }
 }
}
void remove1(Cod **T, int digito)
{
 if(*T == NULL)
 {
 printf("\nValor inexistente na árvore!\n");
 return;
 }
 else
 {
 if(digito > (*T)->digito)
 {
 remove1(&(*T)->direita, digito);
 }
 else
 {
 Cod *aux = *T;
 if (((*T)->esquerda == NULL)&&((*T)->direita == NULL))
 {
 free(aux);
 printf("\nRemovido! \n");
 (*T) = NULL;
 }
 else
 {
 if ((*T)->esquerda == NULL)
 {
 (*T) = (*T)->direita;
 aux->esquerda = NULL;
 free(aux);
 aux = NULL;
 printf("\nRemovido! \n");
 }
 else
 {
 aux = PraDireita(&(*T)->esquerda);
 aux->esquerda = (*T)->esquerda;
 aux->direita = (*T)->direita;
 (*T)->esquerda = (*T)->direita = NULL;
 free((*T));
 *T = aux;
 aux = NULL;
 printf("\nRemovido! \n");
 }
 }
 }
 }
}
PERCURSO PRÉ ORDEM
void moCodraPREORDEM(Cod **T)
{
 if((*T) != NULL)
 {
 printf("%i\n", (*T)->digito);
 moCodraPREORDEM(&(*T)->esquerda);
 moCodraPREORDEM(&(*T)->direita);
 }
}
PERCURSO QUANDO EM ORDEM
void moCodraEMORDEM(Cod **T)
{
 if((*T) != NULL)
 {
 moCodraEMORDEM(&(*T)->esquerda);
 printf("%i\n", (*T)->digito);
 moCodraEMORDEM(&(*T)->direita);
 }
}
PERCURSO PÓS ORDEM
void mostraPOSORDEM(Cod **T)
{
 if((*T) != NULL)
 {
 mostraPOSORDEM(&(*T)->esquerda);
 mostraPOSORDEM(&(*T)->direita);
 printf("%i\n", (*T)->digito);
 }
}
VERIFICANDO O MAIOR
int maior(int a, int b)
{
 if(a > b)
 return a;
 else
 return b;
}
IMPRIMIR
void imprimir(Cod **T)
{
 if((*T) != NULL)
 {
 if((*T) != NULL)
 {
 printf("\nRaíz %i\n",(*T)->digito);
 if((*T)->esquerda != NULL)
 printf("esquerda: %i\t",(*T)->esquerda->digito);
 else
 printf("esquerda: NULL\t");
 if((*T)->direita != NULL)
 printf("direita: %i\t",(*T)->direita->digito);
 else
 printf("direita: NULL\t");
 if((*T)->esquerda != NULL)
 imprimir(&(*T)->esquerda);
 if((*T)->direita != NULL)
 imprimir(&(*T)->direita);
 }
 else
 printf("Árvore Vazia! \n");
 }
}
Código Principal
int main()
{
 struct Valor x;
 int c;
 Cod *T;
 criaCODIGO(&T);
 setlocale(LC_ALL, "portuguese");
 int opcao;
 do
 {
 system("CLS");
 printf("******** DIGITE UM VALOR DE OPÇÃO ********\n\n");
 printf("1- Insere Valor: \n");
 printf("2- Remove Valor: \n");
 printf("3- Exibe PRÉ-ORDEM: \n");
 printf("4- Exibe EM ORDEM: \n");
 printf("5- Exibe PÓS-ORDEM: \n");
 printf("6- Imprime Árvore \n");
 //printf("\nopcaoção [0 para Sair]: ");
 scanf("%d", &opcao);
 switch(opcao)
 {
 Case 1:
 system("CLS");
 printf("\nprefixo: ");
 scanf("%s", x.prefixo);
 printf("\nDigite um Número (Referência na Árvore): ");
 scanf("%d",&c);
 inserirCod(&T,c);
 system("PAUSE");
 break;
 Case 2:
 system("CLS");
 printf("\nDigite um Número: ");
 scanf("%d",&c);
 remove1(&T,c);
 system("PAUSE");
 break;
 Case 3:
 system("CLS");
 moCodraPREORDEM(&T);
 system("PAUSE");
 break;
 Case 4:
 system("CLS");
 moCodraEMORDEM(&T);
 system("PAUSE");
 break;
 Case 5:
 system("CLS");
 mostraPOSORDEM(&T);
 system("PAUSE");
 break;
 
 Case 6:
 system("CLS");
 imprimir(&T);
 printf("\n");
 system("PAUSE");
 break;
 Case 0:
 break;
 default:
 printf("\n\nopcaoção Inválida. \n");
 system("PAUSE");
 break;
 }
 }
 while(opcao!=0);
 return 0;
}