AED-I-Lista-6

Prévia do material em texto

1 
Algoritmos e Estruturas de Dados I IBm1014 
Departamento de Computação e Matemática 1º Semestre/2012 
 Prof. Dr. José Augusto Baranauskas 6ª Lista de Exercícios 
 
1. Responda: 
a) Quantas árvores distintas existem com 3 nós? 
b) Quantas árvores orientadas distintas existem com 3 nós? 
c) Dada uma árvore cujo grau da raiz é d, como transformá-la em uma floresta com d árvores? 
d) Dada uma floresta com d árvores como transformá-la em uma árvore cujo nó raiz tem grau d? 
 
2. Em um diagrama convencional de árvore (raiz no topo): 
a) Se o nó X tem nível mais alto que o nó Y, então o nó X aparece abaixo de Y no diagrama? 
b) Se o nó A tem 3 irmãos e B é o pai de A, qual o grau de B? 
 
3. Considere árvores binárias que representam expressões aritméticas. Por exemplo, a expressão (7-
3)*(2+1)+10 é representada pela seguinte árvore: 
+
* 10
+-
1237
+
* 10
+-
1237
 
 
As folhas da árvore armazenam operandos e os nós internos os operadores. Quando avaliada, a expressão da 
árvore fornecida como exemplo é 22. Considere a seguinte representação para árvores binárias de 
expressões: 
 
 struct TreeNode 
 { char op; // operador: ‘+’, ‘-’, ‘*’, ‘/’ 
 float valor; // valor do operando 
 TreeNode *LeftNode, *RightNode; // subárvores 
 }; 
 typedef TreeNode *TreePointer; 
 
Nesta representação, o campo valor é usado apenas pelas folhas e o campo op pelos nós internos. 
Implemente os métodos para este tipo de árvore que: 
a) Imprima a expressão em notação pré-fixa; para o exemplo acima, o resultado é + * - 7 3 + 2 1 10; 
b) Imprima a expressão em notação in-fixa; para o exemplo acima, o resultado é 7 – 3 * 2 + 1 + 10; 
c) Imprima a expressão em notação pós-fixa; para o exemplo acima, o resultado é 7 3 – 2 1 + * 10 +; 
d) Retorne o valor correspondente à avaliação da expressão; para o exemplo acima, o resultado é 22. 
 
4. Desenhe as árvores binárias que correspondem às seguintes expressões aritméticas: 
a) 2*(a-b/c) 
b) a+b+5*c 
 
5. Mostre que se conhecermos a seqüência de nós em pré-ordem e em-ordem podemos construir a estrutura 
da árvore binária correspondente. Dê um exemplo. 
 
6. Encontre todas as árvores binárias cujos nós aparecem exatamente na mesma seqüência em: 
a) pré-ordem e em-ordem; 
b) pré-ordem e pós-ordem; 
c) em-ordem e pós-ordem. 
 
 2 
7. Desenhe a árvore binária correspondente às seguintes seqüências em pré-ordem 1, 2, 3, 4, 5, 6, 7, 8, 9 e 
em-ordem 3, 2, 6, 5, 4, 1, 7, 8, 9. 
 
8. Idem ao exercício anterior para as seqüências em pré-ordem: A, B, C, F, H, D, L, M, P, N, E, G, I e em-
ordem F, C, H, B, D, L, P, M, N, A, I, G, E. 
 
9. Considerando a árvore binária: 
a) Quantas subárvores ela contém? 
b) Quais os nós folhas? 
c) Quais os nós não folhas 
d) Qual o nível de cada nó? 
e) Quais os ancestrais do nó 6? E do nó 7? E do 
nó 8? 
f) Identifique todas as relações de parentesco 
entre os nós. 
 
5
3 8
64
7 
5
3 8
64
7 
 
 
10. Escreva um algoritmo recursivo que calcula a altura de uma árvore binária. 
 
11. Defina o algoritmo Equal que retorna false se, dadas duas árvores binárias S e T, elas não são iguais; 
caso contrário retorna true. 
 
12. Defina um algoritmo para percorrer árvore em nível (sugestão: use uma fila como estrutura auxiliar). Por 
exemplo, para a árvore dada a seguir, o percurso resultante é 30, 25, 45, 15, 41, 56, 35, 43, 50. 
 
25
15
30
45
41 56
504335
25
15
30
45
41 56
504335
 
 
13. Escrever algoritmos não recursivos para percorrer uma árvore binária em pré-ordem, pós-ordem e em-
ordem. 
 
14. Uma quarta maneira de se percorrer uma árvore binária é conseguida pelos três passos seguintes: 
• visite a raiz; 
• percorra a subárvore direita pelo mesmo método; 
• percorra a subárvore esquerda pelo mesmo método. 
a) Essa nova ordem tem alguma relação com alguma das 3 ordens discutidas em aula? 
b) Percorra dessa maneira a árvore do exercício 9. 
 
15. Implemente funções que, dada uma árvore binária, retorne: 
a) a quantidade de nós que armazenam números pares; 
b) a quantidade de nós que armazenam valores maiores que um determinado valor x (fornecido como 
parâmetro); 
c) a quantidade de nós folhas; 
d) a quantidade de nós que possuem apenas um filho; 
e) a quantidade de nós que possuem pelo menos um filho;