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.

Na primeira inserção que fizemos a função retornava o endereço do novo nó criado. Esta não é a única forma de inserir um elemento em uma árvore binária. Na verdade existem diversas variações dependendo inclusiva das estruturas que são utilizadas. Nesta aula vamos aprender um segunda forma de inserir um pouco mais eficiente.

Na versão anterior o endereço do novo nó era retornado para atualizar a variável raiz criada na função main. Assim, se passarmos para o procedimento de inserção o endereço desta variável não será necessário nenhum tipo de retorno, uma vez que a variável poderá ser atualizada dentro do próprio procedimento de inserção.

É exatamente isso que é feito no trecho de código a seguir. Observe que a lógica é exatamente a mesma da função anterior. A diferença é que agora o procedimento recebe ponteiro para ponteiro.

/*
    Inserir versão 2
*/
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);
    }
}

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

/*
            Aula 266: Como inserir em uma Árvore Binária de Busca?
            SEGUNDA 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 imprimir_versao_1(NoArv *raiz){ // 50 25 30 100
    if(raiz){
        printf("%d ", raiz->valor);
        imprimir_versao_1(raiz->esquerda);
        imprimir_versao_1(raiz->direita);
    }
}

void imprimir_versao_2(NoArv *raiz){ // 25 30 50 100
    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);
            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;
}