C Erro em Árvore Binária de Pesquisa

Eduardo de Quadros · 24 de novembro de 2017

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <locale.h>

struct ArvoreBinaria{
int raiz;
struct ArvoreBinaria *esq;
struct ArvoreBinaria *dir;
};

void criar(struct ArvoreBinaria **arv){
*arv = NULL;
}

bool vazia(struct ArvoreBinaria *arv){
if(arv == NULL) return true;
else return false;
}

void inserir(struct ArvoreBinaria **nodo, int num){
if(vazia(*nodo)){
*nodo = (struct ArvoreBinaria*) malloc(sizeof(struct ArvoreBinaria));
(*nodo)->esq = NULL;
(*nodo)->dir = NULL;
(*nodo)->raiz = num;
}
else if(num < (*nodo)->raiz) inserir(&(*nodo)->esq, num);
else if(num > (*nodo)->raiz) inserir(&(*nodo)->dir, num);
}

void mostrarPrefixado(struct ArvoreBinaria *arv){
if(vazia(&arv)) printf("\nÁrvore vazia impossível de mostrá-la!\n");
else{
printf("%d\t", arv->raiz);
mostrarPrefixado(arv->esq);
mostrarPrefixado(arv->dir);
}
}

void mostrarInfixado(struct ArvoreBinaria *arv){
if(vazia(&arv)) printf("\nÁrvore vazia impossível de mostrá-la!\n");
else{
mostrarInfixado(arv->esq);
printf("%d\t", arv->raiz);
mostrarInfixado(arv->dir);
}
}

void mostrarSufixado(struct ArvoreBinaria *arv){
if(vazia(&arv)) printf("\nÁrvore vazia impossível de mostrá-la!\n");
else{
mostrarSufixado(arv->esq);
mostrarSufixado(arv->dir);
printf("%d\t", arv->raiz);
}
}

bool buscaElem(struct ArvoreBinaria **arv, int elem){
if(vazia(&(*arv))) return false;
else if((*arv)->esq == NULL && (*arv)->dir == NULL){
if((*arv)->raiz == elem) return true;
else return false;
}
else if((*arv)->raiz == elem) return true;
else{
if((*arv)->raiz < elem){
if((*arv)->esq == NULL){
if((*arv)->raiz == elem) return true;
else return false;
}
else{
*arv = (*arv)->esq;
if((*arv)->raiz == elem) return true;
}
}
else if((*arv)->raiz > elem){
if((*arv)->dir == NULL){
if((*arv)->raiz == elem) return true;
else return false;
}
else{
*arv = (*arv)->dir;
if((*arv)->raiz == elem) return true;
}
}
}
}

struct ArvoreBinaria* maiorDireita(struct ArvoreBinaria **no){
if((*no)->dir != NULL) return maiorDireita(&(*no)->dir);
else{
struct ArvoreBinaria *aux = *no;
if((*no)->esq != NULL) *no = (*no)->esq;
else *no = NULL;
return aux;
}
}

struct ArvoreBinaria* menorEsquerda(struct ArvoreBinaria **no){
if((*no)->esq != NULL) return menorEsquerda(&(*no)->esq);
else{
struct ArvoreBinaria *aux = *no;
if((*no)->dir != NULL) *no = (*no)->dir;
else *no = NULL;
return aux;
}
}

void remover(struct ArvoreBinaria **arv, int num){
if(vazia(&(*arv))) printf("Árvore vazia impossível de excluir qualquer nó!");
else if(!(buscaElem(&(*arv), num))) printf("Elemento não encontrado!");
else if(num < (*arv)->raiz) remover(&(*arv)->esq, num);
else if(num > (*arv)->raiz) remover(&(*arv)->dir, num);
else{
struct ArvoreBinaria *aux = *arv;
if(((*arv)->esq == NULL) && ((*arv)->dir == NULL)){
free(aux);
*arv = NULL;
}
else if((*arv)->esq != NULL){
*arv = (*arv)->esq;
aux->esq = NULL;
free(aux);
aux = NULL;
}
else if((*arv)->dir != NULL){
*arv = (*arv)->dir;
aux->dir = NULL;
free(aux);
aux = NULL;
}
else{
int op;
for(;;){
printf("\n\nEscolha uma das opções abaixo:\n");
printf("\nDigite 1 para remover o maior elemento à direita na sub-árvore à esquerda");
printf("\nDigite 2 para remover o menor elemento à esquerda na sub-árvore à direita");
printf("\n\n");
scanf("%d", &op);
switch(op){
case 1:
aux = maiorDireita(&(*arv)->esq);
break;
case 2:
aux = menorEsquerda(&(*arv)->dir);
break;
default:
printf("\nOpção Inválida!\n");
}
}
if(op == 1){
aux->esq = (*arv)->esq;
aux->dir = (*arv)->dir;
(*arv)->esq = (*arv)->dir;
(*arv)->dir = NULL;
free(*arv);
*arv = aux;
aux = NULL;
}
if(op == 2){
aux->esq = (*arv)->esq;
aux->dir = (*arv)->dir;
(*arv)->dir = (*arv)->esq;
(*arv)->esq = NULL;
free(*arv);
*arv = aux;
aux = NULL;
}
}
}
}

int contaNos(struct ArvoreBinaria *arv){
if(vazia(&arv)) return 0;
else return contaNos(arv->esq) + contaNos(arv->dir) + 1;
}

int maiorElem(int a, int b){
if(a > return a;
else return b;
}

int altura(struct ArvoreBinaria *arv){
if(contaNos(&arv) >= 0 && contaNos(&arv) <= 1) return contaNos(&arv);
else return maiorElem(altura(arv->esq), altura(arv->dir)) + 1;
}

int main(){
setlocale(LC_ALL, "portuguese");
struct ArvoreBinaria arv;
int op, valor;
criar(&arv);
for(;;){
printf("\n\nEscolha uma das opções abaixo:\n");
printf("\n0: Sair do Sistema");
printf("\n1: Inserir um nó");
printf("\n2: Remover um nó");
printf("\n3: Mostrar caminhamento prefixado");
printf("\n4: Mostrar caminhamento infixado");
printf("\n5: Mostrar caminhamento sufixado");
printf("\n6: Contar o número de nós");
printf("\n7: Descobrir a altura da árvore");
printf("\n8: Buscar um elemento");
printf("\n\n");
scanf("%d", &op);
switch(op){
case 0: printf("\n");
return 0;
case 1: printf("Qual valor você deseja inserir? ");
inserir(&arv, scanf("%d", &valor));
break;
case 2: printf("Qual valor você deseja remover? ");
remover(&arv, scanf("%d", &valor));
break;
case 3: mostrarPrefixado(&arv);
break;
case 4: mostrarInfixado(&arv);
break;
case 5: mostrarSufixado(&arv);
break;
case 6: printf("O número de nós na árvore é %d!", contaNos(&arv));
break;
case 7: printf("A altura da árvore é %d!", altura(&arv));
break;
case 8: printf("Informe o elemento a ser buscado: ");
buscaElem(&arv, scanf("%d", &valor));
break;
default: printf("\nOpção Inválida!\n\n");
}
}
}