#include <stdio.h> #include <stdlib.h> //Criação da estrutura de um nó da arvore struct No{ int num; //Número armazenado int fb; //Fator de balanceamento struct No* L; //Filho à esquerda struct No* R; //Filho à direita }; typedef struct No No; /* UTILIZANDO PONTEIRO DUPLO **pRaiz == ARVORE pRaiz->num == Resulta em ERRO pois a ARVORE em si não possui um número, apenas os nós Para acessar os atributos é preciso referenciar o NÓ e não a ARVORE *pRaiz = Nó (*pRaiz)->num == Correto para acessar um atributo de um nó */ /* Define o primeiro NÓ da ARVORE como nulo */ void criarArvore(No **pRaiz){ *pRaiz = NULL; } /*Mostra os números recursivamente*/ void showRED(No **pRaiz){ if((*pRaiz) != NULL){ printf("%d - ",(*pRaiz)->num); /*R*/ showRED(&(*pRaiz)->L); /*E*/ showRED(&(*pRaiz)->R); /*D*/ } } void showERD(No **pRaiz){ if((*pRaiz) != NULL){ showERD(&(*pRaiz)->L); printf("%d(%d) - ",(*pRaiz)->num,(*pRaiz)->fb); showERD(&(*pRaiz)->R); } } void showEDR(No **pRaiz){ if((*pRaiz) != NULL){ showEDR(&(*pRaiz)->L); showEDR(&(*pRaiz)->R); printf("%d - ",(*pRaiz)->num); } } /*Busca o nó que possui o número 'n' salvo*/ No* buscar(No **pRaiz,int n){ //Se o nó tem o número retorna ele if((*pRaiz)->num == n) return (*pRaiz); //Se o número desse nó é maior que 'n', procura 'n' a esquerda if((*pRaiz)->num > n) return buscar(&(*pRaiz)->L,n); //Caso contrário procura 'n' a direita else return buscar(&(*pRaiz)->R,n); } /*Retorna o pai do nó que possui o número 'n' salvo*/ No* buscarPai(No **pRaiz,int n){ No* pai = NULL; //Se o nó atual possir o número retorna ele (caso o número procurado seja a raiz principal da arvore) if((*pRaiz)->num == n) return (*pRaiz); //Verifica se existe filho à direita if((*pRaiz)->R){ //Verifica se o filho a direita possui o número, se sim retorna este nó if((*pRaiz)->R->num == n) return (*pRaiz); //Senão passa para o filho à direita else pai = buscarPai(&(*pRaiz)->R,n); } //Verifica se existe filho à esquerda e o pai ainda não foi encontrado if((*pRaiz)->L && !pai){ //Verifica se o filho a esquerda possui o número, se sim retorna este nó if((*pRaiz)->L->num == n) return (*pRaiz); //Senão passa para o filho à esquerda else pai = buscarPai(&(*pRaiz)->L,n); } return pai; } /*Insere novo valor na àrvore*/ void inserir(No **pRaiz,int n){ //Caso o nó não exista aloca espaço, insere o número e define filhos como NULL if(*pRaiz == NULL){ *pRaiz = (No*) malloc(sizeof(No)); (*pRaiz)->R = NULL; (*pRaiz)->L = NULL; (*pRaiz)->num = n; }else{ //Caso o número seja maior que o número do nó insere à direita if(n > (*pRaiz)->num) inserir(&(*pRaiz)->R,n); //Senão insere à esquerda if(n < (*pRaiz)->num) inserir(&(*pRaiz)->L,n); } } /*Retonar o menor valor da árvore*/ No* min(No **pRaiz){ //Anda até o ultimo nó à esquerda e o retorna if((*pRaiz)->L) min(&(*pRaiz)->L); return (*pRaiz); } /*Retonar o maior valor da árvore*/ No* max(No **pRaiz){ //Anda até o ultimo nó à direita e o retorna if((*pRaiz)->R) max(&(*pRaiz)->R); return (*pRaiz); } /*Remove um número da àrvore (esta função não funciona caso o nó a ser removido tenha NETOS) REMOVENTO UM NÓ Casos: 1) Nó não tem filhos: Apenas remove o nó defininindo NULL para sua conexão com o pai 20 20 \ \ 21 (X) 2) Nó tem 1 filho: Faz com que o pai do nó aponte para o filho do nó e apaga o nó 20 20 20 \ \ \ 21 \ 21 \ (X) \ \ \ 22 22 22 3) 2 filhos: Substitui o nó pelo seu neto à esquerda do deu filho a direita, caso não tenha neto, substitui pelo filho a direita. x22x (23) (23) / \ / \ / \ 19 24 19 24 19 24 / \ / \ / \ (23) 25 x22x 25 X 25 */ No* remover(No **pRaiz,int n){ //Caso não encontre número, exibe mensagem de erro if (*pRaiz == NULL) { printf("\n%d não existe nesta àrvore!\n",n); return *pRaiz; } //Procura e remove nó com o número a ser excluído if (n < (*pRaiz)->num){ (*pRaiz)->L = remover(&(*pRaiz)->L, n); } else if(n > (*pRaiz)->num){ (*pRaiz)->R = remover(&(*pRaiz)->R, n); } //Quando encontra else { //Apenas 1 filho à direita if ((*pRaiz)->L == NULL) { No *temp = (*pRaiz)->R; free(*pRaiz); return temp; } //Apenas 1 filho à esquerda else if ((*pRaiz)->R == NULL) { No *temp = (*pRaiz)->L; free(*pRaiz); return temp; } //2 filhos No *temp = min(&(*pRaiz)->R); //Obtem nó com o menor número (*pRaiz)->num = temp->num; //Troca valores com o menor número (*pRaiz)->R = remover(&(*pRaiz)->R, temp->num); //Chama a remoção para a ultimo nó } return *pRaiz; } /*Retorna a altura de um nó*/ int altura(No **pRaiz) { //Se não existe a altura é -1 if ((*pRaiz) == NULL) return -1; else { //Obtem as alturas da esquerda e direita int hl = altura(&(*pRaiz)->L); int hr = altura(&(*pRaiz)->R); //Retorna a hr+1 se a altura direita for maior, caso contrário retorna hl+1 if (hl < hr) return hr + 1; else return hl + 1; } } /*Calcula o fator de balanceamento da alvore*/ void getFb(No **pRaiz) { /*(fb) = hr - hl*/ if (*pRaiz != NULL) { (*pRaiz)->fb = altura(&(*pRaiz)->R) - altura(&(*pRaiz)->L); getFb(&(*pRaiz)->L); //Calcula fb da esquerda getFb(&(*pRaiz)->R); //Calcula fb da direita } } /*Rotação à direita*/ No* rotR(No** pRaiz){ No* q,*temp; q = (*pRaiz)->L; temp = q->R; q->R = (*pRaiz); (*pRaiz)->L = temp; *pRaiz = q; return *pRaiz; } /*Rotação à esquerda*/ No* rotL(No** pRaiz){ No* q = NULL; No* temp = NULL; q = (*pRaiz)->R; temp = q->L; q->L = *pRaiz; (*pRaiz)->R = temp; *pRaiz = q; return *pRaiz; } /*Rotação esquerda-direita*/ No* rotLR(No** pRaiz){ (*pRaiz)->L = rotL(&(*pRaiz)->L); return rotR(&(*pRaiz)); } /*Rotação direita-esquerda*/ No* rotRL(No** pRaiz){ (*pRaiz)->R = rotR(&(*pRaiz)->R); return rotL(&(*pRaiz)); } /*Balanceia a àrvore (se fb < -1 ou > 1 está desbalanceada)*/ void balancear(No **pRaiz){ do{ getFb(&(*pRaiz)); if((*pRaiz)->fb < -1){//Caso o nó esteja pesado para a esquerda (-) //Se o sinal do filho também for negativo rotação simples à direita if((*pRaiz)->L->fb <= 0) *pRaiz = rotR(pRaiz); //Caso contrário rotação esquerda-direita else *pRaiz = rotLR(pRaiz); }else if((*pRaiz)->fb > 1){//Caso nó esteja pesado para a direita (+) //Se o sinal do filho também for positivo rotação simples à esquerda if((*pRaiz)->R->fb >= 0) *pRaiz = rotL(pRaiz); //Caso contrário rotação direita-esquerda else *pRaiz = rotRL(pRaiz); } }while((*pRaiz)->fb < -1 || (*pRaiz)->fb > 1); //Fazer isso enquando a raiz não estiver balanceada } #define size 6 //número de nós int main(void) { No *pRaiz; criarArvore(&pRaiz); //Insere nós int x[size] = {8,4,6,10,2,5}; for(int i = 0; i < size; i++){ inserir(&pRaiz,x[i]); } //Mostra estado inicial printf("Antes:"); showERD(&pRaiz); printf("\n"); //Remove número 6 remover(&pRaiz,6); //Balanceia a àrvore balancear(&pRaiz); //Mostra estado final da àrvore printf("\n"); printf("Depois:"); showERD(&pRaiz); return 0; }