exerciciosteoricos_arvores

Prévia do material em texto

UNIVERSIDADE FEDERAL DO PARANÁ 
SETOR DE EDUCAÇÃO PROFISSIONAL E TECNOLÓGICA 
TECNOLOGIA EM ANÁLISE E DESENVOLVIMENTO DE SISTEMAS 
ESTRUTURA DE DADOS II 
PROF. ME. ANDREIA DE JESUS 
 
Exercícios - Árvores 
 
1. Considerando a representação em parênteses de uma árvore, reescreva-as 
utilizando a representação hierárquica: 
 
 a) (a (b(c)) (e (f( )( )) (g( )( ))) (h)) 
 
 b) (a (b(c(d(f)(g))) (h)) 
 
 c) (5(4(11(7( )( )) (2( )( ))) ( )) (8(13( )( )) (6( )(1( )( ))))) 
 
2. Abaixo está uma árvore: 
 
 
 
 
 
 
 
 
 
 
 
Responda: 
a) Ache os nós filhos de H 
b) Ache o nó pai de K 
c) Ache o nós filhos de C 
d) Altura da árvore 
e) Altura do nó G 
f) Nível do nó G 
g) Nível do nó A 
h) Altura do nó E 
i) As subárvores do nó F. 
I H E 
B 
A 
L 
K 
J 
G 
D 
C 
F 
3. Dada a árvore: 
1 ––––––––––––––––––––––––––––––––––––––– 
2 ––––––––––––––––––––––––––––––––––– 
7 –––––––––––––––––––––––––––– 
8 –––––––––––––––––––––––––––– 
3 ––––––––––––––––––––––––––––––––––– 
9 –––––––––––––––––––––––––––– 
4 ––––––––––––––––––––––––––––––––––– 
10 ––––––––––––––––––––––––––– 
14 –––––––––––––––––––– 
15 –––––––––––––––––––– 
16 –––––––––––––––––––– 
17 –––––––––––––––––––– 
20 ––––––––––––– 
18 –––––––––––––––––––– 
19 –––––––––––––––––––– 
11 ––––––––––––––––––––––––––– 
12 ––––––––––––––––––––––––––– 
5 ––––––––––––––––––––––––––––––––––– 
13 ––––––––––––––––––––––––––– 
6 ––––––––––––––––––––––––––––––––––– 
 
Resolva: 
a) Redesenhe-a na forma tradicional. 
b) Qual o grau da mesma? Explique. 
c) Qual a altura da árvore? 
d) Dê o nível (altura) de cada nó. 
e) Dê o grau de cada nó. 
f) Transforme-a em uma árvore binária utilizando a regra: filhos à esquerda, irmãos à 
 direita. 
 
4. Considerando o conceito de árvore binária cheia: 
 
• Todos os seus nós internos têm duas subárvores associadas. 
• O número n de nós de uma árvore cheia de altura h é: nos_arvore = 2h - 1 
• O número de nós em um determinado nível é: nos_nivel = 2nivel 
 
 
 
 
 
 
 
 
 
 
 
a) Qual é o número máximo de nós que pode ser achado nos níveis 5, 7 e 12 de uma árvore 
binária? 
 
 
 
5. Listar as letras no percursos pré-ordem, in-ordem e pos-ordem da seguinte árvore: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
6. Tendo em conta a árvore apresentada a seguir, indique a sequência dos elementos percorrendo 
a árvore de acordo com, 
 
a) ordem post-ordem 
b) ordem pré-ordem 
c) ordem in-ordem 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
7. Uma árvore binária tem 10 nós. O passeio in-ordem e pré-ordem da árvore é 
mostrado abaixo. Desenhe a respectiva árvore. 
 
Pré-ordem: J C B A D E F I G H 
 Em-ordem: A B C E D F J G I H 
 
8. Diga, para cada uma das árvores binárias abaixo, se são balanceadas, perfeitamente 
balanceadas ou nenhum dos casos ou ambos e liste seus nós em 
 
(i) pré-ordem, 
(ii) in-ordem 
(iii) pós-ordem: 
O 
I 
N 
E 
B 
A 
L 
O 
D C 
F 
10 
12 
8 
6 
2 
1 
11 
9 
5 4 
7 
13 14 
14 
 
a) (1 (2 (4) (5)) (3 (6) (7))); 
b) (A (B (D (F)) (E)) (C (G (H)))). 
 
 
9. Mostre que, se conhecermos a sequência de nós em pré-ordem e in-ordem de uma 
árvore binária, podemos descobrir qual é a estrutura dessa árvore. Dê um exemplo. 
 
10. Suponha que tenhamos números entre 1 e 1000 em uma árvore binária de pesquisa 
e desejamos fazer uma pesquisa (busca) pelo número 363. Qual(is) das seguintes 
sequências não poderia(m) ser a sequência de nodos examinados? Justifique. 
 
a) 2, 252, 401, 398, 330, 344, 397, 363. 
b) 924, 220, 911, 244, 898, 258, 362, 363. 
c) 925, 202, 911, 240, 912, 245, 363. 
d) 2, 399, 387, 219, 266, 382, 381, 278, 363. 
e) 935, 278, 347, 621, 299, 392, 358, 363. 
 
11. Considere uma árvore binária de pesquisa, inicialmente vazia, a qual armazena 
caracteres. Faça a inserção de todas as letras do seu nome completo na mesma 
sequência da escrita, desprezando os espaços em branco. Considere, também, 
todas as letras maiúsculas, sem acentuação e a ordenação da árvore de acordo com 
a ordem alfabética, onde a letra A é o menor valor e a letra Z é o maior. Exemplo: 
Michel Miguel Elias Temer Lulia = MICHELMIGUELELIASTEMERLULIA; inserir a 
letra M, em seguida a letra I, depois a letra C e assim por diante até a inserção da 
última letra que, no exemplo, é a letra A. Obs: Letras repetidas devem ser inseridas 
à direita. 
 
Alfabeto: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z. 
 
Em seguida, resolva: 
a) Qual é a altura da árvore? 
b) Dê o resultado de um percurso pós-fixado. 
c) Quem é o sucessor do nó de maior altura (caso existam dois ou mais, considere 
 o menor deles) na árvore? 
d) Quem é o predecessor do quarto nó inserido na árvore? 
e) Indique o resultado da retirada do nó raiz da árvore.