Partindo para a prática, vamos aprender nesta aula como inserir em uma estrutura do tipo árvore binária. Nesta aula será apresentada uma solução. Nas aulas seguintes veremos outras formas de inserção em uma árvore binária.

Caso você não tenha estudado a aula anterior ou não se recorde de como funciona uma árvore binária eu recomendo que você revise a aula anterior. Precisamos desse conhecimento teórico para implementar uma árvore binária na prática.

Vamos iniciar com a estrutura que irá formar nossa árvore. Esta estrutura possui três campos, um campo de informação e dois ponteiros, um para a esquerda e outro para a direita, como apresentado a seguir.

/*
    Estrutura nó
*/
typedef struct no{
    int valor;
    struct no *direita, *esquerda;
}NoArv;

A raiz da nossa árvore binária será um ponteiro para um nó declarado na função main que inicialmente terá o valor nulo, que indica que a árvore está vazia.

Ao tentar fazer uma inserção, o primeiro teste que precisamos fazer é verificar se a árvore está vazia ou não. Caso a árvore esteja vazia, a raiz será nula. Assim, basta alocar memória para um novo nó, inserir a informação do nó e retornar o endereço desse nó que será recebido como retorno na função main, mantendo o ponteiro atualizado.

/*
    Função parcial para inserir um nó na árvore
*/
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{
        // se raiz não for nula
    }
}

Contudo, se a raiz não for nula, precisamos descobrir em qual subárvore será inserido o novo elemento, esquerda se for menor que a raiz ou direita se for maior que a raiz.

Uma forma simples de fazer isso é por meio de recursão. Como a função retorna o endereço do novo nó, basta atualizar o ponteiro da direita ou da esquerda, como apresentado a seguir.

/*
    Função completa para inserir um novo nó
*/
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;
    }
}

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

/*
            Aula 265: Como inserir em uma Árvore Binária de Busca?

            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;
    }
}

int main(){

    NoArv *raiz = NULL;

    raiz = inserir_versao_1(raiz, 100);

    return 0;
}