Escreva uma função não-recursiva que verifique a existência de um valor
na árvore binária.
Passo 1
A questão pede para escrever uma função não-recursiva que verifique se um valor X está presente em uma árvore binária. O conteúdo envolvido é travessia (search) em uma árvore binária usando estruturas de dados auxiliares (pilha ou fila). Para resolver, vamos precisar entender como usar uma pilha para simular a chamada recursiva de uma busca em profundidade (DFS).
Passo 2
A estratégia escolhida é realizar uma busca em profundidade (DFS) iterativa, usando uma pilha. Em cada iteração, retiramos o nó do topo da pilha, comparamos seu valor com X e, se não for igual, empilhamos seus filhos (primeiro filho esquerdo, depois filho direito, ou vice-versa, conforme preferência).
Inicializamos uma pilha vazia e, se a raiz não for nula, empilhamos a raiz. Em seguida, entramos em um laço que continua enquanto a pilha não estiver vazia.
Inicializamos uma pilha vazia e, se a raiz não for nula, empilhamos a raiz. Em seguida, entramos em um laço que continua enquanto a pilha não estiver vazia.
Passo 3
Dentro do laço, retiramos o nó do topo da pilha. Se o valor desse nó for igual a X, retornamos verdadeiro. Caso contrário, se o nó tiver filho direito, empilhamos esse filho; depois, se tiver filho esquerdo, empilhamos o filho esquerdo. Isso garante que o próximo nó a ser processado seja o filho esquerdo (comportamento clássico de DFS).
Se o laço terminar sem encontrar X, retornamos falso, indicando que o valor não está presente na árvore.
Se o laço terminar sem encontrar X, retornamos falso, indicando que o valor não está presente na árvore.
Resposta
// Definição simplificada de nó de árvore binária
struct TreeNode {
int valor;
TreeNode *esq;
TreeNode *dir;
};
struct TreeNode {
int valor;
TreeNode *esq;
TreeNode *dir;
};
bool existeValor(TreeNode *raiz, int X) {
if (raiz == nullptr) {
return false;
}
if (raiz == nullptr) {
return false;
}
// Pilha para nós a visitar
std::stack<TreeNode*> pilha;
pilha.push(raiz);
while (!pilha.empty()) {
TreeNode *no = pilha.top();
pilha.pop();
// Verifica se o valor do nó é X
if (no->valor == X) {
return true;
}
// Empilha primeiro o filho direito (vai ser processado depois)
if (no->dir != nullptr) {
pilha.push(no->dir);
}
// Empilha o filho esquerdo (será processado em seguida)
if (no->esq != nullptr) {
pilha.push(no->esq);
}
}
// Se percorrer toda a árvore sem encontrar X
return false;
}