Programação II
Prof. Mateus Raeder
Universidade do Vale do Rio dos Sinos
- São Leopoldo -
Árvores
• Não são estruturas como as listas
– Ou seja, não são estruturas lineares
• Árvores são estruturas hierárquicas
• São utilizadas para representar:
–
–
–
–
–
–
sistemas de arquivos
interfaces gráficas (organização dos menus, por exemplo)
organização das páginas de um site
partidas de um torneio
organização de cargos ou setores de uma empresa
forma de avaliação de expressões aritméticas, etc.
Programação II – Prof. Mateus Raeder
Árvores
• Exemplos de utilização de árvores
– Sistema de arquivos
C:\
Músicas:\
Calipso:\
Unisinos:\
Belo:\
Jogos:\
Prog_II:\
Lista_01:\
Lista_02:\
Programação II – Prof. Mateus Raeder
Árvores
• Exemplos de utilização de árvores
– Hierarquia de classes
Figura
Triangulo
Equilátero
Isósceles
Quadrado
Trapézio
Circulo
Escaleno
Programação II – Prof. Mateus Raeder
Árvores
• Exemplos de utilização de árvores
– Hierarquia de classes
Bebida
Alcoólica
Não-alcoólica
Whisky
Cerveja
Gin
Bohemia
Skol
Polar
Programação II – Prof. Mateus Raeder
Árvores
• Exemplos de utilização de árvores
– Árvores de derivação
-
+
5
+
x
12
y
(5 + x) – (12 + y)
Programação II – Prof. Mateus Raeder
Árvores
• Exemplos de utilização de árvores
– Ordenar valores
7
4
27
15
8
31
22
Programação II – Prof. Mateus Raeder
Árvores
• Terminologia
Raiz
A
B
D
C
E
F
G
Programação II – Prof. Mateus Raeder
Árvores
• Terminologia
A
Sub-árvore
Sub-árvore
B
D
C
E
F
G
Programação II – Prof. Mateus Raeder
Árvores
• Que árvore é esta?
Uma árvore sem nós é uma
árvore vazia
Programação II – Prof. Mateus Raeder
Árvores
• Definição de árvore
– Uma árvore enraizada T (ou simplesmente uma árvore) é
um conjunto finito de elementos denominados nós ou
vértices tais que:
• T = 0 é a árvore dita vazia ou
• existe um nó especial r, chamado raiz de T
• os restantes constituem um único conjunto vazio ou são
divididos em m conjuntos distintos não vazios que são as subárvores de r
• cada sub-árvore é, por sua vez, uma árvore
Programação II – Prof. Mateus Raeder
Árvores
• Terminologia
– Considere o nodo “O”
“P” é dito PAI de “O”
P
O
“F” é dito
FILHO de “O”
I
“I” é dito
IRMÃO de “O”
F
Programação II – Prof. Mateus Raeder
Árvores
• Terminologia
– GRAU de um nó: é o número de sub-árvores que ele possui
– FOLHA (ou Terminal): é um nó com grau igual a 0
– GRAU DA ÁRVORE: grau máximo entre os nós
Grau 3
A
Grau 1
B
C
D
Grau 2
= Folhas
Grau 0
E
F
H
G
I
Grau 0
Programação II – Prof. Mateus Raeder
Árvores
• Terminologia
– FLORESTA: um conjunto de árvores disjuntas
Árvore 2
Árvore 1
A
A
Árvore 4
B
B
C
D
D
C
Árvore 3
D
F
B
E
H
Programação II – Prof. Mateus Raeder
G
I
Árvores
• Terminologia
– Pode existir uma Floresta vazia?
Árvore 2
Árvore 1
Árvore 4
Árvore 3
Programação II – Prof. Mateus Raeder
Árvores
• Terminologia
– CAMINHO: sequência de nós distintos, tal que existem
sempre nós consecutivos que possuam entre si a relação
“é filho de” ou “é pai de”
– COMPRIMENTO do caminho?
A
Número de nós no caminho - 1
B
C
- A alcança G
- G é alcançado por A
- Comprimento: 3
D
F
Programação II – Prof. Mateus Raeder
E
G
Árvores
• Terminologia
– NÍVEL de um nó: número de nós entre ele e a raiz
(contando ele próprio)
– ALTURA (ou Profundidade) da árvore: é o seu maior nível
Nível 1
A
B
Nível 2
C
ALTURA = 4
D
F
E
G
Nível 3
Nível 4
Programação II – Prof. Mateus Raeder
Árvores
• Operações básicas sobre árvores
A
– criação da árvore
– inserção de um novo nodo
• a raiz
• como folha
• em posição intermediária
B
– exclusão de um determinado nodo
– acesso a um nodo
• determinar forma de percorrer a árvore
D
C
E
– destruição da árvore
F
H
G
I
Programação II – Prof. Mateus Raeder