Arvore de busca Binária AVL

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

/*
IFMT - ENGENHARIA DA COMPUTAÇÃO (ESTRUTURA DE DADOS 2) 
MURILLO H. SILVA SOARES
 =>Aplicativo de arvore de pesquisa binária deve ser utilizado no contexto de AVL<=
*/
/*
Após add a raiz, haverá a comparação entre o valor inserido com os seus filhos, sendo: 
	valor > filhos = direita;
	valor < filhos = esquerda;
0, 1 ou -1 nos diz que a arvore está balaceada, comparando dois nós:
	1=> Se o primeiro for maior
 -1=> Se o segundo for maior
 0=> Se ambos forem iguais
 
 Rotações simples (RR) e (LL): 
 	Direita;
 	Esquerda;
*/
#include<stdio.h>
#include<stdlib.h>
#include<locale>
int const def = 6;
typedef struct no{
	struct no *esq;
	struct no *dir;
	int valor;
}no;
int altura(no* raiz){//Verifica a altura para cada nó e incrementa
	int hesq, hdir;
	if(raiz == NULL)
		return NULL;
	hesq = altura(raiz->esq);
	hdir = altura(raiz->dir);
	return hesq > hdir ? hesq+1 : hdir+1;// testando if alternativo
}
void inserir(no** raiz, int elemento){
	no* aux;
	if(*raiz == NULL){
		aux = (no*)malloc(sizeof(no));
		aux->valor = elemento;
		aux->dir = aux->esq = NULL;
		*raiz = aux;
		return;
		free(aux);
		aux = NULL;
	}			
	if(elemento < (*raiz)->valor){
		inserir(&(*raiz)->esq, elemento);
		return;
	}
	if(elemento > (*raiz)->valor){
		inserir(&(*raiz)->dir, elemento);
		return;
	}
	if(elemento == (*raiz)->valor){
		printf("\n\nElemento %d já existe na arvore!\n\n", elemento);
		return;
	}	
}
no* LL(no** pai){//Rotação simples a direita
	printf(">LL>");
	no* b = *pai;
 	no* a = b->esq;
 	b->esq = a->dir;
 	a->dir = b;
 	*pai = a;
 	return a;
}
no* RR(no** pai){//Rotação simples a esquerda
	printf(">RR>");
	no* a = *pai;
	no* b = a->dir;
	a->dir = b->esq;
	b->esq = a;
	*pai = b;
	return b;
}
no* RL(no** pai){
	printf("\n\tRL>");
 	LL(&(*pai)->dir);
 	return RR(pai);
}
no* LR(no** pai){
	printf("\n\tLR>");
	RR(&(*pai)->esq);
	return LL(pai);
}
int fator(no* raiz){
	int b;
	b = (altura(raiz->esq)) - (altura(raiz->dir));
	return b;
}
no* balanceamento(no* raiz){
	int f = fator(raiz);
	if(f > 1){
		if(fator(raiz->esq) > 0)
			raiz = LL(&raiz);
		else
			raiz = LR(&raiz);
	}
	if(f < -1){
		if(fator(raiz->dir) > 0)
			raiz = RL(&raiz);
		else
			raiz = RR(&raiz);
	}
	return raiz;
}
 
