927507_Lista_4 2

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

Lucas Naziazeno Pilar
Rafael Dornelas Gobbi

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?
3, 17, 25, 27, 44, 58, 83, 35, 68, 98
Dê o nível e altura dos nós 36, 18,90, 68, 17 29, 3.
3, 5, 4, 4, 6, 2,6 respectivamente
Qual a altura da ávore?
7
Qual as seqüências de caminhamento percorrendo esta árvore em:
Pré_Ordem: 63,29,1,15,7,3,13,9,18,17,26,25,27,36,35,45,44,58,81,74,68,99,90,83,98
Em_Ordem: 1,3,7,9,13,15,17,18,25,26,27,29,35,36,44,45,58,63,58,74,81,83,90,98,99
Pós_Ordem: 3,9,13,7,17,25,27,26,18,15,1,35,44,58,45,36,29,68,74,83,98,90,99,81,63

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

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

Pré-Ordem:
M,G,A,B,F,C,E,D,H,K,I,J,M,Z,U,P,N,P,Q,R,V,X

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

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

Para a árvore do exercício 2 indique:
a) O grau da árvore; 2
b) O número de folhas; 5
c) O nó com menor nível e que nível é este; Raiz M nivel 1
d) O nó com maior nível e que nível é este; Nó D nivel 7
e) A altura da árvore; 8

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.

void maimen(arvore *raiz, int &mai, int &men, int &c)
{
if(arvore_Vazia()) {