Introdução a Árvores
Prof. Ernesto Lindstaedt
Introdução


Estrutura de dados adequada para representar e manipular
informação hierárquica
Exemplos de aplicação:
• Estrutura de diretórios (pastas) em um sistema de
arquivos
• Organograma de uma empresa/instituição
• Expressão aritmética
• Estrutura de classes de uma API
Definição

Uma árvore T é um conjunto finito de elementos denominados nós
ou vértices tais que:
• T = 0 é a árvore dita vazia ou
• Existe um nó r, chamado raiz de T; os nós restantes
constituem um único conjunto vazio ou são divididos em
m1 conjuntos distintos não vazios que são as subárvores de r, cada sub-árvore a qual é, por sua vez, uma
árvore.
Sub-árvores: definições



Notação: Se v é um nó de T,então a notação Tv indica a subárvore de T com raiz em v
Seja a árvore TA = {A, B, ...}
• A árvore TA possui duas sub-árvores: Tb e Tc onde Tb = {
B } e Tc = {C, D, ...}
• A sub-árvore Tc possui 3 subárvores: Td , Tf e Te onde Td
= {D, G, H} Tf = {F, I} Te = {E}
As sub-árvores Tb, Te, Tg, Th, Ti possuem apenas o nó raiz e
nenhuma sub-árvore.
Outro exemplo:
Mais definições...
Seja v o nó raiz da subárvore Tv de T



Nós filhos
• os nós w1, w2, ... Wj, raízes das subárvores de Tv, são
chamados filhos de v.
Pais, tios, irmãos e avô
• O nó v é chamado pai de w1, w2, ... wj. Os nós w1, w2,
...wj são irmãos. Se z é filho de w1 então w2 é tio de z e v
é avô de z.
Nó descendente e ancestral
• Se x pertence à subárvore Tv, então x é descendente de v e
v é ancestral, ou antecessor, de x.
Exemplo:
Mais definições...




Grau de saída
• Grau de saída: número de filhos de um nó;
Nó folha
• Nó que não possui descendentes, ou seja, um nó folha é
aquele com grau de saída nulo.
Nó interior ou interno
• Nó que não é folha (isto é, possui grau de saída diferente de
zero).
Grau de uma árvore
• Valor máximo entre os graus de seus nós.
Exemplo:
Mais definições...



Floresta
• Conjunto de zero ou mais árvores
Caminho na árvore
• Seqüência de nós distintos v1, v2, ..., vk, tal que existe
sempre entre nós consecutivos (isto é, entre v1 e v2, entre
v2 e v3, ... , v(k-1) e vk) a relação "é filho de“ ou "é pai de"
Comprimento do caminho
• Um caminho que passa por vk vértices é obtido pela
seqüência de k-1 pares. O valor k-1 é o comprimento do
caminho.
Exemplo de floresta:
Exemplo de caminho:
Mais definições...



Nível (ou profundidade) de um nó
• O nível ou profundidade de um nó é o número de nós do
caminho da raiz até o nó (raiz tem nível 1)
Altura de um nó v
• Número de nós no maior caminho de v até um de seus
descendentes (folhas têm altura 1)
Altura de uma árvore T ou h(T)
• Máximo nível de seus nós (a altura da sub-árvore de raiz v é
representada por h(v) )
Exemplo de níveis:
Caminhamento em Árvores - Amplitude

Visitar cada nó começando no de menor nível e mover-se
para os níveis mais altos, nível após nível, visitando cada
nó da esquerda para a direita:
• Breadth - First Search (BFS)
Fila: 13
13
Fila: 10, 25
10
2
Fila: 25, 2, 12
25
12
20
Fila: 2, 12, 20, 31
31
29
Percurso: 13, 10, 25, 2, 12, 20, 31, 29
Fila: 12, 20, 31
Fila: 20, 31
Fila: 31
Fila: 29
Caminhamento em Árvores Profundidade

O caminhamento em profundidade prossegue tanto quanto
possível à esquerda (ou direita), então se move para trás
até a primeira encruzilhada, vai um passo para a direita (ou
esquerda) e novamente, tanto quanto possível, para a
esquerda (ou direita). • Deapth - First Search (DFS)
V – Visitar um nó
L – Percorrer à esquerda
R – Percorrer à direita
13
10
2
25
12
20
31
29
VLR VRL
LVR RVL
LRV RLV
Percurso: 2, 12, 10, 20, 29, 31, 25, 13