Escreva uma função não-recursiva que verifique se uma árvore binária é também de busca.

Passo 1

Resumindo o enunciado: o objetivo é implementar uma função não-recursiva que, dado o ponteiro para a raiz de uma árvore binária, determine se ela satisfaz a propriedade de árvore de busca (ou BST), isto é, para todo nó, os valores na subárvore esquerda são menores e na subárvore direita são maiores.

Passo 2

Antes de tudo, vale lembrar a propriedade fundamental de uma BST: se fizermos um percurso em ordem (in-order), os valores dos nós serão visitados em ordem estritamente crescente. Vamos usar essa característica para testar a árvore.

Passo 3

Como o enunciado pede solução não-recursiva, vamos simular o percurso in-order usando uma pilha (stack). Durante o percurso, mantemos uma variável lastValue que guarda o valor do nó visitado anteriormente. Se em algum momento encontrarmos um nó cujo valor é menor ou igual a lastValue, concluímos que não é BST.

Passo 4

Algoritmo passo a passo: 1) Inicialize uma pilha vazia e aponte current = root; 2) Enquanto current ≠ NULL, empurre current na pilha e faça current = current→left; 3) Quando current for NULL, desempilhe o topo da pilha em node; 4) Compare node→key com lastValue (inicialmente definido como o menor valor possível ou indicador de que não foi definido): se node→key ≤ lastValue, retorne false; caso contrário, atualize lastValue = node→key; 5) Faça current = node→right e volte ao passo 2; 6) Se a pilha esvaziar e current for NULL, retorne true.

Passo 5

Vamos agora traduzir isso num pseudocódigo em C para ficar bem claro como implementar a função sem recursão.

Resposta

#include <limits.h>
#include <stdbool.h>
// Definição típica de nó de árvore binária
typedef struct Node {
int key;
struct Node *left;
struct Node *right;
} Node;
bool isBST(Node *root) {
// Stack implícita via alocação dinâmica ou vetor
Node *stack[1000]; // ou use tamanho dinâmico conforme o máximo esperado
int top = -1;
Node *current = root;
int lastValue = INT_MIN;
bool hasLast = false; // indica se lastValue já foi atribuído
while (current != NULL || top >= 0) {
    // desça até a folha mais à esquerda
    while (current != NULL) {
        stack[++top] = current;
        current = current->left;
    }
    // desempilha um nó
    current = stack[top--];
    // verifica a ordenação estrita
    if (hasLast && current->key <= lastValue) {
        return false;
    }
    lastValue = current->key;
    hasLast = true;
    // tenta a subárvore direita
    current = current->right;
}
return true;
}

Exercícios relacionados