Você está visualizando atualmente Árvore Binária

Árvore Binária

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.

Representação visual de uma Árvore Binária

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.

Este post tem um comentário

  1. Renata Ribeiro

    Muito obrigada, me ajudou muito. Antes de encontrar esse site eu não estava entendendo nada, agora entendi tudo direitinho.

Deixe um comentário

treze + cinco =

Wagner Gaspar

Capixaba de São Gabriel da Palha, Espírito Santo. Bacharel em Ciência da Computação pela Universidade Federal do Amazonas e mestre em informática pela Universidade Federal do Espírito Santo.