Árvore Binária de Busca - ABB
Publicado por Reginaldo de Matias 18/01/2007
[ Hits: 13.989 ]
Homepage: http://mundodacomputacaointegral.blogspot.com/
Download ArvoreBinariaBuscaABB.zip
O presente script apresenta a implementação da Árvore Binária de Busca (ABB) em forma de projeto (Tipo de Dado Abstrato).
Segue abaixo o código fonte de cada arquivo separado. ABB_privado.h /*Árvore Binária de Busca - ABB*/ /*ABB_privado*/ #ifndef ABB_PRIVADO_H #define ABB_PRIVADO_H #include "ABB_interface.h" typedef struct noABB { struct noABB *dir; struct noABB *esq; void *dados; }NoABB,*pNoABB; typedef struct ABB { int tamInfo; pNoABB raiz; }ABB; int auxReinicia(pNoABB p); #endif ABB_interface.h /*ABB_interface.h*/ #ifndef ABB_INTERFACE_H #define ABB_INTERFACE_H #include <stdio.h> #include <stdlib.h> #include <string.h> #define SUCESSO 1 #define FRACASSO 0 #define MAIOR 1 #define MENOR -1 #define IGUAL 0 #define SIM 1 #define NAO 0 typedef struct ABB *pABB,**ppABB; int criaABB(ppABB pp,int tamInfo); int insereABB(pABB p,void *novo,int(*comparaElemElem)(void *k,void *e)); int removeABB(pABB p,void *chave,int (*comparaChaveElem)(void *e1,void *e2)); int buscaABB(pABB p,void *chave,void *destino,int (*comparaChaveElem)(void *e1,void *e2)); /*int percurso_em_ordem(pABB p,void(*visita)(void *info)); int percurso_pre_ordem(pABB p,void(*visita)(void *info)); int percurso_pos_ordem(pABB p,void(*visita)(void *info));*/ int testaVaziaABB(pABB p); void reiniciaABB(pABB p); void destroiABB(ppABB pp); #endif ABB.c #include "ABB_privado.h" /******************************************************************************************/ int criaABB(ppABB pp,int tamInfo) { (*pp) = (pABB )malloc(sizeof(ABB)); if((*pp) == NULL) return FRACASSO; (*pp)->tamInfo = tamInfo; (*pp)->raiz = NULL; return SUCESSO; } /*******************************************************************************************/ int buscaABB(pABB p,void *chave,void *destino,int(*comparaChaveElem)(void *k,void *e)) { pNoABB aux; if(p == NULL) /*se a árvore não foi criada*/ return FRACASSO; if(testaVaziaABB(p) == SIM) /*se a árvore estiver vazia*/ return FRACASSO; aux = p->raiz; while(aux != NULL && comparaChaveElem(chave,aux->dados) != IGUAL) { if(comparaChaveElem(chave,aux->dados) == MENOR) { aux = aux->esq; } else aux = aux->dir; } if(aux == NULL) /*não encontrado*/ return FRACASSO; memcpy(destino,aux->dados,p->tamInfo); return SUCESSO; } /********************************************************************************************/ int insereABB(pABB p,void *novo,int(*comparaElemElem)(void *e1,void *e2)) { pNoABB aux = NULL, ant = NULL; if(p == NULL) /*se a árvore não foi criada*/ return FRACASSO; aux = p->raiz; while(aux != NULL) { ant = aux; if(comparaElemElem(novo,aux->dados) == MENOR) aux = aux->esq; else if(comparaElemElem(novo,aux->dados) == MAIOR) aux = aux->dir; else if(comparaElemElem(novo,aux->dados) == IGUAL) { printf("\n!!!ERRO!!!Chave igual\n"); return FRACASSO; } } aux = (pNoABB )malloc(sizeof(NoABB)); if(aux == NULL) return FRACASSO; aux->dados = malloc(p->tamInfo); if(aux->dados == NULL) { free(aux); aux = NULL; return FRACASSO; } memcpy(aux->dados,novo,p->tamInfo); aux->dir = NULL; aux->esq = NULL; if(ant != NULL) /*se for inserir a folha da árvore*/ { if(comparaElemElem(novo,ant->dados) == MENOR) ant->esq = aux; else if(comparaElemElem(novo,ant->dados) == MAIOR) ant->dir = aux; return SUCESSO; } if(ant == NULL) /*árvore vazia*/ { p->raiz = aux; return SUCESSO; } return SUCESSO; } /******************************************************************************************/ int removeABB(pABB p,void *chave,int(*comparaChaveElem)(void *k,void *e)) { /*Remoção: casos: 1) Remoção de um nó sem filhos 2) Remoção de um nó com um único filho(esquerdo ou direito) 3) Remoção de um nó com dois filhos substituído pelo nó Sucessor(ou Antecessor) vem vem na sequência da ordenação. */ pNoABB aux,ant,suc,pai_suc,x; ant = NULL; if(p == NULL) /*se a árvore não foi criada*/ return FRACASSO; if(testaVaziaABB(p) == SIM) /*se a árvore estiver vazia*/ return FRACASSO; aux = p->raiz; while(aux != NULL && comparaChaveElem(chave,aux->dados) != IGUAL) { ant = aux; if(comparaChaveElem(chave,aux->dados) == MENOR) aux = aux->esq; else aux = aux->dir; } if(aux == NULL) /*não encontrou*/ return FRACASSO; if(aux->esq == NULL && aux ->dir == NULL) /*caso 1*/ { if(ant == NULL) p->raiz = NULL; else { if(comparaChaveElem(chave,ant->dados) == MENOR) { ant->esq = NULL; } else ant->dir = NULL; } } else if(aux->esq == NULL || aux->dir == NULL) /*caso 2*/ { if(ant == NULL) /*remoção da raiz*/ { if(aux->esq == NULL) p->raiz = aux->dir; else p->raiz = aux->esq; } else { if(aux->esq == NULL) x = aux->dir; else x = aux->esq; if(ant->esq == aux) ant->esq = x; else ant->dir = x; } } else /*caso 3*/ { suc = aux->dir; pai_suc = aux; while(suc->esq != NULL) { pai_suc = suc; suc = suc->esq; } pai_suc->esq = suc->dir; suc->esq = aux->esq; suc->dir = aux->dir; if(ant == NULL) /*remoção da raiz com dois filhos*/ { p->raiz = suc; } else { if(ant->esq == aux) ant->esq = suc; else ant->dir = suc; } } free(aux->dados); free(aux); return SUCESSO; } /******************************************************************************************/ int testaVaziaABB(pABB p) { if(p->raiz == NULL) return SIM; else return NAO; } /******************************************************************************************/ void reiniciaABB(pABB p) { auxReinicia(p->raiz); p->raiz = NULL; } /******************************************************************************************/ int auxReinicia(pNoABB p) { if(p != NULL) { auxReinicia(p->esq); auxReinicia(p->dir); free(p->dados); free(p); } else return FRACASSO; } /******************************************************************************************/ void destroiABB(ppABB pp) { reiniciaABB(*pp); free(*pp); *pp = NULL; } ABB_Aplica.h /*ABB_Aplicação.h*/ #ifndef ABB_APLICA_H #define ABB_APLICA_H #include "ABB_interface.h" typedef struct info{ long chave; char nome[40]; char fone[15]; float salario; }Info; int comparaElemElem(void *e1,void *e2); int comparaChaveElem(void *k,void *e); #endif ABB_Aplica.c /******************************************************************************* Universidade do Estado de Santa Catarina - UDESC Centro de Ciências Tecnológicas - CCT Bacharelado em Ciência da Computação - BCC Acadêmico: Reginaldo de Matias E-mail: reginaldo.matias@gmail.com ********************************************************************************/ #include "ABB_Aplica.h" int comparaElemElem(void *e1,void *e2) { long *c = (long *)e1; Info *i = (Info *)e2; if(*c > i->chave) return MAIOR; else if(*c < i->chave) return MENOR; else return IGUAL; } int comparaChaveElem(void *e1,void *e2) { Info *x1 = (Info *)e1; Info *x2 = (Info *)e2; if(x1->chave > x2->chave) return MAIOR; else if(x1->chave < x2->chave) return MENOR; else return IGUAL; } int main() { pABB p = NULL; Info reg; int op,id; if(criaABB(&p,sizeof(Info)) == SUCESSO) { do{ system("title Árvore Binária de Busca :. ABB"); system("color 9A"); printf("\n\tArvore Binaria de Busca :. ABB\n"); printf("[1]Inserir\n"); printf("[2]Remover\n"); printf("[3]Buscar\n"); printf("[4]Resetar\n"); printf("[5]Creditos\n"); printf("[0]Sair\n"); scanf("%i",&op); switch(op) { case 1: fflush(stdin); printf("Numero da chave: "); scanf("%li",&(reg.chave)); fflush(stdin); printf("Nome: "); gets(reg.nome); fflush(stdin); printf("Fone: "); scanf("%s",&(reg.fone)); fflush(stdin); printf("Salario: "); scanf("%f",&(reg.salario)); fflush(stdin); if(insereABB(p,®,comparaElemElem) == SUCESSO) printf("\nDado Inserido com Sucesso!\n"); else printf("\nChave jah existe\n"); break; case 2: if(testaVaziaABB(p) == SIM) printf("\n!!!Arvore Vazia!!!\n"); else { printf("Entre com a chave que deseja remover: "); scanf("%i",&id); if(removeABB(p,&id,comparaChaveElem) == SUCESSO) printf("\nDado removido com Sucesso!\n"); else printf("\nChave Inexistente!\n"); } break; case 3: if(testaVaziaABB(p) == SIM) printf("\n!!!Arvore Vazia!!!\n"); else { printf("Entre com a chave que deseja consultar: "); scanf("%i",&id); if(buscaABB(p,&id,®,comparaChaveElem) == SUCESSO) { printf("Chave:. %i\n",reg.chave); printf("Nome:. %s\n",reg.nome); printf("Fone:. %s\n",reg.fone); printf("Salario:. %f\n",reg.salario); } else printf("\nChave Inexistente!\n"); } break; case 4: if(testaVaziaABB(p) == SIM) printf("\nA Arvore jah se encontra Vazia\n"); else { reiniciaABB(p); printf("\nArvore Reiniciada com Sucesso!\n"); } break; case 5: printf("\n|******************************************************|"); printf("\n|Academico: Reginaldo de Matias |"); printf("\n|Ciencia da Computacao - UDESC |"); printf("\n|******************************************************|"); break; } }while(op != 0); destroiABB(&p); } else { printf("\nERRO! NAO FOI POSSIVEL CRIAR A ARVORE!\n"); } system("Pause"); } OK! Qualquer dúvida entre em contato.
Google Code Jam 2010 - Africa Classification Round A
Nenhum comentário foi encontrado.
Atenção a quem posta conteúdo de dicas, scripts e tal (1)
Manutenção de sistemas Linux Debian e derivados com apt-get, apt, aptitude e dpkg
Melhorando o tempo de boot do Fedora e outras distribuições
Como instalar as extensões Dash To Dock e Hide Top Bar no Gnome 45/46
Como Atualizar Fedora 39 para 40
Instalar Google Chrome no Debian e derivados
Consertando o erro do Sushi e Wayland no Opensuse Leap 15
Instalar a última versão do PostgreSQL no Lunix mantendo atualizado
Flathub na sua distribuição Linux e comandos básicos de gerenciamento
pacotes 32 bit no void 64 bit (1)
erro ao clonar repo github (7)
ASRock H310CM-HG4 vs Linux (1)
Como adicionar módulo de saúde da bateria dos notebooks Acer ao kernel... (26)
[Shell Script] Script para desinstalar pacotes desnecessários no OpenSuse
[Shell Script] Script para criar certificados de forma automatizada no OpenVpn
[Shell Script] Conversor de vídeo com opção de legenda
[C/C++] BRT - Bulk Renaming Tool
[Shell Script] Criação de Usuarios , Grupo e instalação do servidor de arquivos samba