927507_Lista_4 1

Pontifícia Universidade Católica de Minas Gerais
Campus Belo Horizonte – Núcleo Universitário São Gabriel
Curso: Engenharia de Computação
Disciplina: AED II
Professor: Júlio César Dillinger Conway
LISTA DE EXERCÍCOS 4 – ÁRVORES COM ALOCAÇÃO DINÂMICA
VALOR: 5 PONTOS
GRUPOS DE ATÉ 3 ALUNOS

Exercícios

Exercício 1: Dada a seguinte seqüência de entrada de nós de uma árvore binária de pesquisa (ABP), construa a árvore através de um desenho:

Seqüência: 63, 29, 81, 99, 36, 1, 15, 7, 74, 35, 18, 26, 90, 25, 45, 17, 98, 68, 13, 44, 27, 9, 83, 58,3

Quais os nós folhas?
Dê o nível e altura dos nós 36, 18,90, 68, 17 29, 3.
Qual a altura da ávore?
Qual as seqüências de caminhamento percorrendo esta árvore em:
Pré_Ordem
Em_Ordem
Pós_Ordem

Exercício 2: Considere a seguinte entrada de dados:

M, G, H, A, Z, U, P, Q, B, F, K, N, C, U, V, E, I, O, X, D, R, J

Desenhe a ABP resultante.
Indique os caminhos (sequências) em Pré-ordem, Pós-ordem e Em-ordem.

Para a árvore do exercício 2 indique:
a) O grau da árvore;
b) O número de folhas;
c) O nó com menor nível e que nível é este;
d) O nó com maior nível e que nível é este;
e) A altura da árvore;

Exercício 3: Considere a função abaixo que imprime os elementos de uma ABP:

Baseado nesse código escreva um procedimento recursivo para achar a maior chave de uma árvore de pesquisa binária.

Exercício 4: Considere que os elementos de uma ABP foram inseridos nesta ordem:
K B D A S V U C D J L O P X E H Z I M
Baseado no código acima, mostre como os elementos serão exibidos na tela.
Lembre-se que cada letra tem seu código ASCII correspondente, e que segue a ordem do alfabeto, ou seja, a letra A < B, J > C, etc.

Exercício 5: Baseado no TAD árvore disponibilizado, tente escrever um algoritmo recursivo que calcula a altura de uma árvore.