Escreva e implemente um algoritmo não recursivo para obter a altura de uma ABB.

Passo 1

Temos uma Árvore Binária de Busca (ABB) e queremos calcular sua altura sem usar recursão, ou seja, iterativamente. Vamos precisar percorrer a árvore nível a nível e contar quantos níveis ela possui.
Para definir altura, consideramos que uma árvore vazia tem altura 0 e que a altura de uma árvore não vazia é o número de níveis existentes da raiz até as folhas.

Passo 2

Uma forma comum de fazer isso sem recursão é usar uma travessia em largura (Breadth-First Search) com uma fila, contando níveis: a cada vez que processamos todos os nós de um nível, incrementamos a altura.

Passo 3

Segue o pseudocódigo em estilo C para ilustrar a implementação iterativa usando fila e contagem de níveis:

Passo 4

Analisando o algoritmo, vemos que cada nó é enfileirado e desenfileirado exatamente uma vez, e fazemos um trabalho constante por nó, resultando em complexidade O(n), onde n é o número de nós da árvore.

Resposta

// Estrutura básica de nó da ABB
typedef struct Node {
int chave;
struct Node* left;
struct Node* right;
} Node;
// Função para calcular a altura de uma ABB sem recursão
int alturaABB(Node* root) {
if (root == NULL)
return 0;
// Fila para percorrer nível a nível
Node** fila = malloc(sizeof(Node*) * 1000); // ou tamanho dinâmico conforme necessidade
int inicio = 0, fim = 0;

// Enfileira a raiz
fila[fim++] = root;
int altura = 0;

// Enquanto houver nós na fila
while (inicio < fim) {
    int nivelSize = fim - inicio; // quantos nós restam neste nível

    // Processa todos os nós deste nível
    for (int i = 0; i < nivelSize; i++) {
        Node* atual = fila[inicio++];

        // Enfileira filhos, se existirem
        if (atual->left != NULL)
            fila[fim++] = atual->left;
        if (atual->right != NULL)
            fila[fim++] = atual->right;
    }

    // Um nível completo foi processado
    altura++;
}

free(fila);
return altura;
}

Exercícios relacionados