Dando continuidade ao estudo da estrutura ÁRVORE BINÁRIA DE BUSCA, vamos aprender nesta aula o conceito de altura e como calcular a altura de uma árvore binária.

A altura de uma árvore binária nada mais é que o caminho partindo da raiz até a folha mais distante. Uma árvore com três nós, a raiz, um filho à esquerda e um filho à direita, possui altura 1, pois basta um passo para sair da raiz e chegar à folha mais distante (que neste caso estão à mesma distancia da raiz).

Partindo da ideia acima concluímos que calcular a altura de uma árvore é um processo recursivo. Precisamos descobrir a altura da subárvore à esquerda e à direita e verificar qual é maior.

Se a raiz recebida for nula retornaremos -1. Mais adiante ficará claro porque -1 e não 0.

Contudo, se a raiz não for nula, precisamos descobrir a altura das duas subárvores, esquerda e direita, e retornar a maior + 1. Esse +1 representa o caminho da raiz até a subárvore de maior caminho.

Porém, imagine uma árvore que possui apenas 1 nó, a raiz. Sua altura é zero. Assim, ao tentar calcular a altura desta árvore com a nossa lógica, teremos como resultado a altura da maior subárvore + 1. Como a altura desta árvore é zero, ao receber uma raiz nula a função precisa retornar -1 para anular o +1. Dessa forma, a altura da subárvore à esquerda e á direita será -1 (pois ambas são nulas) e o resultado final será: -1 + 1 = 0.

A seguir é apresentada uma versão de uma função recursiva para calcular a altura de uma árvore binária de busca.

/*
     Função para calcular a altura de uma árvore binária
*/
int altura(NoArv *raiz){
    if(raiz == NULL){
        return -1;
    }
    else{
        int esq = altura(raiz->esquerda);
        int dir = altura(raiz->direita);
        if(esq > dir)
            return esq + 1;
        else
            return dir + 1;
    }
}

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

/*
            Aula 271: Como calcular a ALTURA uma Árvore Binária?

            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){ // 500
    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){ // 500 700 850 1000 1500
    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;
}

int altura(NoArv *raiz){
    if(raiz == NULL){
        return -1;
    }
    else{
        int esq = altura(raiz->esquerda);
        int dir = altura(raiz->direita);
        if(esq > dir)
            return esq + 1;
        else
            return dir + 1;
    }
}

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\t4 - Altura\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;
        case 4:
            printf("\n\tAltura da arvore: %d\n\n", altura(raiz));
            break;
        default:
            if(opcao != 0)
                printf("\n\tOpcao invalida!!!\n");
        }
    }while(opcao != 0);

    return 0;
}