3 - ARVORES COM EXERCICIOS

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
DEQ/EE3 – FUNDAMENTOS DA ESTRUTURA DA INFORMAÇÃO
Departamento de Engenharia Química
Universidade Estadual de Maringá
Leonardo F. Costa
*
*
ÁRVORES
Introdução
Definições e Representações Básicas
Árvores Binárias
Percurso em Árvores Binárias
Conversão de uma Floresta
*
*
Conversão de uma árvore qualquer para árvore binária
Por que converter árvores m-árias em binárias?
Otimização de alocação de memória
Mais fáceis de serem manipuladas
Implementação de operações são simplificadas
Não aumenta a quantidade de nós
Pode ser revertida a qualquer momento
*
*
Processo de Conversão
Seja T uma árvore qualquer. T é convertida em uma árvore binária B(T) da seguinte maneira. B(T) possui um nó B(v), para cada nó v de T. As raízes de T e B(T) coincidem.
O filho esquerdo de um nó B(v) em B(T) corresponde ao primeiro filho de v em T, caso exista. Se não existir, a subárvore esquerda de B(v) é vazia.
O filho direito de um nó B(v) em B(T) corresponde ao irmão de v em T, localizado imediatamente à sua direita, caso exista. Se não existir, a subárvore direita de B(v) é vazia.
*
*
Exemplo
A
C
B
D
F
E
*
*
Conversão de Florestas
Para converter uma floresta em uma árvore binária, basta considerar as raízes das árvores da floresta com sendo irmãos e aplicar a conversão anterior.
*
*
A
C
B
D
F
E
*
*
A
C
B
D
F
E
G
H
I
J
K
L
M
*
*
Exercícios
Ache a raiz de cada uma das seguintes árvores binárias
Percurso pós-ordem: FCBDG
Percurso pré-ordem: IBCDFEN
Percurso in-ordem: CBIDFGE
2. Para a árvore binária a seguir:
Ache o grau para cada um dos nós
Determine os nós folhas
Complete a árvore binária com tantos nós quantos forem necessários para transformá-la em árvore binária cheia
*
*
Exercícios
*
*
Exercício
3. Converter a árvore apresentada a seguir em árvore binária
Inserir os nós P e Q como filhos de Z
Excluir os nós O e M
Inserir os nós R e S como filhos de L
Inserir V como filho esquerdo de C
2. Considerando a árvore binária gerada, executar as seguinte operações:
Inserir o nó X como filho a direita de A
Inserir os nós Y e Z como filhos de X
*
*
EXERCÍCIOS
3.5 – Mostrar a equivalência entre as representações de uma árvore através do diagrama de inclusão e de parênteses aninhados.
3.6 – Representar através de uma árvore, a seguinte expressão aritmética
*
*
EXERCÍCIOS
3.9 – Provar:
Numa representação de árvores pelo método das barras
As barras correspondentes a nós irmãos ocorrem necessariamente em linhas consecutivas
O comprimento da barra correspondente a um nó v é maior do que o de um nó w se e somente se v for ancestral próprio de w.
*
*
3.17 – Seja um percurso definido pelas seguintes operações:
Ordem A
visitar a raiz
percorrer a subárvore esquerda de v na ordem A
percorrer a subárvore direita de v na ordem B
Ordem B
percorrer a subárvore esquerda de v na ordem B
visitar a raiz
percorrer a subárvore direita de v na ordem A
Supondo que o processo se inicie pela raiz da árvore, em ordem A, escrever o percurso final obtido quando o algoritmo for aplicado a árvore ao lado.
*
*
EXERCÍCIOS
3.31 – O percurso de uma árvore em pré-ordem resultou na impressão da sequência:
A B C F H D L M P N E G I
E o percurso da mesma árvore em ordem simétrica resultou em:
F C H B D L P M N A I G E
Construa uma árvore que satisfaça estes percursos