Estrutura de dados e Árvore Binária - Não é AVL
Entendendo o conceito e o uso da árvore binária na estrutura de dados.
 |
| Exemplo de árvore binária não AVL. |
1 - Introdução a árvore binária
Falarei sobre a árvore binária que não será implementada em modo AVL, ou seja, não é balanceada. Comentarei sobre esse assunto em outra oportunidade. As árvores binárias são estrutura de dados com cinco componentes básicos em sua formação, que são: a raiz, nós, filhos, pais e folhas. Abaixo o que é cada elemento da árvore a imagem usada no início do artigo demonstra como fica uma árvore binária construída e quem são os elementos da mesma.
- Raiz: é o nó no topo da árvore. O que dá início a sequencia da estrutura.
- Nós: todos os seguimentos abaixo da raiz.
- Filhos: são nós depois de outros nós. Com isso temos que todo nó, exceto a raiz, será um nó filho.
- Pais: são os nós que vem antes de outros nós. Temos definido assim que a raiz sempre será um pai e, exceto as folhas, todos os outros nós também serão.
- Folhas: Os últimos nós da estrutura. Neles termina a ramificação da árvore.
2 - Aplicação da árvore binária
3 - Estrutura da árvore binária
Dentro da árvore binária temos os seguintes tipos de estruturas:
- Árvore binária completa: é uma árvore onde todos os nós possuem dois filhos.
- Árvore binária completa ordenada: árvore onde além de todos os nós terem obrigatoriamente dois filhos, os mesmos são ordenados, seja alfabeticamente, numericamente, ...
- Árvore binária ordenada: é uma estrutura onde os nós não precisam ter dois filhos obrigatoriamente mas são ordenadas, conforme explicação anterior.
4 - Código
Abaixo vou colocar o código feito por mim na implementação de um sistema de manipulação da árvore. O mesmo conta com alguns menus para inserção, remoção, busca e impressão na árvore. O código está comentado e sobre as funções usadas falarei mais abaixo, juntamente com o raciocínio por trás do algoritmo.
#include;
#include;
#include; // uso do system("pause")
/*estrutura da arvore, com um campo de informacao e dois
campos inteiros, direita e esquerda*/
struct tree{
int numero;
struct tree *esq, *dir;
};
//definicao de "alias" da arvore, para melhor manuseio
typedef struct tree * ptrTree;
//variavel para a raiz da arvore
ptrTree raiz = NULL;
//declaracao de metodos utilizados no projeto
void Inserir(ptrTree*, int);
int Remover(ptrTree*, int);
ptrTree maior(ptrTree*);
void Ordem(ptrTree);
void preOrdem(ptrTree);
void posOrdem(ptrTree);
ptrTree Buscar(ptrTree, int);
int main(void){
char opcao;
int x, aux;
/*inicio do menu em console com as funcoes basicas de
inserir, excluir, visualizar e buscar elementos*/
do{
system("CLS");
printf("****************************\n");
printf("*A R V O R E B I N A R I A*\n");
printf("****************************\n\n");
printf("O que deseja fazer?\n");
printf("(I) - Inserir um novo no.\n");
printf("(R) - Remover um no.\n");
printf("(V) - Visualizar a arvore.\n");
printf("(B) - Buscar elemento.\n");
printf("(S) - Sair do programa.\nOpcao escolhida: ");
//funcao fflush para limpar teclas que estao no buffer do teclado
fflush(stdin);
scanf("%c", &opcao);
//conversao de letras maiusculas para minusculas
if(isupper(opcao)) opcao = tolower(opcao);
//case usado para escolha da opcao do menu
switch (opcao){
case 'i':
printf("Digite o valor que deseja inserir: ");
scanf("%d", &x);
Inserir(&raiz, x); // passado o endereco de memoria de raiz
printf("\nValor inserido com sucesso!\n");
system("PAUSE");
break;
case 'r':
printf("Digite o elemento que deseja remover: ");
scanf("%d", &x); // passado o endereco de memoria de raiz
aux = Remover(&raiz, x);
if(!aux)
printf("Item excluido com sucesso.\n");
else
printf("O numero nao existe na arvore.\n");
system("PAUSE");
break;
case 'v':
printf("Digite o modo que deseja visualizar a arvore.\n");
printf("(O) - Ordem\n");
printf("(E) - Pre-Ordem.\n");
printf("(S) - Pos-Ordem.\n");
char y;
fflush(stdin); // limpa buffer do teclado
scanf("%c", &y);
//conversao de maiuscula para minuscula
if(isupper(y)) y = tolower(y);
switch(y){
case 'o': printf("Elementos em Ordem...\n"); Ordem(raiz);
break;
case 'e': printf("Elementos em Pre-Ordem...\n"); preOrdem(raiz);
break;
case 's': printf("Elementos em Pos-Ordem...\n"); posOrdem(raiz);
break;
default: printf("Opcao inexistente.\n"); break;
}
system("\nPAUSE");
break;
case 'b':
printf("Digite o elemento que deseja procurar: ");
scanf("%d", &x);
//aqui e passado o valor do ponteiro raiz e nao seu endereco
aux = Buscar(raiz, x);
if(aux) printf("O elemento %d foi encontrado.\n", aux);
else printf("O elemento nao existe na arvore.\n");
system("\nPAUSE");
break;
case 's': break; default: printf("Opcao invalida. Digite uma das apresentadas.\n");
break;
}
}while(opcao != 's');
return 0;
}
/* essa funcao ira fazer de forma recursiva a inclusao...
ela ira procurar para ver se a arvore esta vazia.
se sim, ela cria um primeiro no, a raiz.
Caso contrario, ela ira, conforme os parametros,
passar o endereco de subarvore a direita ou esquerda
para a funcao e entao novamente trabalhara em cima desses valores.*/
void Inserir(ptrTree *p, int x){ //funcao recursiva se a raiz for vazia
if((*p) == NULL){
*p = (ptrTree)malloc(sizeof(struct tree));
(*p)->esq = NULL;
(*p)->dir = NULL;
(*p)->numero = x;
}else{
if(x < ((*p)->numero))
//funcao recursiva se o numero for menor do que o no pai
Inserir(&((*p)->esq), x);
else
//funcao recursiva se o numero for maior do que o no pai
Inserir(&((*p)->dir), x);
}
}
/*essa funcao analisa cinco possibilidades. Arvore vazia, remocao de
no sem subnos, remocao de no com subno esquerda, remocao de
no com subno direita e remocao de no com subnos direita e esquerda*/
int Remover(ptrTree *p, int x){
if(*p == NULL) // se arvore vazia, retorna 1
return 1;
else{
ptrTree aux = *p;
if((*p)->numero == x){ // achou o elemento
// aqui, quando se tem apenas o subno direita
if((*p)->esq == NULL){
*p = (*p)->dir;
free(aux);
}else
// aqui, quando se tem apenas o subno esquerda
if((*p)->dir == NULL){
*p = (*p)->esq;
free(aux);
}else{
/*aqui, quando possui os dois subnos. Chamada da funcao maior*/
aux = maior(&((*p)->dir));
(*p)->numero = aux->numero;
free(aux);
}
}else{
if(x < (*p)->numero)
return Remover(&((*p)->esq), x);
else
return Remover(&((*p)->dir), x);
}
return 0; // retorna 0 caso tenha conseguido remover o elemento
}
}
// funcao procura o maior subno esquerdo na arvore direita
ptrTree maior(ptrTree *p){
ptrTree aux = *p;
if(aux->esq == NULL){
*p = (*p)->dir;
return aux;
}
else{
return maior(&((*p)->esq));
}
}
/*mostra os elementos da arvore de forma ordenada, ou seja,
mostra os elementos da esquerda de forma recursiva,
depois a raiz e depois os elementos a direita */
void Ordem(ptrTree p){
if(p != NULL){
Ordem(p->esq);
printf("%d \t", p->numero);
Ordem(p->dir);
}
}
//o mesmo que acima, porem, com a ordem raiz, esquerda, direita
void preOrdem(ptrTree p){
if(p != NULL){
printf("%d \t", p->numero);
Ordem(p->esq);
Ordem(p->dir);
}
}
//o mesmo que acima, mas na ordem esquerda, direita, raiz
void posOrdem(ptrTree p){
if(p != NULL){
Ordem(p->esq);
Ordem(p->dir);
printf("%d \t", p->numero);
}
}
//procura um elemento na arvore e o retorna. caso nao ache, retorna 0
ptrTree Buscar(ptrTree p, int x){
if(p == NULL) return 0;
else{
if(p->numero == x) return p->numero;
else{
if(x < p->numero) return Buscar(p->esq, x);
else return Buscar(p->dir, x);
}
}
}
5 - Explicando as funções
Função INSERIR
A função inserir recebe como parâmetros a referência (ponteiro) de um nó e um inteiro, que é o conteúdo propriamente dito, da estrutura.
Após receber os parâmetros ela faz uma primeira verificação (IF...THEN) para saber se já existe um nó raiz e, caso não exista, o mesmo será criado e o valor inteiro informado será armazenado para esse nodo raiz. Caso contrário, ela fará uma nova chamada de si mesma (recursividade) e irá inserir o número a esquerda (se o valor do número for menor do que o valor do nó pai) ou a direita (se o valor do número for maior ou igual ao do pai).
Função REMOVER
A função remover verificará se a árvore está vazia e se estiver, retornará o valor 1. Caso tenha nodos, ele fará uma busca pelo valor selecionado para ser removido. Essa procura será recursiva. Será verificado se existe apenas o nó à esquerda e removê-lo caso seja o número procurado. Se houver apenas nó à direita, apenas o removerá caso seja o número procurado. Havendo dois nós, será feita a chamada da função maior(*ptrTree, int) para procurar o maior nó da esquerda do nó atual, para que o mesmo seja direcionado para cima e possa se tornar pai do nó que estava a direita. A imagem abaixo mostra o que acontecerá.
 |
