8.2.1.1 Exercícios sobre
Árvore de Busca
Q.1:
-
Implemente uma Árvore de Busca Binária
com Nodos contendo somente números inteiros. Utilize OOP, implementando
a Árvore em C++.
Q.2:
-
Uma árvore é
uma estrutura tipicamente recursiva. Nós vimos um algoritmo iterativo
para realizar esta busca. Porque não utilizar um algoritmo recursivo
para a busca em uma árvore de busca ?
Elabore um algoritmo recursivo para efetuar
uma busca em uma árvore binária de busca pressupondo as estruturas
de dados do exemplo anterior.
-
Existe alguma razão para evitarmos
algoritmos de busca em árvore recursivos (memória, complexidade,
etc) ? Justifique.
Q.3:
-
O algoritmo recursivo
de inserção em árvore binária de busca apresentado
é bastante simples e reflete bem a estrutura da própria árvore.
Não será possível
também realizar a função deste algoritmo com um algoritmo
iterativo ? Crie um algoritmo iterativo para a inserção simples
em uma árvore binária.
Q.4:
-
Elimine os nodos 3 e 12
da árvore do exemplo de eliminação em árvore
de busca binária anterior, nesta ordem, a partir da árvore
anterior utilizando o algoritmo dado.
Mostre o stack a cada chamada recursiva.