AV2 ESTRUTURA DE DADOS

Prévia do material em texto

AV2 ESTRUTURA DE DADOS
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 * * *
1. Incluir nó.
2. Remover nó.
3. Buscar pré-ordem.
4. Buscar em ordem.
5. Buscar pós-ordem.
Opção [0 para encerrar]
R = ENVIEI O CODIGO TAMBÉM EM UM BLOCO DE NOTAS, ESTÁ EM UM FORMATO MELHOR.
CÓDIGO
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <locale.h>
struct alimentos
{
	char nome[50];
	char marca[50];
	int validade;
	float preco;
};
struct No
{
	int num;
	struct alimentos x;
	struct No *esquerda;
	struct No *direita;
};
typedef struct No No;
void criarArvore(No **pRaiz)
{
	*pRaiz = NULL;
}
void inserir(No **pRaiz, int num, struct alimentos x)
{
	if(*pRaiz == NULL)
	{
		*pRaiz = (No *) malloc(sizeof(No));
		(*pRaiz)->esquerda = NULL;
		(*pRaiz)->direita = NULL;
		(*pRaiz)->num = num;
		(*pRaiz)->x = x;
	}
	else
	{	
		if(num < (*pRaiz)->num)
			inserir(&(*pRaiz)->esquerda, num, x);
		if(num > (*pRaiz)->num)
			inserir(&(*pRaiz)->direita, num, x);
	}
}	
	
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;
	}
}
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;
	}
}
void remover(No **pRaiz, int num)
{
	if(*pRaiz == NULL)
	{
		printf("\nNúmero não existe na árvore!\n");
		return;
	}
	if(num < (*pRaiz)->num)
	remover(&(*pRaiz)->esquerda, num);
	else
		if(num > (*pRaiz)->num)
		remover(&(*pRaiz)->direita, num);
		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;
						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");
					}
				}
			}
		}
}
void exibirPreOrdem(No **pRaiz)
{
	if((*pRaiz) != NULL)
	{
		printf("%i\n", (*pRaiz)->num);
		exibirPreOrdem(&(*pRaiz)->esquerda);
		exibirPreOrdem(&(*pRaiz)->direita);
	}
}
void exibirEmOrdem(No **pRaiz)
{
	if((*pRaiz) != NULL)
	{
		exibirEmOrdem(&(*pRaiz)->esquerda);
		printf("%i\n", (*pRaiz)->num);
		exibirEmOrdem(&(*pRaiz)->direita);
	}
}
void exibirPosOrdem(No **pRaiz)
{
	if((*pRaiz) != NULL)
	{
		exibirPosOrdem(&(*pRaiz)->esquerda);
		exibirPosOrdem(&(*pRaiz)->direita);
		printf("%i\n", (*pRaiz)->num);
	}
}
int maior(int a, int b){
	if(a > b)
	return a;
else
	return b;
}
int imprimir(No **pRaiz)
{
	if((*pRaiz) != NULL)
	{
		if((*pRaiz) != NULL)
		printf("\nPai %i\n",(*pRaiz)->num);
 		if((*pRaiz)->esquerda != NULL)
 	printf("Esq: %i\t",(*pRaiz)->esquerda->num);
 	else
 		printf("Esq: NULL\t");
 		if((*pRaiz)->direita != NULL)
 			printf("Dir: %i\t",(*pRaiz)->direita->num);
 	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");
}
int main ()
{
	struct alimentos ca;
	int c;
	No *pRaiz;
	criarArvore(&pRaiz);
	setlocale(LC_ALL, "portuguese");
	int op;
do{
	system("CLS");
		printf("Escolha uma opção * * *\n\n");
	printf("1. Inserir Alimento: \n");
	printf("2. Remover Alimento: \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("0. para Sair: ");
	scanf("%d", &op);
	switch(op)
	{
	case 1:
		system("CLS");
	printf("\nAlimentos: ");
	scanf("%s", &ca.nome);
	printf("\nMarca do produto: ");
	scanf("%s",&ca.marca);
	printf("\nAno de Validade do produto: ");
	scanf("%d", &ca.validade);
	printf("\nPreço do Alimento: ");
	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 (Referência na Árvore): ");
	scanf("%d",&c);
	remover(&pRaiz,c);
	system("PAUSE");
 	break;
	case 3:
		system("CLS");
	exibirPreOrdem(&pRaiz);
	system("PAUSE");
 	break;
	case 4:
		system("CLS");
	exibirEmOrdem(&pRaiz);
	system("PAUSE");
	break;
	case 5:
		system("CLS");
	exibirPosOrdem(&pRaiz);
	system("PAUSE");
 	break;
	case 6:
		system("CLS");
	imprimir(&pRaiz);
	printf("\n");
	system("PAUSE");
	break;
	case 0:
 	break;
 	
	default:
	printf("\nOpção Inválida. \n");
	system("PAUSE");
	break;
	}
}while(op!=0);
	return 0;
}