| Remoção de nó da árvore binária com dois sub nós. |
Caso não seja achado o valor, será feita uma chamada da mesma função de forma recursiva para a direita e uma chamada recursiva da mesma função para a esquerda, repetindo todo o processo anterior. Caso não seja encontrado o valor, será retornado 1 para o programa, já que ele cairá na primeira verificação da função, que é o IF...THEN para saber se o nó é vazio.
Função MAIOR
Será usada para pegar o maior nodo à esquerda do nó atual, para que o mesmo assuma a posição de pai do nó que estava a direita. Função chamada pela função de remoção apenas e é usada no GIF mostrado na função de remoção.
Função ORDEM
Mostrará os valores, conforme o nome da função diz, em ordem. Ele irá percorrer de forma recursiva a parte esquerda da árvore, depois lerá o nó raiz e depois todo o lado direito, de forma recursiva.
Função PREORDEM
Ele lerá o nó raiz, depois irá percorrer de forma recursiva a parte esquerda da árvore e depois todo o lado direito, de forma recursiva.
Função POSORDEM
Ele irá percorrer de forma recursiva a parte esquerda da árvore, depois todo o lado direito, também de forma recursiva e depois lerá o nó raiz.
Função BUSCAR
Receberá o nó raiz e o valor que quer se buscar na árvore como parâmetros. Após isso, irá verificar se o valor é o mesmo do nó raiz e retorná-lo caso verdadeiro. Se for falso, irá fazer uma chamada para a mesma função ao lado esquerdo da árvore caso o valor procurado seja menor do que o do nó raiz e para o lado direito caso seja maior.
Conclusão
Assim caros leitores, terminamos mais um artigo sobre desenvolvimento. Um assunto que muita gente tem dúvida e deixa de lado quando é passado para aprender, por talvez não ter ficado muito bem explicado ou mesmo por medo de tentar entender, tendo visto que é algo que não é tão fácil de se aprender caso não seja bem explicado.
No mais, dúvidas sobre o assunto, perguntas, sugestões ou críticas por favor, não exitem em fazê-las aqui no blog mesmo ou então na página do Google Plus. Continuem acompanhando as matérias pelo feed, assinando o blog e também seguindo a nossa página no G+. Compartilhem o link e divulguem o blog pois quanto mais gente para debater sobre os assuntos melhor!
Até a próxima e Nerds Attack!
Nenhum comentário:
Postar um comentário