Lista4_Arvores

Prévia do material em texto

IBILCE UNESP Departamento de Ciências de Computação e Estatística 
Profa. Inês Ap.Gasparotto Boaventura 
Estruturas de Dados 
Lista de Exercícios sobre Árvores Binárias 
 
(1) Percurso 
Lembrando dos percursos numa árvore binária, implementar as rotinas abaixo de forma recursiva. 
a) Mostrar uma árvore binária em pré-ordem 
b) Mostrar uma árvore binária em pós-ordem 
 
 
(2) Busca 
Podemos fazer várias formas de busca. Uma delas é buscar pelo valor do elemento e retornar 
verdadeiro ou falso. Outra forma é buscar pelo valor, mas retornar o ponteiro do nó que armazena o 
valor ou retornar NULL se o valor não existir. Implementar ambos os tipos de busca. 
 Boolean busca_valor(No_arv<t> *p, T valor); 
No_arv<T> * busca_no(No_arv<t> * p, T valor); 
 
(3) Diversas funções 
Fazer funções para árvores binárias: 
a) descubra o total de nós de uma árvore 
b) descubra a altura da árvore 
c) determine a quantidade de nós folhas de uma árvore 
d) determine a quantidade de nós de uma árvore que possuem somente um filho 
e) encontre o menor elemento de uma árvore 
f) encontre a soma de todos os elementos de uma árvore 
g) descubra a quantidade de nós que tem números pares em uma árvore 
h) descubra quantos nós possuem valores maiores que um valor x 
i) elimine o menor elemento da árvore 
 
 
 
(4) Criar uma copia 
Desenvolva uma função que duplica uma árvore binária e retorna o endereço da cópia. 
 
(5) Transformação de árvores 
 
É possível transformar uma árvore binária em uma árvore de busca binária (os elementos estão 
ordenados). Para isso tem-se que percorrer a primeira árvore segundo algum critério e inseri-los na 
árvore binária de busca. Implemente essa conversão usando os percursos pre-ordem, em-ordem e 
pós-ordem. Verifique se as árvores binárias de busca geradas são iguais. 
 
 
 
 
(6) Outra forma de percurso 
Escreva qual o comportamento que as formas de busca iriam apresentar se a seqüência de visita das 
sub-árvores fossem modificadas, ou seja percorrer as árvores da sub-árvore a direita para a esquerda. 
Com essa consideração, a busca em pós-ordem fica da seguinte forma: 
 Percorre Subárvore à direita; 
Percorre Subárvore à esquerda; 
Visita o Nó; 
 Mostrar o comportamento com um exemplo. 
 
(7) Desenho da árvore conhecendo as informações de percursos 
 
 Desenhe a árvore correspontente às seguintes sequências em pré-ordem 1 2 3 4 5 6 7 8 9 e em in-
ordem 3 2 6 5 4 1 7 8 9. Você deve usar ambas as informações de percurso para desenhar uma única 
árvore. 
 
(8) Ordenação de vetor através da construção de uma árvore binária 
 Escreva uma função: void TreeSort(no_arv<int> *t, vetor<int> &A); que ordena o 
vetor A por inserir seus elementos em uma árvore de busca binária, e depois percorrendo-a em in-
ordem faz a cópia ordenada dos elementos de volta para o vetor. 
 
(9) Árvores binárias, cujos nós mantém um ponteiro para o seu pai 
 
Os nós de uma árvore binária podem ser modificados de forma a conter um ponteiro para o seu nó pai. 
Defina a classe noarvP<T> de forma a manter esse ponteiro e escreva a função 
template<class T> 
void ImprimeAncestral(no_arv<T> * t) 
que imprime os dados dos nós do caminho do nó t e a raiz da árvore. 
 
(10) Travessia de uma árvore binária em largura 
 
Escreva uma função que implementa a travessia nível por nível de uma árvore binária, ou seja, 
começa com a raiz no nível 0, depois visita todos os filhos da raiz, no nível 1 e assim por diante. 
(você precisa definir uma fila para auxiliar nessa travessia) 
 
 (11) Árvores AVL 
 
1-Partindo de uma árvore AVL vazia, realize a inserção da seguinte sequência de chaves: 
 
 99, 44, 71, 80, 74, 63, 59, 120, 98, 150. 
 
Redesenhe a árvore a cada inserção. Indique para cada rotação feita, o nome da rotação e o nó 
desbalanceado. 
 
 
2- Seja uma árvore AVL T. Considere a inserção de um nó q em T, que tornou T desbalanceada. Seja p 
o nó desbalanceado mais próximo das folhas. 
 
a- Qual o valor exato de |he(p) - hd(p)| ? Por que não pode ser nem mais nem menos? 
 
b- Supondo que hd(p) > he(p) então existe um filho direito u de p. Por que necessariamente temos 
|hd(u) - he(u)| = 1? Por que não pode ser 2 ? Por que não pode ser 0 ? 
 
c- De acordo com o ítem b, quando hd(p) > he(p) existem dois sub-casos a serem considerados: 
he(u) = hd(u) + 1 ou hd(u) = he(u) + 1. 
Para cada um dos sub-casos acima, apresente a transformação que balanceia p ( diga qual e apresente 
um esquema ). Mostre que realmente todos os nós originalmente em T ficam balanceados (através da 
análise das alturas das subárvores). 
 
d- Por que o balanceamento de p (nó desbalanceado mais próximo das folhas ) regula toda a árvore ? 
 
3- Considere a árvore AVL a seguir: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
a) Realize, na árvore acima, as inserções das seguintes chaves 49, 60, 65. Mostre todas as rotações e o 
formato da árvore após cada operação. 
 
b) Seja q um nó recém-inserido e p o seu ancestral mais próximo que se tornou desbalanceado. Quais 
os possíveis valores para o fator de balanceamento de p após a inserção? Examinar o fator de 
balanceamento de p é suficiente para concluir se a inserção foi à esquerda ou a direita de p? Por 
que? 
 
 
 
 
 
30 
4 56 
4
1
2
3 43 50