Estruturas de Dados
2015/16
Ficha Prática nº 5
Estruturas de Dados
Universidade da Beira Interior
Departamento de Informática
Árvores Binárias
1. Ilustre as árvores binárias de pesquisa resultantes da inserção por
ordem da seguinte sequência de elementos:
a. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
b. 3, 1, 4, 1, 5, 9, 2, 6, 5, 4.
c. 2, 7, 1, 8, 2, 8, 1, 8, 2, 8.
2. Implemente uma função que verifique se uma dada árvore binária
está correctamente ordenada.
3. Implemente uma função que procure por um elemento na árvore
e devolva um apontador para o elemento encontrado.
a. Ao procurar através do atributo chave
b. Ao procurar através de qualquer outro atributo
4. Codifique uma função que permita calcular a altura de uma árvore
binária.
5. Implemente a função que conta o número de nós de uma árvore
binária.
6. Implemente uma função para inserir um novo elemento na
respectiva posição de uma árvore binária.
7. Codifique uma função que permita mostrar todo o conteúdo de
uma árvore binária.
Estruturas de Dados
2015/16
Ficha Prática nº 5
8. Implemente uma função para eliminar um nó (especificado
através do atributo-chave) de uma árvore.
9. Implemente uma função que elimina uma árvore binária.
10.
Codifique a função que retorna o valor máximo de um
atributo:
a. Chave
b. Não-chave
11.
Implemente funções para determinas se uma dada árvore
binária de pesquisa é:
a. Completa
b. Cheia
c. Equilibrada
12.
Codifique uma função que efectue a passagem do conteúdo
de uma lista para uma árvore binária de pesquisa.
13.
Codifique uma função que permita efectuar a passagem do
contéudo de uma árvore binária para uma lista.
14.
Crie a função espelho de uma árvore binária. O resultado
será a árvore com os todos os nós-filho do lado esquerdo e direito
trocados.