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.