Tree
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305
#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;
}
C
INFO