Como imprimir uma Árvore Binária de Busca?

Dando continuidade ao estudo da estrutura Árvore Binária de Busca, vamos aprender hoje duas formas para percorrer e imprimir uma árvore binária.

Na aula anterior nós aprendemos uma forma de inserir na árvore. Contudo, por mais que a agente consiga testar nosso código, nada é impresso. Então, vamos imprimir nossa árvore na tela para ter certeza que a inserção está sendo feita corretamente.

Assim como a inserção, a impressão também pode utilizar recursão. Na verdade ela é bem intuitiva com recursão, se a raiz não for nula, imprimimos o valor do nó raiz e fazemos duas chamadas recursivas, uma para a subárvore à esquerda e outra para a subárvore à direita, como apresentado a seguir.

/*
    Procedimento para imprimir uma árvore binária
*/
void imprimir_versao_1(NoArv *raiz){
    if(raiz){
        printf("%d ", raiz->valor);
        imprimir_versao_1(raiz->esquerda);
        imprimir_versao_1(raiz->direita);
    }
}

Também é possível imprimir os valores de forma ordenada. A verdade é que a árvore binária já guarda os valores ordenados (menores à esquerda e maiores à direita). Para obtê-los dessa forma, basta imprimir primeiro o elemento mais a esquerda, em seguida a raiz e só depois o elemento à direita. Fazendo um rascunho em um papel com uma árvore pequena você pode constatar que dessa forma teremos uma lista de números ordenada de forma crescente.

/*
    Imprime os valores da árvore em ordem crescente
*/
void imprimir_versao_2(NoArv *raiz){
    if(raiz){
        imprimir_versao_2(raiz->esquerda);
        printf("%d ", raiz->valor);
        imprimir_versao_2(raiz->direita);
    }
}

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

/*
            Aula 266: Como imprimir 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;
    }
}

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);
            break;
        case 2:
            printf("\n\tPrimeira impresao:\n");
            imprimir_versao_1(raiz);
            printf("\n");
            printf("\n\tSegunda impresao:\n");
            imprimir_versao_2(raiz);
            printf("\n");
            break;
        default:
            if(opcao != 0)
                printf("\n\tOpcao invalida!!!\n");
        }
    }while(opcao != 0);

    return 0;
}

Início