Arvores

ESTRUTURAS DE DADOS NÃO LINEARES

Anteriormente fizemos revisões sobre estruturas lineares (pilha e fila)., isto é, estruturas que guardam colecções de objectos que são acedidos sequencialmente. Efectivamente são chamadas lineares porque cada objecto tem um único sucessor.

Em muitas aplicações a organização dos objectos apresenta-se não linear, dado que qualquer membro pode apresentar múltiplos sucessores. Estudaremos árvores e grafos.

ÁRVORES

Neste tipo de estruturas os elementos não se ligam entre si através de uma relação anterior-seguinte (caso das estruturas lineares), mas existe uma relação organizacional mais rica, uma relação hierárquica, são portanto estruturas hierarquizadas. Este tipo de estrutura representa por exemplo, o organigrama de uma empresa, uma árvore genealógica, ...um livro, por exemplo, também podemos considerá-lo como estruturado em árvore, ver a figura abaixo:

Definição e Terminologia

A terminologia deste tipo de estrutura é uma terminologia intuitiva que se baseia em árvores de família, com os termos "pai", "filho", "ascendentes", "descendentes"...
Árvore é assim um tipo abstracto de dados que guarda os elementos (nós) hierarquicamente.
Na representação gráfica de árvores os nós ligam-se por ramos....

Com excepção do elemento de topo, cada elemento tem um elemento pai e zero ou mais elementos filhos. O elemento de topo é designado por raiz. Assim, este elemento não tem elemento pai nem obviamente ascendentes.

Por sua vez os elementos que não possuem filhos são designados por folhas. Os outros nós da árvore dizem-se interiores.

Por sua vez cada elemento numa árvore é a raiz da subárvore que é definida pelo nó e todos os descendentes do nó.

Exemplo: descendentes do nó 70 são 60 e 75.

O movimento de um nó para os seus descendentes faz-se através de um único caminho.
Os ascendentes de um nó X são todos os nós que existem no caminho desde esse nó até à raiz.
Exemplo: ascendentes do nó 85 são 90 e 80.

Define-se