arvores

Estruturas de Dados

Árvores
Prof. Eduardo Alchieri

Árvores
(introdução)




Importância de estruturas unidimensionais ou lineares (vetores e listas) é inegável
Porém, estas estruturas não são adequadas para representar dados que devem ser dispostos de maneira hierárquica


Por exemplo, diretórios criados em um computador

Um exemplo de estrutura de diretório no Windows 2000

Árvores
(introdução)


Árvore é uma estrutura de dado não linear adequada para representar hierarquias

Árvores
(definição)


Árvores


Dados são dispostos de forma hierárquica



Elementos (nós)


Raiz (pai) - [ancestrais]



Galhos (filhos) – [ancestrais/descendentes]



Folhas (terminais) - [descendentes]

Árvores
(definição)


Forma mais natural de definirmos uma estrutura de árvore é usando recursividade


Definição recursiva de árvores




Uma árvore é uma coleção de nós
A coleção pode estar vazia, ou consistir de um nó raiz R
Existe um arco direcionado de R para a raiz de cada subárvore: a raiz de cada subárvore é chamada de filho de R, da mesma forma R é chamado de pai da raiz de cada subárvore

Árvores
(definição)


Definição recursiva de árvores (outra forma de representar uma árvore) Árvores
(exemplos)


Exemplo de árvore

Quantas subárvores existem na árvore acima?
Quais são as subárvores?
Quais nós são as raízes das subárvores da árvore acima?
Quais nós são considerados nós internos?
Quais nós são considerados nós externos (folhas)?

Árvores
(subárvores)


Subárvores (visualização da definição recursiva)

Árvores
(subárvores)


Subárvores (visualização da definição recursiva)

Árvores
(terminologia)


Terminologia


Grau de um nó: número de subárvores relacionadas com o nó 

Folha: um nó de grau zero



Ordem: número máximo de galhos em um elemento









Caminho: sequência única de arcos que leva a um nó a