programação

AED – Algoritmos e Estruturas de Dados
Roberto de Souza Porto
Árvores Binárias
AED –

Alg. e Est. de Dados

Roberto de Souza Porto

Árvores Binárias

Introdução
• São árvores ordenadas.
• Possuem grau igual a 2.

AED –

Alg. e Est. de Dados

Roberto de Souza Porto

Árvores Binárias

Representação Gráfica
A
B
D
AED –

Alg. e Est. de Dados

C
E
Roberto de Souza Porto

F
Árvores Binárias

Representação Gráfica do Nó
NÓ
ESQ
INFO
DIR
Ponteiro Informação Ponteiro

AED –

Alg. e Est. de Dados

Roberto de Souza Porto

Árvores Binárias

Comparação entre Árvores
Binárias
A
B
B
Iguais
AED –

Alg. e Est. de Dados

A

A

A

B

B

Diferentes
Roberto de Souza Porto

Árvores Binárias

Número Máximo de Nós de uma Árvore Binária T
• Seja K a sua profundidade.
2 ^ (K+1) - 1,

AED –

Alg. e Est. de Dados

K>=0

Roberto de Souza Porto

Árvores Binárias

Construção de Árvores Binárias
• Um ponteiro chamado Raiz aponta para o primeiro nó(raiz).

• Se raiz = Nil  árvore vazia.
AED –

Alg. e Est. de Dados

Roberto de Souza Porto

Árvores Binárias

Construção de Árvores
Binárias - Ciclo de Inserções
1o. Passo: inserir a 1a.
Informação no nós raiz.
2o. Passo: cada nova informação é comparada com o nó raiz.
AED –

Alg. e Est. de Dados

Roberto de Souza Porto

Árvores Binárias

Construção de Árvores
Binárias – Ações do passo 2
2.1 – Se menor visitar a sub-árvore a esquerda.
2.2 – Se maior visitar a sub-árvore a direita.
2.3 – Se sub-árvore vázia inserir novo nó.
AED –

Alg. e Est. de Dados

Roberto de Souza Porto

Árvores Binárias

Exercício
• Crie um árvore binária para os valores abaixo:

30,16,41,22,37,18,51,15,39
AED –

Alg. e Est. de Dados

Roberto de Souza Porto

Árvores Binárias

Solução do Exercício
30

16
15

41
22

37

18
AED –

Alg. e Est. de Dados

51
39

Roberto de Souza Porto

Árvores Binárias