no* inserir_bal(no** RAIZ, int elemento){
	if((*RAIZ) == NULL){
		no* aux1 = (no*)malloc(sizeof(no));
		aux1->valor = elemento;
		aux1->dir = aux1->esq = NULL;
		*RAIZ = aux1;
		free(aux1);
		aux1 = NULL;
	}
	if(elemento < (*RAIZ)->valor){
			(*RAIZ)->esq = inserir_bal(&(*RAIZ)->esq, elemento);
			(*RAIZ) = balanceamento(*RAIZ);
	}
	if(elemento > (*RAIZ)->valor){
			(*RAIZ)->dir = inserir_bal(&(*RAIZ)->dir, elemento);
			(*RAIZ) = balanceamento(*RAIZ);
	}
	return (*RAIZ);
}
no* doisfilhos(no* root){
	if(root == NULL)
		return NULL;
	else if(root->esq == NULL)
		return root;
	else
		return doisfilhos(root->esq);
}
no* remover(no** raiz, int elemento){
	if(*raiz == NULL)
		return NULL;
	else if(elemento < (*raiz)->valor){
		remover(&(*raiz)->esq, elemento);
	}
	else if(elemento > (*raiz)->valor){
		remover(&(*raiz)->dir, elemento);
	}
	else{
		if((*raiz)->esq == NULL && (*raiz)->dir == NULL){
			free(*raiz);
			*raiz = NULL;
		}
	else if((*raiz)->esq == NULL){
		no* aux = (*raiz);
		(*raiz) = (*raiz)->dir;
		free(aux);
		aux = NULL;
	}
	else if((*raiz)->dir == NULL){
		no* aux = (*raiz);
		(*raiz) = (*raiz)->esq;
		free(aux);
		aux = NULL;
	}
	else{//((*raiz)->esq != NULL && (*raiz)->dir != NULL) nó com dois filhos
		no *aux = NULL;
		aux = doisfilhos((*raiz)->dir);
		(*raiz)->valor = aux->valor;
		remover(&(*raiz)->dir, (*raiz)->valor);
		}
	}
	return (*raiz);
}
 
void pesquisaOrdemSimetrica(no* raiz, int nivel){
	int i;
	if(raiz == NULL)
		return;
	pesquisaOrdemSimetrica(raiz->esq, nivel+1);
	for(i=0; i<nivel;i++){
			printf(" ");
		}
	printf("%d\n", raiz->valor);
	pesquisaOrdemSimetrica(raiz->dir, nivel+1);	
}
void pesquisaPosOrdem(no* raiz, int nivel){
	int i;
	if(raiz == NULL)
		return;
	pesquisaPosOrdem(raiz->esq, nivel+1);
	pesquisaPosOrdem(raiz->dir, nivel+1);
		for(i=0; i<nivel;i++){
			printf(" ");
		}
	printf("%d\n", raiz->valor);
}
void pesquisaPreOrdem(no* raiz, int nivel){
	int i;
	if(raiz == NULL)
		return;	
	for(i=0; i<nivel;i++){
			printf(" ");
		}
	printf("%d (%d)\n", raiz->valor, fator(raiz));
	pesquisaPreOrdem(raiz->esq, nivel+1);
	pesquisaPreOrdem(raiz->dir, nivel+1);
}
void esvazia(no** raiz){
	if(*raiz == NULL) return;
	esvazia(&(*raiz)->esq);
	esvazia(&(*raiz)->dir);
	free(*raiz);
	*raiz = NULL;
}
int main(){
	setlocale(LC_ALL, "Portuguese");
	int alt, alt_novo, op, op2, i, x, z, v[def];
	no* raiz = NULL;
	do{
		printf("\n\nMENU:\n\n");
		printf("1 - Inserir\n2 - Calcular Altura\n3 - Balancear\n4 - Remover\n5 - Imprimir\n0 - Sair\n\n>");
		scanf("%d", &op);
			switch(op){
				case 1:
						for(i=0;i<def;i++){
							printf("\nv[%d] = ",i);
							scanf("%d", &v[i]);		
							inserir(&raiz, v[i]);
						}
					break;
				case 2:
					if(raiz == NULL)
						printf("\nArvore Vazia!\n");
					else{
						alt = altura(raiz);
						printf("\nA altura é %d\n", alt);
					}
					break;
				case 3:
					for(i=0;i<def;i++){
					inserir_bal(&raiz, v[i]);
					}
					alt_novo = altura(raiz);
					printf("\nA altura\n\tSem balancear: %d\n\tBalaceado: %d", alt, alt_novo);
					break;
				case 4:
					printf("\tREMOVER?\n1 - Elemento\n2 - Tudo\n>");
					scanf("%d", &op2);
					if(op2 == 1){
					printf("\nDigite o valor a ser removido: ");
	
					scanf("%d", &z);
					remover(&raiz, z);	
					}
					if(op2 == 2){
					esvazia(&raiz);
					printf("\nArvore Esvaziado!\n");	
					}
					break;
				case 5:
					printf("\n\n\tValor (fator de balaceamento)\n\n");
					pesquisaPreOrdem(raiz, 0);
					break;
				case 0:
					printf("\n");
					esvazia(&raiz);
					system("pause");
					break;
				default: system("cls");
			}
	}while(op != 0);
}