Dando continuidade ao nosso Curso de Programação C, vamos aprender nesta aula como buscar um elemento em uma ÁRVORE BINÁRIA DE BUSCA de forma iterativa, sem fazer uso de recursão.

Nas aulas anteriores já mencionamos que toda vez que usamos recursão há um custo envolvido no acesso à pilha de recursão. Assim, sempre que possível, é preferível uma versão iterativa para resolver o problema.

Na aula anterior nós aprendemos como realizar uma busca em uma árvore binária de busca usando recursão. Nesta aula vamos aprender como realizar a mesma operação de forma iterativa, sem recursão.

Como desejamos substituir a recursão, significa que vamos precisar de um loop, uma repetição. Usaremos para este loop um while.

A primeira ação a ser realizada é verificar se a raiz é diferente de nula. Como não vamos usar recursão, este teste fica dentro de um while. Enquanto raiz for diferente de null, desejamos realizar algo.

Dentro da repetição, como raiz é diferente de null, precisamos verifica se é o elemento que estamos procurando. Se for o elemento procurado precisamos quebrar a repetição. Isso é feito com a instrução return, retornando o endereço do nó que possui o elemento procurado.

Contudo, caso não seja o elemento procurado, precisamos verificar se é maior ou menor. Se o elemento da raiz for maior que o número procurado, então precisamos seguir para o filho à esquerda, onde se encontram os elementos menores que a raiz. Porém, se a raiz for menor que o elemento procurado, então precisamos seguir o filho à direita, onde se encontram os elementos maiores que a raiz.

/*
     Função iterativa para realizar uma busca em uma árvore binária de busca
*/
NoArv* buscar_versao_2(NoArv *raiz, int num){
    while(raiz){
        if(num < raiz->valor)
            raiz = raiz->esquerda;
        else if(num > raiz->valor)
            raiz = raiz->direita;
        else
            return raiz;
    }
    return NULL;
}

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

#include <stdio.h>
#include <stdlib.h>

/*
            Aula 270: Como BUSCAR em uma Árvore Binária de Busca?
            VERSÃO ITERATIVA

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

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

NoArv* buscar_versao_2(NoArv *raiz, int num){
    while(raiz){
        if(num < raiz->valor)
            raiz = raiz->esquerda;
        else if(num > raiz->valor)
            raiz = raiz->direita;
        else
            return raiz;
    }
    return NULL;
}

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 *busca, *raiz = NULL;
    int opcao, valor;

    do{
        printf("\n\t0 - Sair\n\t1 - Inserir\n\t2 - Imprimir\n\t3 - Buscar\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;
        case 3:
            printf("\n\tDigite o valor a ser procurado: ");
            scanf("%d", &valor);
            //busca = buscar_versao_1(raiz, valor);
            busca = buscar_versao_2(raiz, valor);
            if(busca)
                printf("\n\tValor encontrado: %d\n", busca->valor);
            else
                printf("\n\tValor nao encontrado!\n");
            break;
        default:
            if(opcao != 0)
                printf("\n\tOpcao invalida!!!\n");
        }
    }while(opcao != 0);

    return 0;
}