2 - ARVORES

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
*
*
ÁRVORES BINÁRIAS
Árvores binárias são estruturas do tipo árvore onde cada nó pode ter no máximo duas sub-árvores – o grau de cada nó pode ser 0, 1 ou 2.
A raiz da subárvore esquerda de um nó v, se existir, é denominada filho esquerdo de v.
A raiz da subárvore direita de um nó v, se existir, é denominada filho direito de v.
*
*
ÁRVORES BINÁRIAS
Naturalmente, o esquerdo pode existir sem o direito e vice-versa.
T(v) indica a subárvore binária cuja raiz é v e cujas subárvores esquerda e direita de T são TE(v) e TD(v), respectivamente.
*
*
O nó A é a raiz de T
Subárvore binária esquerda de T: TE(A)
Subárvore binária direita de T: TD(A)
Raiz de TE(A): B
Raiz de TD(A): C
O filho esquerdo de A é o nó B
O filho direito de A é o nó C
O nó B possui o nó D como filho esquerdo, mas não possui filho direito
*
*
Estas duas árvores são idênticas?
*
*
Estas duas árvores são idênticas?
Se forem árvores, sim.
Se forem árvores binárias, não.
*
*
Toda árvore binária com n nós possui exatamente n+1 subárvores vazias entre suas subárvores esquerdas e direitas
9 nós e 10 subárvores vazias
*
*
Tipos Especiais de Árvores Binárias
Árvore estritamente binária:
Cada nó possui 0 ou 2 filhos.
 Não existe nó com apenas 1 filho
*
*
Tipos Especiais de Árvores Binárias
Árvore binária completa:
É uma árvore estritamente binária (grau 0 ou 2), nos quais seus nós folhas podem estar apenas no penúltimo e último nível
*
*
Tipos Especiais de Árvores Binárias
Árvore binária cheia:
É aquela que todos os nós, exceto os nós do último nível tem duas subárvores
Toda árvore binária cheia é completa e estritamente binária.
*
*
Relação entre a altura de uma árvore binária e o seu número de nós
A árvore binária que possui altura máxima é aquela cujos nós interiores possuem exatamente uma subárvore vazia.
Estas árvores são denominadas zigue-zague e sua altura é sempre igual a n.
*
*
Subárvore parcial
Seja T uma árvore (ou árvore binária), e v um nó de T.
Seja T(v) a subárvore de T de raiz v, e S um conjunto de nós de T(v) tal que T(v) – S é uma árvore.
A árvore T’ = T(v) – S é chamada subárvore parcial de raiz v
A diferença entre uma subárvore de raiz v e uma subárvore parcial de raiz v é que a primeira contém obrigatoriamente todos os descendentes de v, enquanto a segunda, não necessariamente
*
*
Subárvore parcial
Árvore T
Subárvore T de raiz E. T(E)
Subárvore parcial de T de raiz E. T(E)-S
*
*
Árvore Binária ordenada
É aquela em que todo nó tem chave maior do que a dos seus descendentes a esquerda e menor que a chave dos seus descendentes a direita
*
*
ÁRVORES
Introdução
Definições e Representações Básicas
Árvores Binárias
Percurso em Árvores Binárias
Conversão de uma Floresta
*
*
Percurso em Árvores Binárias
Percurso: visita a cada um dos nós de uma árvore binária.
O percurso é uma das operações básicas relativas à manipulação de árvores.
Visitar um nó significa operar, de alguma forma, com a informação a ele relativa.
Imprimir, atualizar suas informações, etc.
*
*
Percurso em Árvores Binárias
Em geral, percorrer uma árvores significa visitar os seus nós exatamente uma vez.
Contudo, no processo de percorrer a árvore pode ser necessário passar várias vezes por alguns de seus nós, porém, sem visitá-los.
*
*
Algorítmos de Percurso
Um dos passos de qualquer algorítmo de percurso é visitar a raiz v de cada subárvore da árvore T
Após a visita a raiz v, percorre-se as subárvores esquerda e direita de v, para cada nó v de T.
Essas 3 operações (visitar e percorrer as subárvores esquerda e direita) compõem um algorítmo.
Resta definir em que ordem.
*
*
Percurso em pré-ordem
Passos:
visitar a raiz
percorrer sua subárvore esquerda, em pré-ordem
percorrer sua subárvore direita, em pré-ordem
A
B
D
G
C
E
H
I
F
*
*
Algoritmo não recursivo para percurso em pré-ordem
A versão não recursiva deve manter sempre atualizados os caminhos percorridos a partir da raiz da árvore.
Uma das formas de se armazenar estas informações é a utilização de uma pilha.
O nó só é retirado da pilha quando for concluída as visitas às subárvores relativas a este nó.
Portanto, informação do sentido do percurso também deverá ser armazenada.
*
*
Percurso em ordem simétrica
O percurso em ordem simétrica é muito utilizado para árvores binárias de busca.
Para cada uma das subárvores, segue os seguintes passos:
percorrer sua subárvore esquerda, em ordem simétrica
visitar a raiz
percorrer sua subárvore direita, em ordem simétrica
*
*
Percurso em ordem simétrica
percorrer sua subárvore esquerda, em ordem simétrica
visitar a raiz
percorrer sua subárvore direita, em ordem simétrica
G
D
B
A
H
E
I
C
F
*
*
Percurso em pós-ordem
Passos:
percorrer sua subárvore esquerda, em pós ordem
percorrer sua subárvore direita, em pós ordem
visitar a raiz
G
D
B
H
I
E
F
C
A
Da esquerda para a direita de baixo para cima
*
*
Percurso em nível
A árvore é percorrida de cima para baixo da esquerda para a direita (sentido da escrita)
A
B
C
D
E
F
G
H
I
*
*
Exemplo de percursos
In ordem = simétrica
*
*
Estrutura de ponteiros
Cada nó deve possuir dois campos de ponteiros, esq e dir, que apontam para as suas subarvores esquerda e direita respectivamente
O ponteiro ptraiz indica a raiz da árvore
Necessita-se de 2n +1 unidades de memória para representar uma árvore binária com n nós.
*
*
Estrutura de ponteiros usada no armazenamento da árvore binária
*
*
ÁRVORES
Introdução
Definições e Representações Básicas
Árvores Binárias
Percurso em Árvores Binárias
Conversão de uma Floresta
*