Lista de Exerc cios Sugerida Arvore Binaria

Lista de Exercícios Sugerida – Árvore Binária –
12 de Abril de 2014
1 – Escreva algoritmos recursivos e não-recursivos para determinar:
a. O número de nós de uma árvore binária
b. A soma do conteúdo de todos os nós numa árvore binária de inteiros
c. A profundidade de uma árvore binária
2 – Escreva um algoritmo para determinar se uma árvore binária é:
a. Estritamente binária
b. Completa
c. Quase completa
3 – Prove que os nós de uma árvore quase completa estritamente binária com n folhas podem ser numerados de 1 a 2n - 1, de tal modo que o número atribuído ao filho esquerdo do nó numerado com i seja 2i, e o número atribuído ao filho direito do nó numerado com i seja 2i +
1.
4 – Duas árvores binárias são semelhantes se ambas estiverem vazias, ou se forem não-vazias e suas sub-árvores esquerdas e sub-árvores direitas forem semelhantes. Escreva um algoritmo para determinar se duas árvores binárias são semelhantes.
5 – Desenvolva um algoritmo para localizar repetições numa lista de números sem usar uma árvore binária. Se existirem n números distintos na lista, quantas vezes dois números precisarão ser comparados em seu algoritmo? E se todos os n números forem iguais?
6 – Escreva um algoritmo que aceite a raiz de uma árvore binária de busca e elimine o menor elemento da árvore.
7 – Escreva um algoritmo que aceite um nó como parâmetro e retorne TRUE se esse nó for a raiz de uma árvore binária válida, e FALSE, caso contrário.
8 – Escreva um algoritmo que receba a raiz de uma árvore binária e um nó da árvore e retorne o nível do nó na árvore.
9 – Escreva um programa para fazer a seguinte experiência: gerar 100 números aleatórios. À medida que cada número for gerado, insira-o numa árvore binária de busca, inicialmente vazia. Quando todos os 100 números tiverem sido inseridos, imprima o nível da folha de maior nível e o nível da folha de menor nível. Repita esse processo 50 vezes.
Imprima uma tabela com uma contagem de quantas das 50 passagens resultaram numa diferença entre o