O objetivo é falar da forma mais clara e resumida sobre árvores binárias de busca, e com isso auxiliar outros aspirantes a programadores (assim com eu) a conseguirem dar mais um passo nessa difícil jornada.

Perceba que a definição é recursiva e, devido a isso, muitas operações sobre árvores binárias utilizam recursão. É o tipo de árvore mais utilizado na computação. A principal utilização de árvores binárias são as árvores de busca binária.

Uma grande vantagem de uma árvore binária é que ela propicia pesquisas muito rápidas.

Grande vantagem: flexibilidade e eficiência quando usadas em programas de gerenciamento de banco de dados.

O código que utilizo como exemplo apenas captura as informações fornecidas pelo usuário e as armazena numa árvore binária e na sequência percorre a árvore das três formas possíveis exibindo os valores armazenados.

Cada árvore possui:

• Raiz ou nó e várias subárvores
• As subárvores também são um árvore
• Os nós que não possuem nenhum filho, são chamados de folha
• O grau de uma árvore  diz respeito ao número de máximo de subárvore em cada nós da árvore
• A altura ou tamanho da árvore diz respeito a quantidade de níveis da árvore

Numa árvore binária cada nó tem no máximo 2 filhos

Em cada nó temos a informação que será a raiz e dois ponteiros, um para o filho esquerdo e outro para o filho direito

A implementação de uma árvore binária é baseado no conceito de listas encadeadas.

Uma árvore binária com raiz R é uma árvore binária de busca (ABB) se:

1. Se a chave de cada nó da subárvore a esquerda de R é menor do que a chave do nó R;
2. A chave de cada nó da subárvore a direita for maior do que a chave do nó R;
3. As subárvores esquerda e direita também devem ser abb's.

Etapas de uma implementação:

   a. Uma struct que será o molde da nossa árvore

   b. Criar um ponteiro do tipo desta struct recém criada e uma variável do tipo inteiro que armazenará a quantidade de elementos inseridos na árvore (devem ser variáveis globais)

   c. Um método construtor (onde o ponteiro receberá NULL e o contador receberá zero)

   d. Método destrutor (devemos liberar a memória alocada)

   e. Método que verifica se abb está vazia (essa condição é satisfeita quando a raiz apontar para NULL)

   f. Método que verifica a quantidade de elementos inseridos

   g. Método de inserção

   h. Método de pesquisa

   i. Método de busca:
      i. Em ordem:subarvore esquerda, raiz, subarvore direita
      ii. Pré-ordem: raiz, subarvore esquerda, subarvore direita
      iii. Pós-ordem: subarvore esquerda, subarvore direita, raiz

   j. Método de exclusão

Aguardo sugestões.

• Download 5665.main.cpp
• Enviar nova versão

Esconder código-fonte

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

struct arvore{
    char item;
    arvore *esq,*dir;
};

arvore *Raiz;
int contador;

void arvore_Construtor(){
    Raiz=NULL;
    contador=0;
}

void arvore_Destrutor(arvore *&Raiz){
    if(Raiz!=NULL){
        arvore_Destrutor(Raiz->esq);
        arvore_Destrutor(Raiz->dir);
        free(Raiz);
        Raiz=NULL;
    }
}

bool arvore_Vazia(){
    return Raiz==NULL;
}

int arvore_Tamanho(){
    return contador;
}

bool arvore_Inserir(char letra, arvore *&Raiz){
    if(Raiz==NULL){
        if((Raiz=(arvore *) malloc(sizeof(arvore)))==NULL)
            return false;
        else{
            Raiz->item=letra;
            Raiz->esq=Raiz->dir=NULL;
            contador++;
            return true;
        }
    }
    else{
        if(letra<Raiz->item)
            return arvore_Inserir(letra,Raiz->esq);
        else{
            if(letra>Raiz->item)
                return arvore_Inserir(letra,Raiz->dir);
            else
                return false;//letra já existe na árvore
        }
    }
}

//percorre a árvore
void arvore_Busca_em_Ordem(arvore *&Raiz){
    if(Raiz!=NULL){
        arvore_Busca_em_Ordem(Raiz->esq);
        printf(" %c",Raiz->item);
        arvore_Busca_em_Ordem(Raiz->dir);
    }
}

//percorre a árvore
void arvore_Busca_pre_Ordem(arvore *&Raiz){
    if(Raiz!=NULL){
        printf(" %c",Raiz->item);
        arvore_Busca_pre_Ordem(Raiz->esq);
        arvore_Busca_pre_Ordem(Raiz->dir);
    }
}

//percorre a árvore
void arvore_Busca_pos_Ordem(arvore *&Raiz){
    if(Raiz!=NULL){
        arvore_Busca_pos_Ordem(Raiz->esq);
        arvore_Busca_pos_Ordem(Raiz->dir);
        printf(" %c",Raiz->item);
    }
}

int main(){
    char x,opcao;

    arvore_Construtor();

    do{
        printf("\nInforme a letra: ");
        setbuf(stdin,NULL);
        scanf("%c",&x);

        arvore_Inserir(x,Raiz);

        printf("\nMais dados? S/N:  ");
        setbuf(stdin,NULL);
        scanf("%c",&opcao);
    }while(toupper(opcao)!='N');

//  tamanho da árvore
    printf("\nQuantidade de elementos: %d\n",contador);

//   impressão em ordem
    printf("\nArvore em ordem:\n");
    arvore_Busca_em_Ordem(Raiz);
    printf("\n\n");

//  impressão em pré-ordem
    printf("Arvore em pre-ordem:\n");
    arvore_Busca_pre_Ordem(Raiz);
    printf("\n\n");

//  impressão em pós-ordem
    printf("Arvore em pos-ordem:\n");
    arvore_Busca_pos_Ordem(Raiz);
    printf("\n\n");

//  devolvendo memóra alocada ao sistema operacional
    arvore_Destrutor(Raiz);

    return 0;
}

CPU e memória em C no GNU/Linux

Passando parâmetros com getopt

Calculadora com interface GTK

Cálculo do dia da semana

MeikeNeime - Programa gerador de nomes aleatórios