Dentre as estruturas de dados dinâmicas, as árvores binárias estão entre as mais conhecidas, sendo uma estrutura muito eficiente para organização e busca de dados.
Sua principal característica, que justifica o nome “binária”, advêm do fato de que cada nó pode possuir no máximo dois filhos, um à esquerda e um à direita.
A escolha pela inserção à direita ou à esquerda se dá por um valor chave. Valores menores que o valor chave do nó raiz serão inseridos à esquerda, enquanto que valores maiores serão inseridos à direita. Ao final desse processo, temos uma estrutura que armazena os dados de forma ordenada, como apresentado na figura a seguir.
Na videoaula a seguir apresento de forma mais detalhada como funciona uma Árvore Binária.
Inserção de elementos
O principal nó de uma árvore binária é o nó raiz. É por este nó que iniciamos nosso caminhamento na árvore. No início, nossa árvore está vazia, ou seja, o nó raiz é nulo. Ao fazer a primeira inserção, nosso nó raiz então é criado.
A partir desse momento, todo novo nó a ser inserido ficará à esquerda (se for menor) ou à direita (se for maior) do nó raiz.
As operações de inserção, busca e remoção podem ser implementadas de diferentes formas. Na videoaula a seguir apresento uma primeira versão de como inserir elementos em uma árvore binária.
Na videoaula a seguir apresento uma segunda versão para a inserção de novos elementos, mais sucinta que a primeira versão.
Tamanho
As vezes pode ser necessário saber qual o tamanho da árvore, em outras palavras, quantos elementos a árvore possui. Na videoaula a seguir você aprenderá como fazer isso.
Busca
Precisamos também saber como realizar buscas em uma árvore binário, o que é apresentado a seguir. A principal característica aqui é que, a cada comparação, aproximadamente metade da árvore é eliminada, uma vez que apenas percorreremos a subárvore à esquerda ou à direita.
Remoção
Por fim, apresento a remoção de nós em árvores binárias. Esta é apresentada em três partes:
Remoção de nós folhas (nós sem filhos)
Remoção de nós com apenas um filho
Remoção de nós com dois filhos
Código
A seguir apresento todo o código escrito nas videoaulas.
#include <stdio.h>
#include <stdlib.h>
// estrututa nó
typedef struct no {
int conteudo;
struct no *esquerda, *direita;
} No;
// estrutura árvore com um ponteiro para um nó
typedef struct {
No *raiz;
int tam;
} ArvB;
/* Assinatura do procedimento inserirDireita()
necessário pois é utilizado no procedimento inserirEsquerda,
antes deste ser criado
*/
void inserirDireita(No *no, int valor);
// procedimento para inserir um elemento na subárvore esquerda
void inserirEsquerda(No *no, int valor) {
if(no->esquerda == NULL) {
No *novo = (No*)malloc(sizeof(No));
novo->conteudo = valor;
novo->esquerda = NULL;
novo->direita = NULL;
no->esquerda = novo;
} else {
if(valor < no->esquerda->conteudo)
inserirEsquerda(no->esquerda, valor);
if(valor > no->esquerda->conteudo)
inserirDireita(no->esquerda, valor);
}
}
// procedimento para inserir um elemento na subárvore direita
void inserirDireita(No *no, int valor) {
if(no->direita == NULL) {
No *novo = (No*)malloc(sizeof(No));
novo->conteudo = valor;
novo->esquerda = NULL;
novo->direita = NULL;
no->direita = novo;
} else {
if(valor > no->direita->conteudo)
inserirDireita(no->direita, valor);
if(valor < no->direita->conteudo)
inserirEsquerda(no->direita, valor);
}
}
/*
Procedimento para inserir um elemento na árvore
faz uso dos dois procedimentos anteriores,
inserindo à esquerda ou à direita
*/
void inserir(ArvB *arv, int valor) {
if(arv->raiz == NULL) {
No *novo = (No*)malloc(sizeof(No));
novo->conteudo = valor;
novo->esquerda = NULL;
novo->direita = NULL;
arv->raiz = novo;
} else {
if(valor < arv->raiz->conteudo)
inserirEsquerda(arv->raiz, valor);
if(valor > arv->raiz->conteudo)
inserirDireita(arv->raiz, valor);
}
}
/* nova versão para a inserção, mais resumida
perceba que agora é uma função
*/
No* inserirNovaVersao(No *raiz, int valor) {
if(raiz == NULL) {
No *novo = (No*)malloc(sizeof(No));
novo->conteudo = valor;
novo->esquerda = NULL;
novo->direita = NULL;
return novo;
} else {
if(valor < raiz->conteudo)
raiz->esquerda = inserirNovaVersao(raiz->esquerda, valor);
if(valor > raiz->conteudo)
raiz->direita = inserirNovaVersao(raiz->direita, valor);
return raiz;
}
}
// função que retorna o tamanho de uma árvore
int tamanho(No *raiz) {
if(raiz == NULL)
return 0;
else
return 1 + tamanho(raiz->esquerda) + tamanho(raiz->direita);
}
// função para buscar um elemento na árvore
int buscar(No *raiz, int chave) {
if(raiz == NULL) {
return 0;
} else {
if(raiz->conteudo == chave)
return 1;
else {
if(chave < raiz->conteudo)
return buscar(raiz->esquerda, chave);
else
return buscar(raiz->direita, chave);
}
}
}
/* faz a impressão da árvore em ordem crescente
esquerda - raiz - direita
*/
void imprimir(No *raiz) {
if(raiz != NULL) {
imprimir(raiz->esquerda);
printf("%d ", raiz->conteudo);
imprimir(raiz->direita);
}
}
// função para a remoção de um nó
No* remover(No *raiz, int chave) {
if(raiz == NULL) {
printf("Valor nao encontrado!\n");
return NULL;
} else {
if(raiz->conteudo == chave) {
// remove nós folhas (nós sem filhos)
if(raiz->esquerda == NULL && raiz->direita == NULL) {
free(raiz);
return NULL;
}
else{
// remover nós que possuem apenas 1 filho
if(raiz->esquerda == NULL || raiz->direita == NULL){
No *aux;
if(raiz->esquerda != NULL)
aux = raiz->esquerda;
else
aux = raiz->direita;
free(raiz);
return aux;
}
else{
No *aux = raiz->esquerda;
while(aux->direita != NULL)
aux = aux->direita;
raiz->conteudo = aux->conteudo;
aux->conteudo = chave;
raiz->esquerda = remover(raiz->esquerda, chave);
return raiz;
}
}
} else {
if(chave < raiz->conteudo)
raiz->esquerda = remover(raiz->esquerda, chave);
else
raiz->direita = remover(raiz->direita, chave);
return raiz;
}
}
}
// ffunção principal
int main() {
int op, valor;
ArvB arv;
arv.raiz = NULL;
No *raiz = NULL;
do {
printf("\n0 - sair\n1 - inserir\n2 - imprimir\n3 - Buscar\n4 - Remover\n");
scanf("%d", &op);
switch(op) {
case 0:
printf("\nSaindo...\n");
break;
case 1:
printf("Digite um valor: ");
scanf("%d", &valor);
raiz = inserirNovaVersao(raiz, valor);// não precisa da estrutura ArvB
//inserir(&arv, valor);// para utilizar esta inserção, comente a anterior
break;
case 2:
printf("\nImpressao da arvore binaria:\n");
imprimir(raiz);
printf("\n");
printf("Tamanho: %d\n", tamanho(raiz));
break;
case 3:
printf("Qual valor deseja buscar? ");
scanf("%d", &valor);
printf("Resultado da busca: %d\n", buscar(raiz, valor));
break;
case 4:
printf("Digite um valor a ser removido: ");
scanf("%d", &valor);
raiz = remover(raiz, valor);
break;
default:
printf("\nOpcao invalida...\n");
}
} while(op != 0);
}
Se ficou alguma dúvida utilize os espaços para comentários.
Abraços e até o próximo.
Muito obrigada, me ajudou muito. Antes de encontrar esse site eu não estava entendendo nada, agora entendi tudo direitinho.