teste

Á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
d d d d
B
D
C
d d d d
E
F
H
G d
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

d d d d

B

C

D

A

d d d d

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

d d d d

B

E

d d

F

d

I

D

C

d d
J

G

K

H

L

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

d d d d