Algoritmos e Estrutura de Dados II 07/08

Descrição de Árvores Binárias de Busca (ABB)

Diagrama de uma ABB. O campo chave de uma  folha à esquerda da raiz precisa ser menor ou igual (ou maior, a depender do autor), e as folhas à direita devem ter esse campo maior do que o da raiz.

Descrição em prosa do algoritmo Busca_ABB, para encontrar uma determinada chave numa árvore binária de busca.

O algoritmo busca_ABB:

Uma tarefa para orientar os estudos:

1. Na primeira encontrei a seguinte dificuldade, eu não posso criar um valor auxiliar para cada chave analisada (campo info), para comparar com a do ponteiro esquerdo ou direito da folha da árvore. Se a árvore tiver mil nós, eu precisaria de mil variáveis e isso explodiria a memória da máquina. Também não adianta comparar com o campo info da raiz (primeiro nó de uma árvore).

SOLUÇÃO: Se bem que de repente, me bateu uma idéia melhor. Já que o campo chave da raiz deve ser a referencia, bastaria somarmos TODOS os nós que saem do ponteiro esquerdo, e todos que saem do ponteiro esquerdo e comparar um conjunto com o outro.

Deixo assim em prosa, se alguém quiser postar uma implementação em portugol ou qualquer linguagem pode postar nos comentários.
2. A versão não recursiva do Busca_ABB... Vou ficar devendo, mas sei que o Jorge implementou uma solução aprovada pelo professor.
3.Essa eu resolvi implementando um contador, cada vez que o procedimento passar por um valor idêntico ao guardado em C (variável do Busca_ABB), o contador, que inicia com zero, é incrementado em 1.