Created
December 17, 2015 23:29
-
-
Save leandromuto/f9d01f38c8e11a1722c5 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* Árvore AVL | |
* | |
* Fator de balanceamento = hdir - hesq | |
* | |
*/ | |
#include <stdlib.h> | |
#include <stdio.h> | |
#include <string.h> | |
typedef struct cel { | |
char nome[100]; | |
struct cel *prox; | |
} tupla; // OK | |
typedef struct no { | |
int num; | |
int balanceamento; /* balanceamento = hdir - hesq */ | |
int altura; | |
int countNomes = 0; | |
struct no *esq = nullptr; | |
struct no *dir = nullptr; | |
tupla *tupla; | |
} folha; // OK | |
folha *buscaFolha(folha *ini, int numFolha) { | |
folha *aux = ini; | |
if(ini == nullptr) { | |
printf("\n\n\nRaiz não encontrada.\n\n\n"); | |
return nullptr; | |
} | |
while(aux != nullptr) { | |
if(numFolha == aux->num) { | |
return aux; | |
} | |
else if(numFolha < aux->num) { | |
aux = aux->esq; | |
} | |
else if(numFolha > aux->num) { | |
aux = aux->dir; | |
} | |
} | |
printf("Índice %d não encontrada.\n", numFolha); | |
return aux; | |
} // OK | |
void imprimeNomes(folha *ini, int numFolha) { | |
folha *aux = ini; | |
folha *f = buscaFolha(aux, numFolha); | |
tupla *auxTu = f->tupla; | |
if(auxTu->prox == nullptr) { | |
printf("Nenhum nome na lista da folha %d.\n", numFolha); | |
return; | |
} | |
printf("\n\n|---Índice %d---|\n", numFolha); | |
auxTu = auxTu->prox; | |
while(auxTu != nullptr) { | |
printf("| Nome: %s\n", auxTu->nome); | |
auxTu = auxTu->prox; | |
} | |
printf("|---Total---%d -|\n\n", f->countNomes); | |
} // OK | |
void ordenaNome(tupla *t) { | |
tupla *aux; | |
if(t->prox == nullptr) { | |
printf("Lista vazia."); | |
return; | |
} | |
aux = t->prox; | |
while(aux->prox != nullptr) { | |
int cmp = strcmp(aux->nome, aux->prox->nome); | |
if(cmp > 0) { | |
char cp[100]; | |
strcpy(cp, aux->nome); | |
strcpy(aux->nome, aux->prox->nome); | |
strcpy(aux->prox->nome, cp); | |
aux = t->prox; | |
} | |
aux = aux->prox; | |
} | |
} // OK | |
tupla *insereLista(folha *ini, int numFolha, char nome[]) { // insere nome na lista encadeada da folha que inserir como parametro | |
folha *folhaExiste = buscaFolha(ini, numFolha); | |
if(folhaExiste == nullptr) { // verificando se a folha existe, se não sai fora | |
return nullptr; | |
} | |
tupla *t, *aux; | |
t = (tupla *) malloc(sizeof(tupla)); // criando nova tupla | |
strcpy(t->nome, nome); // copia nome do parâmetro pra tupla->nome | |
aux = folhaExiste->tupla; // aux recebe cabeça das tuplas da struct folha | |
t->prox = folhaExiste->tupla->prox; // aponta pra qual a cabeça tava apontando | |
aux->prox = t; // cabeça aponta pra nova | |
printf("Nome \"%s\" inserido no índice %d.\n\n", nome, numFolha); | |
folhaExiste->countNomes++; | |
ordenaNome(folhaExiste->tupla); | |
return t; | |
} // OK | |
folha *novoNo(int num) { | |
folha *novo = (folha*) malloc(sizeof(folha)); | |
novo->num = num; | |
novo->esq = nullptr; | |
novo->dir = nullptr; | |
novo->altura = 1; | |
novo->tupla = (tupla *) malloc(sizeof(tupla)); | |
novo->tupla->prox = nullptr; | |
printf("Nó inserido com sucesso!\n\n\n"); | |
return novo; | |
} // OK | |
int altura(folha *n) { | |
if (n == NULL) { | |
return 0; | |
} | |
return n->altura; | |
} // OK | |
folha *rotacionarDireita(folha *y) { | |
folha *x = y->esq; | |
folha *T2 = x->dir; | |
// faz rotação | |
x->dir = y; | |
y->esq = T2; | |
// atualiza altura | |
y->altura = std::max(altura(y->esq), altura(y->dir))+1; | |
x->altura = std::max(altura(x->esq), altura(x->dir))+1; | |
// retorna nova raiz | |
return x; | |
} // OK | |
folha *rotacionarEsquerda(folha *x) { | |
folha *y = x->dir; | |
folha *T2 = y->esq; | |
// faz rotação | |
y->esq = x; | |
x->dir = T2; | |
// altualiza altura | |
x->altura = std::max(altura(x->esq), altura(x->dir))+1; | |
y->altura = std::max(altura(y->esq), altura(y->dir))+1; | |
// retorna nova raiz | |
return y; | |
} // OK | |
// balanceamento do nó n | |
int balanceamento(folha *n) { | |
if (n == NULL) | |
return 0; | |
return altura(n->esq) - altura(n->dir); | |
} // OK | |
folha *insereNo(folha *fol, int num) { | |
if(fol == nullptr) { | |
return novoNo(num); | |
} | |
if(num < fol->num) { | |
fol->esq = insereNo(fol->esq, num); | |
} | |
else { | |
fol->dir = insereNo(fol->dir, num); | |
} | |
fol->altura = std::max(altura(fol->esq), altura(fol->dir)) + 1; // atualiza a altura do anterior | |
int bal = balanceamento(fol); // pega o valor do balanceamento do anterior para ver para qual lado rotacionar | |
// Rotação dupla a esquerda | |
if (bal > 1 && num < fol->esq->num) { | |
printf("Rotação dupla a esquerda.\n"); | |
return rotacionarDireita(fol); | |
} | |
// Rptação dupla a direita | |
if (bal < -1 && num > fol->dir->num) { | |
printf("Rotação dupla a direita.\n"); | |
return rotacionarEsquerda(fol); | |
} | |
// Rotação a esquerda e depois direita | |
if (bal > 1 && num > fol->esq->num) | |
{ | |
fol->esq = rotacionarEsquerda(fol->esq); | |
printf("Rotação a esquerda e depois a direita.\n"); | |
return rotacionarDireita(fol); | |
} | |
// Rotação a esquerda e depois a direita | |
if (bal < -1 && num < fol->dir->num) | |
{ | |
fol->dir = rotacionarDireita(fol->dir); | |
printf("Rotação a direita e depois a esquerda.\n"); | |
return rotacionarEsquerda(fol); | |
} | |
return fol; | |
} // OK | |
// A utility function to print preorder traversal of the tree. | |
// The function also prints height of every node | |
void ordemArvore(folha *root) { | |
if(root != nullptr) { | |
printf("%d ", root->num); | |
ordemArvore(root->esq); | |
ordemArvore(root->dir); | |
} | |
} | |
int main() { | |
int opc = 9; | |
folha *root = nullptr; | |
while(opc != 0) { | |
printf("\n----------- Menu -------------------\n"); | |
printf("| 1 - Inserir nó ------------------|\n"); | |
printf("| 2 - Inserir nome ----------------|\n"); | |
printf("| 3 - Exibir nomes ----------------|\n"); | |
printf("| 4 - Exibir árvore em ordem ------|\n"); | |
printf("| 0 - Sair ------------------------|\n"); | |
printf("------------------------------------\n"); | |
printf("Escolha uma opção: "); | |
scanf("%d", &opc); | |
switch (opc) { | |
case 1: { | |
int ind; | |
printf("Índice do nó a ser inserido: "); | |
scanf("%d", &ind); | |
root = insereNo(root, ind); | |
break; | |
} | |
case 2: { | |
int ind; | |
char nome[30]; | |
printf("Você escolheu inserir um nome em um índice.\n"); | |
printf("Em qual índice deseja colocar o nome?\n"); | |
printf("Índice: "); | |
scanf("%d", &ind); | |
folha *aux = buscaFolha(root, ind); | |
while(aux == nullptr) { | |
printf("\n\n\nTente novamente.\n"); | |
printf("Em qual índice deseja colocar o nome?\n"); | |
printf("Índice: "); | |
scanf("%d", &ind); | |
aux = buscaFolha(root, ind); | |
} | |
printf("Nome que deseja colocar: "); | |
scanf("%s", &nome); | |
insereLista(root, ind, nome); | |
imprimeNomes(root, ind); | |
break; | |
} | |
case 3: { | |
int ind; | |
printf("\n\n\nVocê escolheu imprimir os nomes de um índice.\n"); | |
printf("De qual índice deseja imprimir?\n"); | |
printf("Índice: "); | |
scanf("%d", &ind); | |
folha *f = buscaFolha(root, ind); | |
if(f == nullptr) { | |
// printf("\n\n\nVocê escolheu imprimir os nomes de um índice.\n"); | |
// printf("De qual índice deseja imprimir?\n"); | |
// printf("Índice: "); | |
// scanf("%d", &ind); | |
// | |
// f = buscaFolha(root, ind); | |
return 0; | |
} | |
imprimeNomes(root, ind); | |
break; | |
} | |
case 4: { | |
ordemArvore(root); | |
break; | |
} | |
case 5: { | |
break; | |
} | |
case 0: { | |
exit(0); | |
break; | |
} | |
default: { | |
printf("Opção inválida. Tente novamente.\n\n\n"); | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment