arvore binariaa

Estruturas de Dados

Prof. Gustavo Willam Pereira
Créditos: Profa. Juliana Pinheiro Campos

ESTRUTURAS DE DADOS

Árvores

Conceitos
Árvores binárias
Árvores binárias de pesquisa
Árvores binárias balanceadas

ESTRUTURAS DE DADOS

Árvores
Estruturas de dados adequadas para a representação de hierarquias.
Exemplo: sistemas de arquivos em um computador
(armazenados em diretórios e subdiretórios);

ESTRUTURAS DE DADOS

Árvores
Uma árvore A é um conjunto finito de 0 ou mais elementos denominados nós.
Existe um nó r denominado raiz da árvore.

ESTRUTURAS DE DADOS

Árvores
Raiz da árvore
Nó raiz

Nós

ESTRUTURAS DE DADOS

Árvores
A forma mais natural de definir uma estrutura de árvore é usando a recursividade.
O nó r (raiz da árvore) contém 0 ou mais subárvores, cujas raízes são ligadas diretamente a
r.
Cada nó ligado diretamente a r é raiz de uma subárvore. Todo nó de uma árvore, é raiz de uma subárvore.

ESTRUTURAS DE DADOS

Árvores
Raiz da árvore
Subárvore A1

Nó raiz

...

Nós

ESTRUTURAS DE DADOS

Árvores
Raiz da árvore
Subárvore A1

Nó raiz

...

Subárvore A2

Nós

ESTRUTURAS DE DADOS

Árvores
Raiz da árvore
Subárvore A1

Nó raiz

...

Subárvore A2
Subárvore A3

Nós

ESTRUTURAS DE DADOS

Árvores
Estrutura de árvore
Nó raiz
Nó raiz
...
...

Subárvores

ESTRUTURAS DE DADOS

Árvores
O número de subárvores de um nó é denominado grau do nó.
O grau da árvore é definido como o maior grau dentre todos os seus nós.
Nó raiz
Grau do nó raiz = 3
...

Grau do nó x = 2
Grau da árvore = 3

ESTRUTURAS DE DADOS

Árvores
Uma árvore com 0 (zero) nós é uma árvore vazia. Os nós raízes das subárvores são ditos filhos do nó pai (r);
Nós internos: nós que possuem filhos (nós de grau > 0)
Nós externos (folhas): nós que não possuem filhos (nós de grau 0).

ESTRUTURAS DE DADOS

Árvores
Nós pais

Nó raiz

...

ESTRUTURAS DE DADOS

Árvores
Nó