Implementação de arvore AVL em lingauem C

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

/*
 Implementação de arvore binária de busca.
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct no{
	int dado;
	struct no *direita; /*Um ponteiro para direita para propria struct no*/
	struct no *esquerda; /*Um ponteiro para esquerda para propria struct no*/
}t_no_arvore;
t_no_arvore* criaNo(int dado);
int inserirNo(t_no_arvore *raiz, int dado);
void ordem(t_no_arvore *raiz);
int alturaArvore(t_no_arvore *raiz);
int estaVazia(t_no_arvore *raiz);
int quantidadeNos(t_no_arvore *raiz);
int somaTodosElementos(t_no_arvore *raiz);
t_no_arvore* removeNo_FUNCAO_AUX(t_no_arvore *atual);
t_no_arvore* removeNo(t_no_arvore *raiz, int dado_Removido);
/*Cria a arvore*/
t_no_arvore* criaNo(int dado) {
	t_no_arvore *no = (t_no_arvore*) malloc(sizeof(t_no_arvore));
	no->direita = NULL;
	no->esquerda = NULL;
	no->dado = dado;
	return no;
}
/*Insere um novo nó na arvore*/
int inserirNo(t_no_arvore *raiz, int dado) {
	if(raiz == NULL) {
		return -1;
	}else {
		if(raiz->dado > dado) { /*Inserindo o dado pela esquerda da arvore*/
			if(raiz->esquerda == NULL) {
				raiz->esquerda = criaNo(dado);
			}else {
				return inserirNo(raiz->esquerda, dado);
			}
		}else if(raiz->dado < dado) {
			if(raiz->direita == NULL) {
				raiz->direita = criaNo(dado);
			}else {
				return inserirNo(raiz->direita, dado);
			}
		}
	}
	return -1;
}
void ordem(t_no_arvore *raiz) {
	if(raiz != NULL) {
		ordem(raiz->esquerda);
		printf("%d\n", raiz->dado);
		ordem(raiz->direita);
	}
}
/*Retorna a altura da arvore (Da raiz mais alta paara folha mais baixa)*/
int alturaArvore(t_no_arvore *raiz) { 
	if(raiz == NULL) {
		return 0;
	}
	int altura_direita, altura_esquerda;
	altura_direita = alturaArvore(raiz->direita);
	altura_esquerda = alturaArvore(raiz->esquerda);
	if(altura_direita > altura_esquerda) {
		//printf("esquerda\n");
		return 1 + altura_direita; /*O return sempre setorna para função que chamo ele*/ 
	}else {
		//printf("direita\n");
		return 1 + altura_esquerda;
	}
}
/*Verifica se a arvore esta vazia*/
int estaVazia(t_no_arvore *raiz) { /*Verifica se a arvore esta vazia*/
	if(raiz == NULL) { /*Problema na criação da arvore*/
		return -1;
	}else {
		return 0;
	}
}
/*Retorna a quantidade de nós de uma arvore binaria*/
int quantidadeNos(t_no_arvore *raiz) {
	if(raiz == NULL) {
		return 0;
	}
	int altura_direita = quantidadeNos(raiz->direita);
	int altura_esquerda = quantidadeNos(raiz->esquerda);
	
	return (altura_esquerda+altura_direita+1);
}
/*Retorna a soma do dado contido em cada nó*/
int somaTodosElementos(t_no_arvore *raiz) {
	int soma = 0;
	if(raiz != NULL) {
		return soma = raiz->dado + somaTodosElementos(raiz->direita) + somaTodosElementos(raiz->esquerda);
	}else {
		return 0;
	}
}
int somaFolhas(t_no_arvore *raiz) {
	int soma;
	if(raiz == NULL) {
		return 0;
	}
	if((raiz->esquerda == NULL) && (raiz->direita == NULL)) {
		return soma += raiz->dado;
	}
	return somaFolhas(raiz->esquerda) + somaFolhas(raiz->direita);
}
//#####################################################################################
/*Remoção de elemento*/
t_no_arvore* removeNo_FUNCAO_AUX(t_no_arvore *atual) {
	t_no_arvore *no1 = NULL, *no2 = NULL;
	if(atual->esquerda == NULL) {
		no2 = atual->direita;
		free(atual);
		return no2;
	}else {
		no1 = atual, no2 = atual->esquerda;
		while(no2->direita != NULL) {
			no1 = no2;
			no2 = no2->direita;
		}
		if(no1 != atual) {
			no1->direita = no2->esquerda;
			no2->esquerda = atual ->esquerda;
		}
		no2->direita = atual->direita;
		free(atual);
		return no2;
	}
	
}
t_no_arvore* removeNo(t_no_arvore *raiz, int dado_Removido) {
	if(raiz == NULL){
		return raiz;
	}
	t_no_arvore *anterior = NULL, *atual = raiz;
	while(atual != NULL) {
		if(dado_Removido == atual->dado) {
			if(atual == raiz) {
				raiz = removeNo_FUNCAO_AUX(atual);
			}else {
				if(anterior->direita == atual) {
					anterior->direita = removeNo_FUNCAO_AUX(atual);
				}else {
					anterior->esquerda = removeNo_FUNCAO_AUX(atual);
				}
			}
			return raiz;
		}
		anterior = atual;
		if(dado_Removido > atual->dado) {
			atual = atual->direita;
		}else {
			atual = atual->esquerda;
		}
	}
}
//#####################################################################################
/*Verifica se a árvore esta balanceada*/
int estaBalanceada(t_no_arvore * raiz) {
	if(raiz == NULL) {
		return 1;
	}
	if(!estaBalanceada(raiz->esquerda)) {
		return 0;
	}
	if(!estaBalanceada(raiz->direita)) {
		return 0;
	}
	if(abs(alturaArvore(raiz->esquerda) - alturaArvore(raiz->direita)) > 1) {
		return 0;
	}
	return 1;	
}
/*t_no_arvore* rotacionaLL(t_no_arvore *raiz) {
	t_no_arvore *x = raiz->esquerda;
	raiz->esquerda = x->direita;
	x->direita = raiz;
	return x; 
}*/
t_no_arvore* rotacionaRR(t_no_arvore *raiz) {
	t_no_arvore *x = raiz->direita;
	raiz->direita = x->esquerda;
	x->esquerda = raiz;
	return x; 
}
int main(void) {
	int dado, qtd_dado;
	printf("Digite a quantidade de elemento(s): ");
	scanf("%d", &qtd_dado);
	scanf("%d", &dado);
	t_no_arvore *raiz = criaNo(dado);		
	qtd_dado--;
	while(qtd_dado--) {
		scanf("%d", &dado);
		inserirNo(raiz, dado);
	}
	printf("Ordem:\n");
	ordem(raiz);
	return 0;
}