A2 TADS4 Estrutura De Dados Teleaula 6 Tema 6 Impressao

05/09/2014

Estrutura de Dados
Tema 6: Árvores binárias. O que é uma árvore
Segundo Knuth (1973), uma árvore pode ser formalmente definida como sendo um conjunto finito T de um ou mais nós, onde:
a) existe um nó especialmente designado para ser a raiz de T; e
b) os demais nós são particionados dentro de m≥0 conjuntos disjuntos T1,T2,
..., Tm e cada um destes conjuntos torna-se uma árvore, chamada sub-árvores da raiz.

Características de uma árvore raiz:- o nó inicial da árvore;
Grau: o número de filhos que um nó possui;
Nível (ou profundidade): a distância de um nó até a raiz;
Altura: o maior nível encontrado na árvore
(altura de uma árvore com n nós pode variar de lg(n) até n-1;
Folha: o nó que não possui filho.

1

05/09/2014

Este nó está no nível
1 e possui grau 1.

raiz

Este nó está no nível
0 e possui grau 2.

6

9

Este nó está no nível
1 e possui grau 0.

14

Altura da árvore é
2

folha
25

Este nó está no nível
2 e possui grau 0.

folha

O que não é uma árvore
G

A

D

C

B
C

D

A

B

O que é uma árvore binária
Um conjunto de finito de elementos que pode estar vazio ou particionado em 3 subconjuntos disjuntos. A
C

B
D

2

05/09/2014

Árvore binária
• Em uma árvore binária os nós podem assumir grau 0, 1 ou 2;
• Em uma árvore binária completa, todos os nós possuem grau igual a 2;
• O número máximo de elementos em uma árvore de altura n é 2n.

Árvore binária de busca
Uma árvore binária de busca possui elementos menores que a raiz armazenados na sub-árvore da esquerda e elementos maiores que a raiz na sub-árvores da direita.
25
38

12
19

Árvore binária como um TDA
Características:
• Conjunto de elementos;
• Raiz para indicar o 1º elemento inserido
• Cada elemento deve indicar os seus descendentes 3

05/09/2014

Árvore binária de busca como um TDA
Operações:
• Inserir novo elemento
• Buscar um elemento
• Mostrar todos os elementos • Remover um elemento
• Contar elementos
• Calcular nível de um elemento Inserção de elementos em uma árvore binária de