AVL com Ncurses em C
quinta-feira, julho 17th, 2008Olhando os trabalhos que realizei na faculdade. Encontrei uma AVL desenvolvida para a cadeira de estutura de dados. Implementei utilizando como interface gráfica NCURSES, para mostrar a árvore.
Irei compartilhar o código. Com certeza será bastante util para quem está estudando.
Este código tem alguns conceitos interessantes como:
- Não utiliza variáveis globais
- Os dados são inseridos na árvore quando ficar desbalanceada é informado e solicitado ao usuário se deseja balancear a árvore
- Informe como a árvore esta desbalanceada em quatro casos: EE,ED,DD e DE
- Calcula a altura da árvore
- Menu em Ncurses
- Visualização da árvore com Ncurses
/* * Nome: Marlon Luis Petry * Description: AVL compilacao gcc "Avl-Marlon.c" -o "Avl-Marlon" -g -lncurses -w Data: 20/10/2005 * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #include#include #include #include #define CENTERX COLS/2 #define CENTERY LINES/2 #define DIST 5 typedef char string[50]; typedef struct t { string info; int alt; struct t *pai; struct t *left; struct t *right; }tree; int tipoBal = -1; string bal[4] = {”Caso EE”,”Caso ED”,”Caso DD”,”Caso DE”}; tree *bal_esq(tree *aux); tree *bal_dir(tree *aux); tree *rotacaoRR(tree *aux); tree *rotacaoLL(tree *aux); tree *rotacaoLR(tree *aux); tree *rotacaoRL(tree *aux); tree *insere(tree **root, string info, int h) { char ch; tree *aux; if (*root == NULL) { aux = (tree *) malloc(sizeof(tree)); strcpy(aux->info,info); aux->left = NULL; aux->right = NULL; aux->pai = NULL; aux->alt = 0; h = 1; *root = aux; } else { if (strcmp(info,(*root)->info) < 0) { insere(&(*root)->left, info, h); //Atualiza PAI do nó inserido if ((*root)->left->pai == NULL) (*root)->left->pai = *root; if (h) switch((*root)->alt) { //Estava mais alto à direita e inseriur mais um nó à esquerda case -1: (*root)->alt = 0; h = 0; //Não propaga os ajustes nos fatores de balanceamento break; case 0: (*root)->alt = 1; //o lado esquerdo fica maior e os fatores de //balanceamento acima deverao ser ajustados break; case 1: mvprintw(8,10,”Arvore Desbalaceou a esquerda A = %s Y = %s”,(*root)->info,info); mvprintw(9,10,”Baleancear (S)im (N)nao: “); scanw(”%c”,&ch); if(ch == ‘S’ || ch == ’s’) { *root = bal_esq(*root); //FB == 2 -> retorna a sub-árvore balanceada h = 0; //não propaga a atualização dos fatores de } //balanceamento break; } } else { insere(&(*root)->right, info, h); //Atualiza PAI do nó inserido if ((*root)->right->pai != NULL) (*root)->right->pai = *root; if (h) switch ((*root)->alt) { //estava mais alto à esquerda e inseriu mais um nó à direita case 1: (*root)->alt = 0; h = 0; //não propaga os ajustes nos fatores de balanceamneto break; case 0: (*root)->alt = -1; // o lado direito fica maior do que o esquerdo e // o ajuste deve ser propagado break; case -1: //FB == -2 -> retorna a sub-árvore balanceada mvprintw(8,10,”Arvore Desbalaceou a direita A = %s Y = %s”,(*root)->info,info); refresh(); mvprintw(9,10,”Baleancear (S)im (N)nao: “); scanw(”%c”,&ch); if(ch == ‘S’ || ch == ’s’) { *root = bal_dir(*root); h = 0; //não propaga a atualização dos fatores de } //balanceamento break; } } } return(*root); } tree *bal_esq(tree *aux) { tree *p; p = aux->left; if (p->alt == 1) { //sinais iguais e positivo tipoBal = 1; aux = rotacaoLL(aux); } else { tipoBal = 2; aux = rotacaoLR(aux); //sinais diferentes } aux->alt = 0; return(aux); } /* * O novo nó foi inserido à direita. Ocorreu desbalanceamento (fb == 2) */ tree *bal_dir(tree *aux) { tree *p; p = aux->right; if (p->alt == -1) //Sinais iguais e negativo { tipoBal = 3; aux = rotacaoRR(aux); } else { tipoBal = 4; aux = rotacaoRL(aux); //Sinais diferentes } aux->alt = 0; refresh(); return(aux); } //rotacoes tree *rotacaoRR(tree *aux) { tree *p; p = aux->right; aux->right = p->left; if (p->left != NULL) p->left->pai = aux; p->left = aux; p->pai = aux->pai; aux->pai = p; aux->alt = 0; return(p); } tree *rotacaoLL(tree *aux) { tree *p; p = aux->left; aux->left = p->right; if (p->right != NULL) p->right->pai = aux; p->right = aux; p->pai = aux->pai; aux->pai = p; aux->alt = 0; return(p); } tree *rotacaoLR(tree *aux) { tree *pai; //ponteiro para depois atualizar o pai após a rotação tree *no_left; //ponteiro para o filho esquerdo para atualizar o FB após a rotação tree *novo_no; //ponteiro à ser retornado int FB_fright; //fator de balanceamento do no à direita do filho esquerdo pai = aux->pai; no_left = aux->left; FB_fright = no_left->right->alt; aux->left = rotacaoRR(no_left); novo_no = rotacaoLL(aux); novo_no->pai = pai; aux->alt = (FB_fright == 1)?-1:0; //Atualiza FB do nó rotacionado no_left->alt = (FB_fright == -1)?1:0; // Atualiza FB do nó à esquerda do nó rotacionado return(novo_no); } /* * Atualização do FB e balanceamento para a raÃz esquerda */ tree *balanceamento_esquerdo(tree *no, int h) { tree *f_dir; int fb_dir; switch (no->alt) { case 1: no->alt = 0; break; case 0: no->alt = -1; h = 1; break; case -1: f_dir = no->right; fb_dir = f_dir->alt; if (fb_dir <= 0) { f_dir = rotacaoRR(no); if (fb_dir == 0) { no->alt = -1; f_dir->alt = 1; h = 0; } else { no->alt = 0; f_dir->alt = 0; } no = f_dir; } else { no = rotacaoRL(no); no->alt = 0; } } return(no); } /* * Atualização do FB e balanceamento para a raiz direita */ tree *balanceamento_direito(tree *no, int h) { tree *f_esq; int alt_esq; switch (no->alt) { case -1: no->alt = 0; break; case 0: no->alt = 1; h = 0; break; case 1: f_esq = no->left; alt_esq = f_esq->alt; if (alt_esq >= 0) { f_esq = rotacaoLL(no); if (alt_esq == 0) { no->alt = 1; f_esq->alt = -1; h = 0; } else { no->alt = 0; f_esq->alt = 0; } no = f_esq; } else { no = rotacaoLR(no); no->alt = 0; } } return(no); } /* * Busca nó substituto e realizada a remoção (busca o mais à direita do nó esquerdo */ tree *busca_remove(tree *no, tree *no_chave, int h) { tree *no_removido; if (no->right != NULL) { no->right = busca_remove(no->right, no_chave, h); if (h) no = balanceamento_direito(no, h); } else { strcpy(no_chave->info,no->info); no_removido = no; no = no->left; if (no != NULL) no->pai = no_removido->pai; h = 1; //Deve propagar a atualização dos FB free(no_removido); } return(no); } /* * Remoção da Ãrvore AVL */ tree *removeTree(tree **raiz, int info, int h) { if (*raiz == NULL) { printf(”Chave não localizada !”); h = 0; } else { if (strcmp((*raiz)->info, info) > 0) { removeTree(&(*raiz)->left, info, h); if (h) *raiz = balanceamento_esquerdo(*raiz, h); } else if (strcmp((*raiz)->info , info) < 0) { removeTree(&(*raiz)->right, info, h); if (h) *raiz = balanceamento_direito(*raiz,h); } else { //Encontrou o elemento a ser removido if ((*raiz)->right == NULL) { if ((*raiz)->left != NULL) //Escolhe o nó à esquerda como substituto (*raiz)->left->pai = (*raiz)->pai; *raiz = (*raiz)->left; h = 1; } else if ((*raiz)->left == NULL) { if ((*raiz)->right != NULL) //Escolhe o nó à direita como substituto (*raiz)->right->pai = (*raiz)->pai; *raiz = (*raiz)->right; h = 1; } else { // Busca o elemento mais à direita do nó esquerdo (*raiz)->left = busca_remove((*raiz)->left, *raiz, h); //Se necessário efetua balanceamento (Esquerdo pois a função //busca_remove foi para o nó esquerdo) if (h) *raiz = balanceamento_esquerdo(*raiz, h); } } } return(raiz); } tree *rotacaoRL(tree *aux) { tree *pai; //ponteiro para depois atualizar o pai após a rotação tree *no_right; //ponteiro para o filho direito para atualizar o FB após a rotação tree *novo_no; //ponteiro à ser retornado int FB_fleft; //fator de balanceamento do no à esquerda do filho direito pai = aux->pai; no_right = aux->right; FB_fleft = no_right->left->alt; aux->right = rotacaoLL(no_right); novo_no = rotacaoRR(aux); novo_no->pai = pai; aux->alt = (FB_fleft == -1)?1:0; //Atualiza FB do nó rotacionado no_right->alt = (FB_fleft == 1)?-1:0; // Atualiza FB do nó à direita do nó rotacionado return(novo_no); } int maxDepth(tree *node) { if (node==NULL) { return(0); } else { int lDepth = maxDepth(node->left); int rDepth = maxDepth(node->right); if (lDepth > rDepth) return(lDepth+1); else return(rDepth+1); } } //print int print(tree *r,int x, int y) { int TotalWidth = width(r)*DIST; int centerWidth = (x + TotalWidth/2); int tamStr; int d = 0; //int centerWidthLinen= centerWidth +20; char t; if(r != NULL) { int leftWidth = width(r->left) * DIST; int rigtWidth = width(r->right) * DIST; tamStr = strlen(r->info); mvprintw(y + (DIST/20),(centerWidth -1- (tamStr/2)),”%s”, r->info); if (r->left != NULL) { int leftX = print(r->left, x , y + DIST); } if (r->right != NULL) { int rightX = print(r->right, x + leftWidth, y + DIST); } } return centerWidth; } int width(tree *root) { if(root == NULL) return 1; else if(root->left == NULL && root->right == NULL) return 1; else return width(root->left) + width(root->right); } main() { tree *root = NULL; char ch; string msg; string info; int opt; int d=0; initscr(); bkgd(COLOR_PAIR(4)); strcpy(msg,”Pressione Qualquer Tecla”); while(1) { clear(); mvprintw(1,10,”%s”,”(1) - Inserir novo valor “); mvprintw(2,10,”%s”,”(2) - Mostrar”); mvprintw(3,10,”%s”,”(3) - Remove”); mvprintw(4,10,”%s”,”(4) - Altura”); mvprintw(5,10,”%s”,”(5) - Sair”); mvprintw(6,10,”[ ]“); move(6,11); scanw(”%d”,&opt); refresh(); switch(opt) { mvprintw(10,10,”%d”,opt); case 1: mvprintw(7,10,”%s”,”Informe Valor: “); refresh(); getstr(info); insere(&root,info,1); break; case 2: clear(); print(root,CENTERX,0); mvprintw(LINES -2,CENTERX,”%s”,bal[tipoBal]); tipoBal = -1; mvprintw(LINES -1,CENTERX,”%s”,msg); getch(); break; case 3: mvprintw(7,10,”%s”,”Informe Valor: “); refresh(); getstr(info); removeTree(&root,info,1); break; case 4: //mvprintw(LINES - 1,CENTERX,”%s”,”f para sair “); mvprintw(7,10,”%s”,”Nivel”); refresh(); d = maxDepth(root); mvprintw(8,10,”%d”,d); refresh(); break; case 5: //mvprintw(LINES - 1,CENTERX,”%s”,”f para sair “); ch = ‘f’; break; } refresh(); if(ch == ‘f’) break; } endwin(); }
Não se esqueça este código é GPL pode ser usado desde que mantido os direitos autorais.
Assinem os FEEDS é de graça. Só essa semana 
