No post passado sobre árvores, foram explanados os conceitos que cercam uma árvore computacional, principalmente as árvores binárias e AVL.
Neste post pretendo explicar o código de uma árvore binária de elementos inteiros, e principalmente as maneiras de listar os elementos de uma árvore (pré-ordem, in-ordem, pós-ordem).
Vamos ao código:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct Item
{
int numero;
Item *esquerda;
Item *direita;
};
bool Inserir(Item **itemAtual, int valor)
{
Item *novo;// -> Aloca memória para o novo item
novo = (Item *)malloc(sizeof(Item));// -> Checa se foi alocado memória corretamente.
if (novo != NULL)
{
// -> Define e inicializa os valores.
novo->numero = valor;
novo->esquerda = NULL;
novo->direita = NULL;// -> Se o nó for nulo então o item alocado é colocado nele.
if(*itemAtual == NULL)
{
*itemAtual = novo;
}
else
{
if(valor < (*itemAtual)->numero)
{
// -> valor menor que o atual vai para a esquerda.
Inserir(&(*itemAtual)->esquerda, valor);
}
else
{
// -> valor maior que o atual vai para a direita.
Inserir(&(*itemAtual)->direita, valor);
}
}
return true;
}
else
{
return false;
}
}
Item** Procurar(Item **itemAtual, int valor)
{
if(*itemAtual == NULL)
{
return NULL;
}
else if((*itemAtual)->numero == valor)
{
return itemAtual;
}
else if(valor < (*itemAtual)->numero)
{
return Procurar(&(*itemAtual)->esquerda, valor);
}
else
{
return Procurar(&(*itemAtual)->direita, valor);
}
}bool Remover(Item **itemAtual, int valor)
{
Item **itemProcurado = Procurar(itemAtual, valor);if(itemProcurado == NULL)
{
printf("\nItem não encontrado!\n");
return false;
}Item *temp = *itemProcurado;
if((*itemProcurado)->direita == NULL)
{
// -> Não tem filho a direita.
(*itemProcurado) = (*itemProcurado)->esquerda;
}
else if((*itemProcurado)->esquerda == NULL)
{
// -> Não tem filho a esquerda.
(*itemProcurado) = (*itemProcurado)->direita;
}
else
{
// -> Tem os dois filhos.
Item *anterior = NULL;
temp = (*itemProcurado)->esquerda;while (temp->direita != NULL)
{
anterior = temp;
temp = temp->direita;
}(*itemProcurado)->numero = temp->numero;
if(anterior == NULL)
{
(*itemProcurado)->esquerda = temp->esquerda;
}
else
{
(*itemProcurado)->direita = temp->esquerda;
}
}free(temp);
return true;
}
void ListarPreOrdem(Item *itemAtual)
{
if (itemAtual != NULL)
{
printf("%i; ", itemAtual->numero);
ListarPreOrdem(itemAtual->esquerda);
ListarPreOrdem(itemAtual->direita);
}
}void ListarInOrdem(Item *itemAtual)
{
if (itemAtual != NULL)
{
ListarInOrdem(itemAtual->esquerda);
printf("%i; ", itemAtual->numero);
ListarInOrdem(itemAtual->direita);
}
}void ListarPosOrdem(Item *itemAtual)
{
if (itemAtual != NULL)
{
ListarPosOrdem(itemAtual->esquerda);
ListarPosOrdem(itemAtual->direita);
printf("%i; ", itemAtual->numero);
}
}void Listar(Item *itemAtual)
{
printf( "Listando... \n\n");
ListarPreOrdem(itemAtual);
printf("\n\n");
}
void Menu()
{
printf( "Digite a sua escolha: \n"
" 1 para inserir um elemento na arvore \n"
" 2 para remover um elemento da arvore \n"
" 3 para finalizar \n"
"? ");
}void main()
{
Item *raiz = NULL;
int opcao;
int numero;Menu();
scanf("%i", &opcao);while (opcao != 3)
{switch (opcao)
{
case 1:
printf( "Digite um numero: ");
scanf("\n%i", &numero);Inserir(&raiz, numero);
Listar(raiz);
break;
case 2:
printf( " Digite o numero a ser removido: ");
scanf( "\n%i", &numero);
Remover(&raiz, numero);
Listar(raiz);break;
default:
printf( "Escolha invalida.\n\n");
Menu();
break;
}scanf("%i", &opcao);
}
printf("Fim do programa.\n");
}
Resultado:
Começando pela struct Item: Ela contém o elemento inteiro que será armazenado, e um ponteiro “para a esquerda” e outro “para a direita”. Lembrando que, conceitualmente, uma árvore binária tem os elementos menores (que o elemento atual) armazenados a esquerda do elemento atual, e os maiores que o elemento atual à direita (do elemento atual).
Inserir: Basicamente temos de seguir a regra para saber se o elemento que esta sendo inserido é maior ou menor que o atual. O atual começa pela raiz da árvore e se estende pelos filhos, até que se encontre um nó nulo. Imagine que temos uma árvore que só tem um elemento, o número 5. Esse elemento será a raiz, e ao inserirmos um número 3, por ele ser menor, terá de ser inserido no ponteiro da “esquerda”. ao inserirmos o elemento 4, ele irá verificar a raiz, sendo menor que ela, o número 4 terá de ir para a “esquerda” e encontrará o elemento 3. 4 é maior que o 3 ele e terá que ficar no ponteiro da “direita” de 3! Para isso é alocado um novo elemento, e é verificado se o item atual é nulo. Se for, ele é referenciado. Se não é verificado com o número do Item atual se o item atual terá de ser o que está a esquerda ou a direita do nó.
Procurar: Faz um processo similar ao do Inserir. Se o elemento atual for nulo, quer dizer que o elemento procurado não foi encontrado! Se o número for igual ao procurado então a referencia para o Item é retornada. Se o elemento for maior do que o atual, devemos ir para a direita, caso contrário: esquerda neles! Usaremos para encontrar o nó que será removido.
Remover: Essa função é um pouco crítica, pois ao removermos um nó, temos que manter seus filhos vinculados na árvore. Após encontrar o elemento que será removido, verificamos se há filhos maiores (à direita). Se o elemento removido não tiver filhos à direita, o nó da esquerda é vinculado ao ponteiro de seu pai. O processo inverso, com a esquerda, também é feito caso tenha filhos à direita. Se o elemento tiver filho à esquerda e à direita, então é localizado o maior elemento (à direita) para substituí-lo. A última linha da função libera a memória do nó removido.
As listagens eu vou explicar com imagens:
Nas listagens, basicamente o que se muda é onde imprimimos o elemento. Lembrando que as funções são recursivas.
Só para fixar melhor o conceito das “ordens”, para somarmos o número 2 no número 3, teríamos a seguinte notação:
- Pré-Ordem: + 2 2
- In-Ordem: 2 + 2
- Pós-Ordem: 2 2 +
Agora vamos à parte divertida da coisa, exercícios:
- Fazer uma árvore para armazenar alunos (Nome, RA e Ano de Nascimento). O Índice da árvore deve ser baseado no ano do nascimento do aluno. Na listagem o usuário deve escolher qual ordem listar!
Boa sorte, e continuarei falando mais sobre árvores em outro post! 
0 comentários:
Postar um comentário