Árvore Binária de Busca em C++: Implementação e Travessias

Árvore Binária de Busca em C++

Código-fonte de uma árvore binária de busca implementada em C++, com funções de inserção, remoção, contagem e exibição em diferentes ordens de travessia.

#include <iostream>
using namespace std;

struct Elemento
{
    int Valor;
    float Preco;
    char Nome[30];
};

struct Nodo
{
    //int Valor;
    Elemento Conteudo;
    Nodo * Esquerda;
    Nodo * Direita;
};

typedef Nodo * Arvore;
typedef Nodo * Ponteiro;

Arvore CriarArvore()
{
    return NULL;
}

bool ArvoreVazia(Arvore arv)
{
    return arv == NULL;
}

void LiberarArvore(Arvore &arv)
{
    if(!ArvoreVazia(arv))
    {
        LiberarArvore(arv->Esquerda);
        LiberarArvore(arv->Direita);
        delete(arv);
        arv = NULL;
    }
}

void ExibirArvore(Arvore arv)
{
    if(!ArvoreVazia(arv))
    {
        cout << "\nValor: " << arv->Conteudo.Valor;
        ExibirArvore(arv->Esquerda);
        ExibirArvore(arv->Direita);
    }
}

void ExibirPreOrdem(Arvore arv)
{
    if(!ArvoreVazia(arv))
    {
        cout << "\nValor: " << arv->Conteudo.Valor;
        ExibirPreOrdem(arv->Esquerda);
        ExibirPreOrdem(arv->Direita);
    }
}

void ExibirOrdem(Arvore arv)
{
    if(!ArvoreVazia(arv))
    {
        ExibirOrdem(arv->Esquerda);
        cout << "\nID: " << arv->Conteudo.Valor;
        cout << "\nNome: " << arv->Conteudo.Nome;
        cout << "\nPreco " << arv->Conteudo.Preco;
        ExibirOrdem(arv->Direita);
    }
}

void ExibirPosOrdem(Arvore arv)
{
    if(!ArvoreVazia(arv))
    {
        ExibirPosOrdem(arv->Esquerda);
        ExibirPosOrdem(arv->Direita);
        cout << "\nValor: " << arv->Conteudo.Valor;
    }
}

void ExibirInverso(Arvore arv)
{
    if(!ArvoreVazia(arv))
    {
        ExibirInverso(arv->Direita);
        cout << "\nValor: " << arv->Conteudo.Valor;
        ExibirInverso(arv->Esquerda);
    }
}

int ContarArvore(Arvore arv)
{
    int cont = 0;
    if(!ArvoreVazia(arv))
    {
        cont++;
        cont = cont + ContarArvore(arv->Esquerda);
        cont = cont + ContarArvore(arv->Direita);
    }
    return cont;
}

void Inserir(Arvore &arv, Elemento e)
{
    if(ArvoreVazia(arv))
    {
        arv = new(Nodo);
        arv->Conteudo.Valor = e.Valor;
        arv->Esquerda = NULL;
        arv->Direita = NULL;
    }
    else
    {
        if(e.Valor < arv->Conteudo.Valor)
        {
            Inserir(arv->Esquerda, e);
        }
        else if(e.Valor > arv->Conteudo.Valor)
        {
            Inserir(arv->Direita, e);
        }
    }
}

Nodo * Localizar(Arvore &arv, Elemento e)
{
    Nodo * pont = NULL;
    if(!ArvoreVazia(arv))
    {
        if(e.Valor == arv->Conteudo.Valor)
            pont = arv;
        if(pont == NULL)
        {
            pont = Localizar(arv->Esquerda, e);
        }
        if(pont == NULL)
            pont = Localizar(arv->Direita, e);
    }
    return pont;
}

Arvore minimo(Arvore T)
{
    // procura o nó com valor mínimo
    if(ArvoreVazia(T))
    {
        return NULL;
    }
    else
    {
        if(ArvoreVazia(T->Esquerda))
        {
            return T;
        }
        else
        {
            return minimo(T->Esquerda);
        }
    }
}

void Remover(Arvore &Arv, int valor)
{
    Arvore aux;
    if(!ArvoreVazia(Arv))
    {
        if(valor < Arv->Conteudo.Valor)
        {
            Remover(Arv->Esquerda, valor);
        }
        else
        {
            if(valor > Arv->Conteudo.Valor)
            {
                Remover(Arv->Direita, valor);
            }
            else
            {
                if(!ArvoreVazia(Arv->Esquerda) && !ArvoreVazia(Arv->Direita))
                {
                    aux = minimo(Arv->Direita);
                    Arv->Conteudo = aux->Conteudo;
                    Remover(Arv->Direita, Arv->Conteudo.Valor);
                }
                else
                {
                    aux = Arv;
                    if(ArvoreVazia(Arv->Esquerda))
                    {
                        Arv = Arv->Direita;
                    }
                    else
                    {
                        Arv = Arv->Esquerda;
                    }
                    delete aux;
                }
            }
        }
    }
}

Tarefas Propostas

1. Criar uma função para verificar se um elemento já está na árvore.
2. Criar uma função para verificar se um elemento é folha.
3. Criar uma função capaz de receber duas árvores como parâmetros e alocar a segunda árvore no local adequado da primeira árvore.
4. Criar uma função que recebe uma árvore e um elemento, procura esse elemento na árvore e remove o nodo correspondente.

Construir Funções de Travessia

• Exibir Pré-Ordem: R-E-D
• Exibir em Ordem: E-R-D
• Exibir Pós-Ordem: E-D-R
• Exibir Inverso (decrescente): D-R-E