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