Programação II
Prof. Mateus Raeder
Universidade do Vale do Rio dos Sinos
- São Leopoldo -
Árvores Binárias
• É uma árvore na qual os nós possuem no máximo 2
filhos
– 0, 1 ou 2 filhos
– Grau máximo: 2
• É formada por nós que possuem um valor
associado, um ponteiro para a direita e um
ponteiro para a esquerda
Programação II – Prof. Mateus Raeder
Árvores Binárias
Árvore binária
x
Árvore não-binária
A
A
B
D
E
E
F
H
B
C
D
F
G
G
I
C
I
H
J
Programação II – Prof. Mateus Raeder
Árvores Binárias
• O nó A é a raiz da árvore
• Como B é a raiz da sub-árvore
esquerda de A, dizemos que B é
o filho esquerdo de A
• Do mesmo modo, C é o filho
direito de A
• Por isso A é o pai dos nós B e C
e estes dois são irmãos
• O mesmo ocorre para todos os
demais nodos
A
B
D
C
E
Programação II – Prof. Mateus Raeder
G
Tipos de Árvores Binárias
• Estritamente Binária
A
– Ocorre quando todo nó que não é
folha tiver sub-árvores esquerda e
direita não vazias.
– Ou seja: todo nó tem 0 ou 2 filhos.
• Número de nós em uma árvore
estritamente binária com n
folhas: 2n-1
B
D
C
E
F
H
G
I
Programação II – Prof. Mateus Raeder
Tipos de Árvores Binárias
• Binária Completa
– É uma árvore estritamente binária,
na qual todos os nós folha estão ou
no penúltimo ou no último nível
A
B
D
C
E
Programação II – Prof. Mateus Raeder
Tipos de Árvores Binárias
• Binária Cheia
– É uma árvore estritamente binária, na qual todos os nós
folha estão no último nível
A
Embora possua muitos
nós, a distância
da raiz até os nós é
relativamente baixa
B
C
D
H
E
I
J
F
K
L
G
M
N
Programação II – Prof. Mateus Raeder
O
Árvores Binárias
• Representação
Referência para
filho da direita
Referência para
filho da esquerda
A
A
B
D
C
E
F
B
G
D
C
F
E
Dado do nó
Programação II – Prof. Mateus Raeder
G
Árvores Binárias
• Representação de expressões aritméticas em
árvores binárias
– Dada uma expressão aritmética, sua representação
em árvore binária é feita de tal forma que a ordem de
prioridade das operações fica implícita.
Regra:
• O operador de menor prioridade aparece na raiz;
• A sub-expressão à esquerda desse operador dá origem
à sub-árvore esquerda;
• A sub-expressão à direita do operador dá origem à subárvore direita.
Programação II – Prof. Mateus Raeder
Árvores Binárias
• Representação de expressões aritméticas em
árvores binárias
+
*
3
(3 * 7) + (6 / 10)
/
7
6
10
Operandos SEMPRE aparecem como folhas
Operadores NUNCA são folhas
Programação II – Prof. Mateus Raeder
Árvores Binárias
• Caminhamentos em árvores:
– Em pos-ordem
– Em in-ordem
– Em pré-ordem
Programação II – Prof. Mateus Raeder