Estrutura de dados

À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.

Fundamentos básicos: ◦ GRAU – número de subárvores de um nó; ◦ FOLHA – um nó que possui grau zero, ou seja não possui subárvores; ◦ FILHOS – são as raízes das subárvores de um nó; ◦ Nó não terminal é um nó que não é uma folha e é diferente da raiz;
◦ A altura de uma árvore é o comprimento do caminho mais longo da raiz até uma das folhas; ◦ Uma árvore nula tem altura 0; ◦ Todos os nós são acessíveis a partir da raiz; ◦ Existe um único caminho entre a raiz qualquer outro nó;

Formas de representação gráfica

Árvores Binárias

Árvore Binária: Uma árvore binária é uma árvore que pode ser nula, ou então tem as seguintes características: ◦ Existe um nó especial denominado raiz; ◦ Nenhum nó tem grau superior a 2 (dois), isto é, nenhum nó tem mais de dois filhos; ◦ Existe um “senso de posição”, ou seja, distingue-se entre uma subárvore esquerda e uma subárvore direita.

Atravessamento (ou caminhamento) de árvore é a passagem de forma sistemática por cada um de seus nós;
- Diferentes formas de percorrer os nós de uma árvore: ◦ Pré-ordem ou prefixa (busca em profundidade); ◦ Em ordem ou infixa (ordem central); ◦ Pós-ordem ou posfixa ; ◦ Em nível.

Pré-ordem (prefixa) ◦ visitar a raiz; ◦ caminhar na subárvore à esquerda, segundo este caminhamento; ◦ caminhar na subárvore à direita, segundo este caminhamento.

Atravessamento em ordem (infixa) ◦ caminhar na subárvore à esquerda, segundo este caminhamento; ◦ visitar a raiz; ◦ caminhar na subárvore à direita, segundo este caminhamento.

Árvore