Dando continuidade ao nosso Curso de Programação com a linguagem C, vamos aprender nesta aula como inserir em uma estrutura do tipo árvore binária de forma um pouco mais eficiente, sem retornar nenhum valor e de forma iterativa, ou seja, sem chamadas recursivas.

Quando estamos tentando resolver um problema com programação, nossa primeira preocupação é obviamente resolver o problema, e nesta etapa é normal não pensarmos muito em custos, seja de tempo ou memória. Contudo, o processo de codificação não deveria finalizar ao encontramos a primeira solução.

Ok. Temos uma solução! Será que é possível melhorar?

Se fazer esta pergunta e, claro, buscar respondê-la pode ser um grande aliado no aprendizado da programação.

Nós já vimos duas formas diferentes para inserir em uma árvore binária. Será que é possível realizar esta inserção de forma mais eficiente?

Bom. Se levarmos em conta o custo de acesso à pilha em um processo recursivo, uma versão iterativa pode ser mais rápida e vamos apresentar uma versão nesta aula.

Como não teremos recursão, a primeira ação aqui é encontrar o ponto de inserção. Para isso precisamos percorrer a árvore binária com um loop (um laço, uma repetição). A variável auxiliar aux é inicializada com o ponteiro para a raiz da árvore. Assim, enquanto aux for diferente de null, iremos caminhar na árvore para a direita ou para a esquerda.

Quando a repetição finalizar, significa que encontramos a posição onde será feita a inserção. Perceba que estamos trabalhando aqui com ponteiro para ponteiro para eliminar a necessidade de retorno também. Assim, aux é um filho à esquerda ou à direita de um nó da árvore e seu valor é null. Então, faremos a locação de memória para este filho e salvaremos o valor a ser inserido nesta região de memória.

Perceba que seu filhos são setados para null. A próxima inserção pode ocorrer em um destes filhos, esquerda ou direita.

/*
    Procedimento iterativo (sem recursão) para inserir em uma árvore binária
*/
void inserir_versao_3(NoArv **raiz, int num){
    NoArv *aux = *raiz;
    while(aux){
        if(num < aux->valor)
            raiz = &aux->esquerda;
        else
            raiz = &aux->direita;
        aux = *raiz;
    }
    aux = malloc(sizeof(NoArv));
    aux->valor = num;
    aux->esquerda = NULL;
    aux->direita = NULL;
    *raiz = aux;
}

Código de exemplo completo de uma Árvore Binária de Busca

/*
            Aula 268: Como inserir em uma Árvore Binária de Busca?
            TERCEIRA VERSÃO

            Código escrito por Wagner Gaspar
            Setembro de 2021
*/

typedef struct no{
    int valor;
    struct no *direita, *esquerda;
}NoArv;

NoArv* inserir_versao_1(NoArv *raiz, int num){
    if(raiz == NULL){
        NoArv *aux = malloc(sizeof(NoArv));
        aux->valor = num;
        aux->esquerda = NULL;
        aux->direita = NULL;
        return aux;
    }
    else{
        if(num < raiz->valor)
            raiz->esquerda = inserir_versao_1(raiz->esquerda, num);
        else
            raiz->direita = inserir_versao_1(raiz->direita, num);
        return raiz;
    }
}

void inserir_versao_2(NoArv **raiz, int num){
    if(*raiz == NULL){
        *raiz = malloc(sizeof(NoArv));
        (*raiz)->valor = num;
        (*raiz)->esquerda = NULL;
        (*raiz)->direita = NULL;
    }
    else{
        if(num < (*raiz)->valor)
            inserir_versao_2(&((*raiz)->esquerda), num);
        else
            inserir_versao_2(&((*raiz)->direita), num);
    }
}

void inserir_versao_3(NoArv **raiz, int num){
    NoArv *aux = *raiz;
    while(aux){
        if(num < aux->valor)
            raiz = &aux->esquerda;
        else
            raiz = &aux->direita;
        aux = *raiz;
    }
    aux = malloc(sizeof(NoArv));
    aux->valor = num;
    aux->esquerda = NULL;
    aux->direita = NULL;
    *raiz = aux;
}

void imprimir_versao_1(NoArv *raiz){
    if(raiz){
        printf("%d ", raiz->valor);
        imprimir_versao_1(raiz->esquerda);
        imprimir_versao_1(raiz->direita);
    }
}

void imprimir_versao_2(NoArv *raiz){
    if(raiz){
        imprimir_versao_2(raiz->esquerda);
        printf("%d ", raiz->valor);
        imprimir_versao_2(raiz->direita);
    }
}

int main(){

    NoArv *raiz = NULL;
    int opcao, valor;

    do{
        printf("\n\t0 - Sair\n\t1 - Inserir\n\t2 - Imprimir\n");
        scanf("%d", &opcao);

        switch(opcao){
        case 1:
            printf("\n\tDigite um valor: ");
            scanf("%d", &valor);
            //raiz = inserir_versao_1(raiz, valor);
            //inserir_versao_2(&raiz, valor);
            inserir_versao_3(&raiz, valor);
            break;
        case 2:
            printf("\n\tPrimeira impressao:\n\t");
            imprimir_versao_1(raiz);
            printf("\n");
            printf("\n\tSegunda impressao:\n\t");
            imprimir_versao_2(raiz);
            printf("\n");
            break;
        default:
            if(opcao != 0)
                printf("\n\tOpcao invalida!!!\n");
        }
    }while(opcao != 0);

    return 0;
}