Rvores 1

Árvores

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, pastas criadas em um computador

Definição de Árvore
• Árvore é uma estrutura de dado não linear adequada para representar hierarquias; Representação Gráfica
Árvores
Dados são dispostos de forma hierárquica
Elementos (nós)
Raiz (pai) - [ancestrais de um nó]
Galhos (filhos) – [ancestrais/descendentes de um nó]
Folhas (terminais) - [descendentes de um nó]

Classificação das Árvores
• Uma árvore pode ser classificada de diversas formas diferentes, uma delas é pelo número máximo de nós-filhos que cada nó-pai pode ter: – Binária (dois nós);
– Ternária (três nós);
– Quaternária (quatro nós);
– N-ária (N nós);
– Não N-ária (quando não conhecemos ou não há um número máximo de nós-filhos para cada nó-pai).

Declaração de uma Árvore N-ária const N = 2; type PNo = ^Tno;
TNo = record valor: integer; filhos: array [1..N] of PNo; end; TArvore = PNo;

Declaração de uma Árvore Não N-ária type PNo = ^TNo;
TNo = record valor: integer; irmao: PNo; filho: PNo; end; TArvore = PNo;

Nível de um Nó
• Refere-se à distância do mesmo até a raiz;

0
1
2
3

Altura ou Profundidade de uma Árvore
• É o nível máximo que um nó da árvore atinge;
0
1
2
3

A altura desta árvore é 3! Ela possui 4 níveis!

Ordem: número máximo de galhos em um elemento
Altura: raiz mais o máximo número de descendentes
Nível de um nó: o comprimento do caminho da raiz até o nó, que é o número de arcos no caminho

Percurso de uma Árvore
• Também conhecido como travessia;
• Consiste em percorrer (em uma dada ordem) todos os nós de um árvore ou até encontrar algum que satisfaça ao problema em questão;
• É empregado, por exemplo, na busca de um nó a partir de uma chave;

Percurso de uma Árvore
• Tipos
– Pré-ordem / pre-order;
– Em-ordem / in-order;
– Pós-ordem / pos-order.

Percurso Pré-Ordem
•