Estrutura De Dados - Arvore

Árvore:

Pode ser denominado como árvore um conjunto de nós onde:

 Existe um nó r, denominado raiz, com zero ou mais sub-árvores,

 Cujas raízes estão ligadas a r

 Os nós raízes destas sub-árvores são os filhos de r

 Os nós internos da árvore são os nós com filhos

 As folhas da árvore são os nós sem filhos

As árvores possuem níveis que iniciam-se sempre do nível 0, conforme a seguir:

Ordens de percurso

 pré-ordem:

• trata raiz, percorre sae, percorre sad

• exemplo: a b d c e f

ordem simétrica:

• percorre sae, trata raiz, percorre sad

• exemplo: b d a e c f

 pós-ordem:

• percorre sae, percorre sad, trata raiz

• exemplo: d b e f c a

• o valor associado à raiz é sempre maior que o valor associado a qualquer nó da sub-árvore à esquerda

• o valor associado à raiz é sempre menor ou igual (para permitir repetições) que o valor associado a qualquer nó da sub-árvore à direita

• quando a árvore é percorrida em ordem simétrica (subarvore esquerda - raiz – subarvore direita), os valores são encontrados em ordem não decrescente

As árvores podem ser classificadas como:

• Árvore Binária Completa – onde todas as folhas encontram-se em um único nível:

• Árvore Binária Quase Completa – onde todo nó que não é folha possui subárvores direitas e esquerdas:

• Árvore Estritamente Binária – onde todas as folhas estão no mesmo nível ou em um até nível acima: