Aula Uea Final

Estrutura de Dados – Árvores
Prof. Tiago Eugenio de Melo, MSc [e-mail] material de referência

http://www.tiagodemelo.info/aulas

1

Roteiro


Motivação



Representação de árvores



Definição



Terminologia



Árvores binárias



Árvores balanceadas



Árvore binária de busca



Exercícios

2

Motivação




Diversas aplicações necessitam de estruturas mais complexas que as listas estudadas até agora, como listas e filas. Diversos problemas podem ser modelados através de árvores.

3

Representação


Existem três formas de representação:
−

Por parênteses aninhados:
( A (B) ( C (D (G) (H)) (E) (F (I)) ) )

−

Diagrama de inclusão:

4

Representação
−

Representação hierárquica

5

Definição


Uma árvore é um conjunto finito de elementos denominados nós ou vértices tais que:
−

T = 0 é a árvore dita vazia ou

−

existe um nó especial r, chamado raiz de T; os restantes constituem um único conjunto vazio ou são divididos em m (deve ser maior ou igual a 1) conjuntos distintos não vazios que são as subárvores de r, cada subárvore a qual é, por sua vez, uma árvore.

6

Exemplo de árvore


Considere a seguinte expressão aritmética:
(a + (b * (c / d) – e))

7

Terminologia


Subárvore:
−



Grau:
−



O número de subárvores de um nó é o grau daquele nó.

Folha:
−

Cada nó da árvore é a raiz de uma subárvore.

Um nó de grau igual a zero é denominado folha ou nó terminal.

8

Terminologia


Nível:
−



Altura:
−

O nível do nó é definido da seguinte forma: a raiz da árvore tem nível 0, enquanto o nível dos demais nós é igual ao número de linhas que o liga à raiz,
i.e., é o comprimento do caminho que vai da raiz até este nó.

É definida como sendo o nível mais alto da árvore.

9

Terminologia


Exemplo:

Nó
A
B
C
D
E
F

A

B

C

D

Grau
2
0
2
0
1
0

Nível
0
1
1
2
2
3

E

F A altura da árvore é igual 3, pois corresponde ao nível mais alto

10

Terminologia