Arvores

Árvores e Árvores Binárias
Siang Wun Song - Universidade de São Paulo - IME/USP

MAC 5710 - Estruturas de Dados - 2008

Siang Wun Song - Universidade de São Paulo - IME/USP

Árvores e Árvores Binárias

Referência bibliográfica

Os slides sobre este assunto são parcialmente baseados nas seções sobre árvores do capítulo 4 do livro
N. Wirth. Algorithms + Data Structures = Programs.
Prentice Hall, 1976.

Siang Wun Song - Universidade de São Paulo - IME/USP

Árvores e Árvores Binárias

Árvore
Uma árvore do tipo T é constituída de uma estrutura vazia, ou um elemento ou um nó do tipo T chamado raiz com um número finito de árvores do tipo T associadas, chamdadas as sub-árvores da raiz.
A
❅ ❅ ❅ ❅
B
D
C
❅ ❅ ❅ ❅
E
F
H
G ❅
J
I
K
L

Siang Wun Song - Universidade de São Paulo - IME/USP

Árvores e Árvores Binárias

Nomenclatura: árvore ordenada
Uma árvore é chamada ordenada quando a ordem das subárvores é significante. Assim, as duas árvores ordenadas seguintes são diferentes.
A

❅
❅

❅ ❅

B

C

D

A

❅ ❅ ❅ ❅

C

D

B

Numa árvore que representa os descendentes de uma família real, a ordem das subárvores pode ser importante pois pode determinar a ordem de sucessão da coroa.
Siang Wun Song - Universidade de São Paulo - IME/USP

Árvores e Árvores Binárias

Nomenclatura: pai, filho, nível
A

❅
❅

❅ ❅

B

E

❅

I

J

D

C

❅ ❅

❅ ❅

F

G

K

L

H

Pai e filho: Um nó y abaixo de um nó x é chamado filho de x. x é dito pai de y . Exemplo: B é pai de E e F.
Irmão: Nós com o mesmo pai são ditos irmãos. Exemplo: B, C,
D são irmãos.
Nível de um nó: A raiz de uma árvore tem nível 1. Se um nó tem nível i, seus filhos têm nível i + 1. Exemplo: E, F, G e H têm nível 3.
Siang Wun Song - Universidade de São Paulo - IME/USP

Árvores e Árvores Binárias

Nomenclatura: altura, folha, grau
A

❅
❅

❅ ❅

B

E

❅

I

J

D

C

❅ ❅

❅ ❅

F

G

K

L

H

Altura ou profundidade de uma árvore: É o máximo nível de seus nós. A árvore do exemplo tem altura