O algoritmo abaixo foi elaborado por um analista para realizar a busca em uma árvore binária ordenada, a partir da seguinte especificação: dado um valor chave “x” e um ponteiro “pt” para o nó raiz passados como parâmetros para o algoritmo “Busca”, o algoritmo deverá retornar uma das opções na variável “b”: 0, se a árvore estiver vazia; 1, se “x” pertencer à árvore; 2, se “x” não pertencer à árvore.

Sabendo que no algoritmo acima “chave” armazena o valor do nó, “esq” é o ponteiro para o nó descendente esquerdo, “dir” é o ponteiro para o nó descendente direito e “ref” indica que a passagem de parâmetros é por referência, assinale a opção correta sobre o algoritmo “Busca” elaborado.

Definições
registro no_lista
inicio
inteiro chave
Registro no_lista *dir, *esq
fim

Algoritmo
algoritmo Busca (inteiro x, registro no_lista *pt,
ref inteiro b)
início
se (pt = nulo) então
b 0
senão
se (x = pt->chave) então
b 1
senão
se (x > pt->dir->chave) então
se (pt->esq = nulo) então
b 2
senão
pt pt->esq
Busca (x, pt, b)
fimse
senão
se (pt->dir = nulo) então
b 2
senão
pt pt->dir
Busca (x, pt, b)
fimse
fimse
fimse
fimse
fimalgoritmo