Arvores binarias

ESTRUTURA DE DADOS
ÁRVORES

ÁRVORES

ÁRVORES

Definição
• Uma árvore é um conjunto finito de um ou mais nós de tal natureza que:
• Existe um nó especialmente designado denominado raiz;
• Os nós restantes estão desdobrados em N conjuntos separados (N >= 0) T1, T2, ... , TN, em que cada um dos conjuntos se constitui uma árvore (denominadas de sub-árvores da raiz).

ÁRVORES

Árvores
• São estruturas de dados adequadas para a representação de hierarquias.
• Uma árvore é composta por um conjunto de nós.
• Existe um nó r, denominado raiz, que contém zero ou mais subárvores, cujas raízes são ligadas diretamente a r.

• A raiz se liga a um ou mais elementos, e cada um destes forma uma nova subárvore. Esses elementos são seus galhos ou filhos.

ÁRVORES

RAIZ

FOLHAS

QUAIS SÃO?

FOLHAS

GRAU DE UM NÓ

QUAIS SÃO?

GRAU DE UM NÓ

Definição Recursiva
• Os nós cujo grau é igual a ZERO são denominados de nós-folhas ou nó terminal.
• – Os nós intermediários são, por conseqüência, denominados de nós nãofolhas ou nós nãoterminais.

NÍVEL DE UM NÓ

INDIQUE!

NÍVEL DE UM NÓ

Altura Da Árvore

Qual Seria?

Altura Da Árvore

FLORESTA

Qual Seriam?

FLORESTA

Como representar, em memória, uma árvore ?

Como representar, em memória, uma árvore ?

Podemos utilizar o mesmo conceito que utilizamos em listas ligadas e, por meio de ponteiros, representar o relacionamento existente um nó e seus nós-filhos.

Como representar, em memória, uma árvore ?

Representação de árvores binárias

Árvores Binárias
• É um conjunto finito de nós, que se apresenta vazia ou que consiste de uma raiz e de, no máximo, duas árvores binárias separadas, denominadas de subárvore esquerda e subárvore direita.

Representação de árvores binárias

Tipos especiais de árvores binárias

Tipos especiais de árvores binárias

Árvores binárias

Árvores binárias

A operação de inserção
• A operação