Neste post abordaremos as principais operações em uma Árvore Binária. O código abaixo conterá as seguintes operações:

-Impressão
-Inserção
-Remoção
-Altura

Vale ressaltar que todas as funções são chamadas passando "apenas" uma estrutura do tipo tAB (tipo Árvore Binária) ao invés de passar ponteiro ou alguma coisa do tipo, foi feito dessa maneira para abstrair, por exemplo, o ponteiro raiz. Quem for utilizar o código não precisa saber que você tem um ponteiro raiz e muito menos qual é o nome dele, fazendo dessa maneira facilitamos a vida do usuário e a nossa também quando precisarmos dessas operações em Árvores não necessitaremos lembrar como que foi feita a implementação.

Sem mais palavras, vamos as operações em C++:

//Autor: Filipe Areias Névola
//Ano: 2007
//Programa: Operações em Árvore Binária
//Licensa: Você pode usar e alterar, mas deve manter o Autor

#include <iostream>
using namespace std;

//estrutura para representar um Nó,
//onde k é a chave
//l é o ponteiro para o filho esquerdo
//r é o ponteiro para o filho direito
struct tABNo{
    int k;
    tABNo *l;
    tABNo *r;
    tABNo():l(NULL),r(NULL){} //inicializando os ponteiros
};

//estrutura para representar uma Árvore,
//onde ptr é o ponteiro da raiz da árvore
struct tAB{
    tABNo *ptr;
};

//imprime a árvore em ordem
void imprimirpt(tABNo *pt){
    if(pt!=NULL){
        imprimirpt(pt->l);
        cout<<" "<<pt->k<<" ";
        imprimirpt(pt->r);
    }
}

//chama a imprimirpt passando a raiz
//Porque passar a raiz somente aqui e não chamar direto?
//Para abstrair, ou seja, o usuário não precisa saber que existe uma raiz
//ele necessita apenas saber que tem uma árvore (todas as funções estão dessa maneira)
void imprimir(tAB F){
    imprimirpt(F.ptr);
}

//insere em x a altura da árvore (está recebendo por referência)
void alturapt(tABNo *pt,int &x){
    int hr,hl;
    if(pt!=NULL){
        x++;
        hr=x;
        hl=x;
        alturapt(pt->r,hr);
        alturapt(pt->l,hl);
        if(hr>x)
            x=hr;
        if(hl>x)
            x=hl;
    }
}

//chama alturapt passando a raiz e irá retornar a altura (um inteiro)
int altura(tAB T){
    int h=0;
    alturapt(T.ptr,h);
    return h;
}

//insere elem na árvore
bool inserirpt(tABNo *&pt,int elem){
   if(pt!=NULL){
        if(elem>=pt->k){
            return inserirpt(pt->r,elem);
        }
        else{
            return inserirpt(pt->l,elem);
        }
    }
    else{
        pt=new tABNo;
        if(pt==NULL)
            return false;
        pt->k=elem;
        pt->r=pt->l=NULL;
        return true;
    }
}

//chama inserirpt passando a raiz e o elemento
void inserir(tAB &F,int elem){
   inserirpt(F.ptr,elem);
}

//encontra um substituto para o nó removido
int substituto(tABNo *pt){
    tABNo *paux,**ppt;
    int subst;
    if(pt->l!=NULL){
        ppt=&pt->l;
        while((*ppt)->r!=NULL)
            ppt=&(*ppt)->r;
        subst=(*ppt)->k;
        paux=*ppt;
        *ppt=(*ppt)->l;

    }
    else{
        ppt=&pt->r;
        while((*ppt)->l!=NULL)
            ppt=&(*ppt)->l;
        subst=(*ppt)->k;
        paux=*ppt;
        *ppt=(*ppt)->r;

    }
    delete []paux;
    return subst;
}

//remove x de uma árvore
bool removerpt(tABNo **pt,int x){
    if((*pt)!=NULL){
        if(x>(*pt)->k)
            return removerpt(&(*pt)->r,x);
        if(x<(*pt)->k)
            return removerpt(&(*pt)->l,x);
        if((*pt)->r==NULL && (*pt)->l==NULL){
            delete []pt;
            *pt=NULL;
        }
        else
            (*pt)->k=substituto(*pt);
        return true;
    }
    return false;
}

//chama removerpt passando a raiz e o x (elemento a ser removido)
bool remover(tAB &T,int x){
    return removerpt(&T.ptr,x);
}

//alguns testes no código
int main(){
    tAB arvore;
    int x,n;
    arvore.ptr=NULL;
    cout<<"\tEntre com o numero de elementos para serem";
    cout<<"\n\tinseridos na arvore binaria de busca: ";
    cin>>n;
    for(int i=0;i<n;++i){ 
        cout<<"\n\tEntre com um elemento: ";
        cin>>x;
        inserir(arvore,x);
    }
    cout<<"\n\tOs numeros ordenados sao: \n\n\t";
    imprimir(arvore);
    cout<<"\nAltura> "<<altura(arvore)<<"\n";
    remover(arvore,20);
    imprimir(arvore);
    cout<<"\n\n";
    remover(arvore,3);
    imprimir(arvore);

}

Não concorda?  Comente, opine e demonstre seu conhecimento!