Árvores e
Árvores Binárias
Prof. Luiz José Hoffmann Filho
[email protected]
Roteiro
• Contextualização
• Árvores
• Árvores Binárias
Roteiro
• Contextualização
• Árvores
• Árvores Binárias
Contextualização
• Importância de estruturas unidimensionais
lineares (vetores e listas) é inegável.
ou
• Contudo, elas não são adequadas para
representar dados que devem ser dispostos de
maneira hierárquica.
• Por
exemplo,
computador.
diretórios
criados
em
um
Exemplo de estrutura hierárquica
Um exemplo de estrutura de diretório no Windows 2000
Roteiro
• Contextualização
• Árvores
• Árvores Binárias
Árvores
• Árvore é uma estrutura de dado adequada para
representar hierarquias.
• Forma mais natural de definirmos uma estrutura de
árvore é usando recursividade.
Definições
• Uma árvore é composta de um conjunto finito
de nós.
• Desse conjunto, há um nó r denominado de raiz,
que contém zero ou mais sub-árvores, cujas
raízes são ligadas diretamente a r.
• Esses nós raízes das sub-árvores são ditos filhos
do nó pai, r.
• Nós com filhos são comumente chamados de
nós internos.
• Nós que não têm filhos são chamados de nós
externos (folhas).
Estrutura de árvores
Exemplos de árvores (1/2)
raiz da árvore
A
B
E
C
F
L
A
B
D
G
H
I
M
C
A
D
J
N
Quantas sub-árvores existem na árvore acima?
Quais são as sub-árvores?
Quais nós são as raízes das sub-árvores da árvore acima?
Quais nós são considerados nós internos?
Quais nós são considerados nós externos (folhas)?
Exemplos de Árvores (2/2)
Desktop
My Documents My Computer
Recycle Bin
3½ Floppy(A:)
Compact Disk (E:)
Local Disk (C:) Local Disk (D:)
Network
Removable Disk (F:)
Local Disk (I:) Local Disk (J:) Control Panel
Apostila
Parte I
Parte II
Parte III
Propriedade Fundamental de Árvores
• Existe um único caminho da raiz para
qualquer nó da árvore.
• Portanto, podemos definir a altura de
todas as árvores como sendo o
comprimento do caminho mais longo da
raiz até uma das folhas.
• Por definição, a altura de uma árvore
que possui somente um elemento é zero.
Exemplo de altura em árvores
Desktop
My Documents My Computer
A
B
E
C
F
Network
Recycle Bin
D
G
H
I
J
Local Disk (C:) Local Disk (D:)
L
M
3½ Floppy(A:)
Compact Disk (E:)
Removable Disk (F:)
N
árvore A1
Local Disk (I:) Local Disk (J:) Control Panel
Apostila
Parte I
Parte II
Parte III
árvore A2
Qual a altura da árvore A1?
Qual a altura da árvore A2?
Roteiro
• Contextualização
• Árvores
• Árvores Binárias
Árvores Binárias (AB)
• Uma árvore binária é constituída de um conjunto
finito de nós.
• Cada nó pode ter no máximo dois filhos.
• De maneira recursiva, podemos definir uma árvore
binária como sendo:
o uma árvore vazia; ou
o um nó raiz tendo duas sub-árvores, identificadas
como a sub-árvore da direita (sad) e a subárvore da esquerda (sae).
Representação Esquemática de AB
Representação esquemática da definição da estrutura de AB
Exemplo Árvore Binária
raiz da árvore
8
raiz da sae
raiz da sad
2
3
4
13
1
5 11
9
7
Notação Textual de Árvore Binária
Exemplo de árvore binária
Árvore vazia é representada por <>, e árvores não vazias por <raiz sae sad>.
Com esta notação, a árvore ilustrada acima é representada por:
<a <b<><d<><>>> <c<e<><>><f<><>>> >
Verificando a altura das árvores
1
nível 0
2
nível 1
nível 2
nível 3
5
4
8
3
6
Qual a altura da árvore binária ao lado ?
7
9 10
Qual a altura da árvore binária ao lado ?
Em qual nível está o nó C?
Percursos em Árvores Binárias
• Muitas operações em árvores binárias envolvem
o percurso de todas as suas sub-árvores,
executando alguma ação de tratamento em
cada nó.
• É comum percorrer uma árvore em uma das
seguintes ordens:
o Pré-Ordem: tratar raiz, percorrer sae, percorrer sad;
o Em-Ordem (ordem simétrica): percorrer sae, tratar raiz,
percorrer sad;
o Pós-Ordem: percorrer sae, percorrer sad, tratar raiz.
Pré-Ordem
• Imprima
os
valores
presentes nos nós da árvore
ao
lado,
segundo
a
condição pré-ordem (tratar
raiz,
percorrer
sae,
percorrer sad).
34
80
40
55
43
13
5
75
26
90
Resultado: 34, 80, 40, 43, 13, 26, 90, 75, 55, 5, 1, 17.
1
17
Em-Ordem (Ordem Simétrica)
• Imprima
os
valores
presentes nos nós da árvore
ao
lado,
segundo
a
condição ordem simétrica
(percorrer sae, tratar raiz,
percorrer sad).
34
80
40
55
43
13
5
75
26
90
Resultado: 40, 80, 26, 90, 13, 43, 75, 34, 55, 1, 5, 17.
1
17
Pós-Ordem
• Imprima
os
valores
presentes nos nós da
árvore ao lado, segundo
a condição pós-ordem
(percorrer sae, percorrer
sad, tratar raiz).
34
80
40
55
43
13
5
75
26
90
Resultado: 40, 90, 26, 13, 75, 43, 80, 1, 17, 5, 55, 34.
1
17
Aplicações de Árvores Binárias (1/2)
• Como árvores binárias de pesquisa (busca)
Aplicações de Árvores Binárias (2/2)
• Análise de expressões algébricas: prefixa,
infixa e pósfixa.
Prefixa: + * + 3 6 – 4 1 5 = 32
Infixa: 3 + 6 * 4 – 1 + 5 = 32
Pósfixa: 3 6 + 4 1 - * 5 + = 32
Definição da Estrutura de Árvores Binárias
• Como definir o Tipo Abstrato de Dados
(TAD) que representa árvores binárias?
• Há duas formas:
o Estática;
o Dinamicamente;
Representação Dinâmica
• Criar um registro contendo os seguintes campos:
info, sae e sad.
• Este registro é auto-referenciado através dos
campos sae e sad.
struct arv {
int info;
struct arv* sae;
struct arv* sad;
};
typedef struct arv Arv;
Registro dos nós de uma AB
info
sae
sad
Principais funções sobre AB
•
•
•
•
•
•
•
•
•
Iniciar árvores como vazias;
Inserir nós na árvore;
Verificar se árvore está vazia;
Informar a altura da árvore;
Pesquisar ocorrência de um valor no nó da árvore;
Liberar estrutura alocada para as árvores;
Percorrer a árvore em pré-ordem;
Percorrer a árvore em em-ordem (ordem simétrica);
Percorrer a árvore em pós-ordem.