Aula Arvore

Á r v o r es

Á r v o r es

Roteiro







Terminologia Básica
Representação em Memória
Árvores Binárias
Representação de Árvores Binárias
Caminhamento em Árvores Binárias
Árvores Binárias de Pesquisa

Árvores


Terminologia Básica
– Conceito: As árvores são estruturas de dados capazes de representar o relacionamento hierárquico entre diversas informações.
– Exemplos
 Árvore



genealógica de uma família
Organograma de uma empresa
Árvore estrutural de um povo

Árvores
Proto-indo-europeu

Helênico

Itálico

Grego
Osco-umbriano

Latino

Germânico

Norte
Germânico

Oscano Umbriano
Francês

Romeno

Oeste
Germânico

Árvore


Terminologia Básica
– 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
Sub-árvore
Sub-árvore

Raiz
Raiz

Árvores


Terminologia Básica
– A definição de árvore é recursiva.
– A exigência que T1, T2, ... , TN sejam disjuntos proíbe que as subárvores jamais sejam interligadas. Resultado: cada item numa árvore é a raiz de alguma sub-árvore total.

Árvores


Terminologia Básica
– Cada nó representa o fator da informação e mais os ramos que os ligam a outros nós (nós-filhos)
Ramo

Nó

Árvore


Terminologia Básica
– Grau de um nó é o número de subárvores desse nó. Grau 3
Grau 2

Grau 1

Árvore


Terminologia Básica
– 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ão-folhas ou nós nãoterminais.

Árvores

Grau 0

Grau 0

Árvore


Terminologia Básica
– Grau da árvore é o maior grau de seus nós constituintes Grau da árvore: 3

Árvore


Terminologia Básica
– Nomenclaturas adicionais
 nós



nó pai de...

 nós



filhos de...

irmãos de...

nós ancestrais