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>
#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;
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
// 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;
}