Árvores Binárias em C: Guia Completo de Implementação

Árvores Binárias em C

Guia prático e estruturado para manipulação e implementação de árvores binárias de busca em linguagem C.

Estrutura do Nó (Struct)

struct No{
    int numero;
    struct No *esquerda;
    struct No *direita;
};
typedef struct No No;

Inicialização da Árvore

void criarArvore(No **pRaiz){
    *pRaiz = NULL;
}

Inserção de Elementos

void inserir(No **pRaiz, int numero){
    if(*pRaiz == NULL){
        *pRaiz = (No *) malloc(sizeof(No));
        (*pRaiz)->esquerda = NULL;
        (*pRaiz)->direita = NULL;
        (*pRaiz)->numero = numero;
    }else{
        if(numero < (*pRaiz)->numero)
            inserir(&(*pRaiz)->esquerda, numero);
        if(numero > (*pRaiz)->numero)
            inserir(&(*pRaiz)->direita, numero);
    }
}

Remoção de Elementos

No *MaiorDireita(No **no){
    if((*no)->direita != NULL) 
       return MaiorDireita(&(*no)->direita);
    else{
       No *aux = *no;
       if((*no)->esquerda != NULL) // se não houver essa verificação, esse nó vai perder todos os seus filhos da esquerda!
          *no = (*no)->esquerda;
       else
          *no = NULL;
       return aux;
    }
}

No *MenorEsquerda(No **no){
    if((*no)->esquerda != NULL) 
       return MenorEsquerda(&(*no)->esquerda);
    else{
       No *aux = *no; 
       if((*no)->direita != NULL) // se não houver essa verificação, esse nó vai perder todos os seus filhos da direita!
          *no = (*no)->direita;
       else
          *no = NULL;
       return aux;
    }
}

void remover(No **pRaiz, int numero){
    if(*pRaiz == NULL){   // esta verificação serve para caso o número não exista na árvore.
        printf("Número não existe na árvore!");
        getch();
        return;
    }
    if(numero < (*pRaiz)->numero)
        remover(&(*pRaiz)->esquerda, numero);
    else 
        if(numero > (*pRaiz)->numero)
            remover(&(*pRaiz)->direita, numero);
        else{    // se não é menor nem maior, logo, é o número que estou procurando! :)
            No *pAux = *pRaiz;     // quem programar no Embarcadero vai ter que declarar o pAux no início do void! :[
            if (((*pRaiz)->esquerda == NULL) && ((*pRaiz)->direita == NULL)){         // se não houver filhos...
                free(pAux);
                (*pRaiz) = NULL; 
            }
            else{     // só tem o filho da direita
                if ((*pRaiz)->esquerda == NULL){
                    (*pRaiz) = (*pRaiz)->direita;
                    pAux->direita = NULL;
                    free(pAux); pAux = NULL;
                }
                else{            // só tem filho da esquerda
                    if ((*pRaiz)->direita == NULL){
                        (*pRaiz) = (*pRaiz)->esquerda;
                        pAux->esquerda = NULL;
                        free(pAux); pAux = NULL;
                    }
                    else{       // Escolhi fazer o maior filho direito da subárvore esquerda.
                        pAux = MaiorDireita(&(*pRaiz)->esquerda); // se você quiser usar o menor da esquerda, só o que mudaria seria isso:
                        pAux->esquerda = (*pRaiz)->esquerda;          //         pAux = MenorEsquerda(&(*pRaiz)->direita);
                        pAux->direita = (*pRaiz)->direita;
                        (*pRaiz)->esquerda = (*pRaiz)->direita = NULL;
                        free((*pRaiz));  *pRaiz = pAux;  pAux = NULL;   
                    }
                }
            }
        }
}

Percurso em Ordem

void exibirEmOrdem(No *pRaiz){
    if(pRaiz != NULL){
        exibirEmOrdem(pRaiz->esquerda);
        printf("\n%i", pRaiz->numero);
        exibirEmOrdem(pRaiz->direita);
    }
}

Percurso em Pré-Ordem

void exibirPreOrdem(No *pRaiz){
    if(pRaiz != NULL){
        printf("\n%i", pRaiz->numero);
        exibirPreOrdem(pRaiz->esquerda);
        exibirPreOrdem(pRaiz->direita);
    }
}

Percurso em Pós-Ordem

void exibirPosOrdem(No *pRaiz){
    if(pRaiz != NULL){
        exibirPosOrdem(pRaiz->esquerda);
        exibirPosOrdem(pRaiz->direita);
        printf("\n%i", pRaiz->numero);
    }
}

Contagem de Nós

int contarNos(No *pRaiz){
    if(pRaiz == NULL)
        return 0;
    else
        return 1 + contarNos(pRaiz->esquerda) + contarNos(pRaiz->direita);
}

Contagem de Folhas

int contarFolhas(No *pRaiz){
    if(pRaiz == NULL)
        return 0;
    if(pRaiz->esquerda == NULL && pRaiz->direita == NULL)
        return 1;
    return contarFolhas(pRaiz->esquerda) + contarFolhas(pRaiz->direita);
}

Altura da Árvore

int maior(int a, int b){
    if(a > b)
        return a;
    else
        return b;
}

int altura(No *pRaiz){
    if((pRaiz == NULL) || (pRaiz->esquerda == NULL && pRaiz->direita == NULL))
        return 0;
    else
        return 1 + maior(altura(pRaiz->esquerda), altura(pRaiz->direita));
}