Árvores
ATAI
1
Arvores

Árvore é um conceito não linear da ciência da computação.

Árvore produz uma organização natural para os dados e está
presente nos sistemas de arquivos, interfaces gráficas do
utilizadores, base de dados, sites e em outros programas de
computador.

As relações numa árvore são hierárquicas com alguns objectos
"acima" e outros "abaixo".

A principal terminologia para a estrutura de dados árvore vem de
árvores genealógicas, com os termos: pai, filho, ascendente e
descendente.
2
Exemplo de estrutura em forma de Arvore
3
TAD Árvore

TAD que armazena elementos
hierarquicamente, isto é:

Exemplo de uma árvore
representando a estrutura de uma
empresa fictícia
Com excepção do elemento do topo, cada
elemento numa árvore tem um elemento
ascendente (pai) e zero ou mais
elementos descendentes (filhos).

A representação visual de uma árvore
normalmente é feita com os elementos
dentro de ovais ou rectângulos, e as
relações entre pais e filhos representadas
através de linha rectas.

O elemento do topo é chamado de raiz da
árvore, mas é mostrado graficamente
como o elemento mais alto, com os
demais elementos conectados abaixo (o
oposto da árvore botânica).
4
Terminologia e Propriedades Básicas

Uma árvore T é um conjunto de nós armazenando elementos numa
relação pai-filho com as seguintes propriedades:




T tem um nó especifico r, chamado de raiz de T, que não tem
pai.
Cada nó v de T diferente de r tem um nó pai u.
Para todo nó v de T, a raiz r é um ascendente de v.
Uma definição recursiva:

um ascendente de um nó é tanto um nó ele mesmo ou um
ascendente de um pai de nó. Ou seja: um nó v é um
descendente de um nó u se u é um ascendente de v.

Exemplo 1: A relação de herança entre classes de um programa Java.

Se um nó u é pai de um nó v, então é dito que v é filho de u.

Dois nós que são filhos do mesmo pai são irmãos.
5
Terminologia e Propriedades Básicas

Um nó é externo se ele
não tem filhos. Um nó
externo também é chamado
de folha.

Um nó é interno se tem um
ou mais filhos.
A sub-árvore de T cuja raiz
é um nó v é uma árvore
que consiste de todos os
nós descendentes de v em
T (incluindo v).

Exemplo2: A árvore de
directórios da maioria dos
sistemas operativos:
6
Terminologia e Propriedades Básicas

Uma árvore é ordenada, se existe uma ordem linear definida para
os filhos de cada nó, de tal maneira que se possa identificar um nó
como sendo o primeiro, o segundo, o terceiro e assim por diante.

Tal ordenação é determinada pelo uso que se deseja dar à árvore.

A ordenação da árvore é usualmente indicada na sua
representação gráfica dispondo os irmãos da esquerda para a
direita, correspondendo à relação linear.

Árvores ordenadas tipicamente indicam a relação linear existente
entre irmãos, listando-os na sequência ou enumeração na ordem
correcta.
7
Terminologia e Propriedades Básicas
Exemplo3: Um documento estruturado como um livro é
hierarquicamente organizado como uma árvore:
8
Métodos de Árvore

O TAD árvore armazena os elementos em posições as
quais, tal como posições numa sequência, são definidas
relativas às posições vizinhas:
 Nas Árvores a noção de posição está relacionada
com as relações pai-filho, definidas numa árvore
válida.

Numa árvore também existe noção de posição (TAD
Position), que suporta o método:
 elemento(): retorna o objecto nesta posição.
 Entrada: Nenhuma; Saída: Objecto.
9
Métodos de Árvore

Métodos de acesso:

root(): Retorna a raiz de T; se T está vazia, um erro ocorre.
 Entrada: Nenhuma; Saída: Posição.

parent(v): Retorna o pai do nó v; um erro ocorre, se v = raiz().
 Entrada: Posição; Saída: Posição.

children(v): Retorna um iterador para os filhos do nó v.
 Entrada: Posição; Saída: Enumeração de posições.
10
Métodos de Árvore

Métodos de pesquisa:



isInternal(v): Testa se a posição v é um nó interno.
 Entrada: Posição; Saída: Booleano.
isExternal(v): Testa se a posição v é um nó externo.
 Entrada: Posição; Saída: Booleano.
isRoot(v): Testa se a posição v é o nó raiz.
 Entrada: Posição; Saída: Booleano.
11
Métodos de Árvore

Métodos genéricos:
 size(): Retorna o número de nós em T.


elements(): Retorna um iterador com todos os elementos
armazenados em nós de T.


Entrada: Nenhuma; Saída: Iterador de posições.
swapElements(v, w): Troca os elementos armazenados nos nós v e
w de T.


Entrada: Nenhuma; Saída: Iterador de objectos.
positions():Retorna um iterador com todas as posições (nós) de T.


Entrada: Nenhuma; Saída: Inteiro.
Entrada: Duas posições; Saída: Nenhuma.
replaceElement(v, e): Substitui o elemento armazenado no nó v
com e, retornando o elemento anteriormente armazenado em v.

Entrada: Uma posição e um objecto; Saída: Objecto.
12
Interface Proposta de um ADT Árvore
13
Interface InspectablePositionalContainer
public interface InspectablePositionalContainer
extends InspectableContainer {
// accessor methods
/** return the positions in the container */
public PositionIterator positions();
}
14
Interface PositionalContainer
public interface PositionalContainer
extends InspectablePositionalContainer {
// update methods
/** swap the elements at two nodes */
public void swapElements(Position v, Position w);
/** replace with and return the element at a node */
public Object replaceElement(Position v, Object e);
}
15
Interface InspectableTree
public interface InspectableTree extends
InspectablePositionalContainer {
// accessor methods
/** return the root of the tree */
public Position root();
/** return the parent of a node */
public Position parent(Position v);
/** return the children of a node */
public PositionIterator children(Position v);
// query methods
/** test whether a node is internal */
public boolean isInternal(Position v);
/** test whether a node is external */
public boolean isExternal(Position v);
/** test whether a node is the root of the tree */
public boolean isRoot(Position v);
}
16
Interface Tree
public interface Tree extends InspectableTree,
PositionalContainer {
}
17
Profundidade da Árvore



A profundidade de um no v de uma árvore T é o número de
ascendentes de v, excluindo o próprio v.
A profundidade da raiz é 0.
A profundidade de um no pode também ser definida recursivamente
como:



Se v é a raiz, então a profundidade é 0.
Caso contrario, a profundidade de v é um mais a
profundidade do pai de v.
O fragmento de código recursivo:
public int depth (InspectableTree T, PostionalContainer v) {
// calculo recursiva da profundidade do no v
if(T.isRoot(v)) {
return 0;
}
return 1 + depth(T, T.parent(v));
}
18
Altura da Árvore



A altura de um no v numa árvore T é também definida recursivamente da
seguinte maneira:
 Se v é um no externo, então a altura de v é 0.
 Caso contrário, a altura de v é um mais a altura máxima dos filhos de v.
A altura total de uma árvore T é definida como a altura da raiz de T.
Outra maneira de ver a altura de uma árvore T é a profundidade máxima de
um no de T, que é encontrada em um ou mais nos externos.
public static int height (InspectableTree T) {
int h = 0;
PositionIterator positer = T.positions();
while (positer.hasNext()) {
Position v = positer.nextPosition();
if (T.isExternal(v))
h = Math.max(h, depth(T, v));
}
return h;
}
19
Largura da Árvore
A largura de uma árvore T é definida através do
conceito de grau.

O grau de um nó v
É dado pelo número de subárvores a ele ligadas.

Grau de uma árvore T
É o máximo grau entre todos os nós da árvore.
20
Tipos de deslocamento numa árvore


O deslocamento numa árvore é uma forma sistemática de aceder
ou "visitar" todos os seus nos.
Existem dois tipos principais de deslocamento:

Pré-ordem (preorder): cada nó é processado antes de qualquer
nó das suas subárvores.

Pós-ordem (postorder): cada nó é processado depois de todos os
nós das suas subárvores.
21
Deslocamento pré-ordem

Em um deslocamento pré-ordem (preorder) de uma árvore T, a
raiz é visitada primeiro e então as sub-árvores, cujas raízes são
seus filhos, são visitados recursivamente.

A acção específica associada à "visita" de um no (processamento
do no) depende de cada aplicação.

Inicialmente a chamada desta rotina é preOrdem(T, T.raiz()).
Algoritmo preOrdem(T, v)
realize a acção de "visita" para o no v
para cada filho w de v faça
caminhe recursivamente a sub-árvore de raiz w
pela chamada de preOrdem(T, w)
22
Deslocamento pré-ordem
23
Deslocamento pos-ordem

O algoritmo pós-ordem (postorder) pode ser visto
como o oposto do algoritmo de deslocamento préordem, porque ele primeiro caminha recursivamente
as sub-árvores cujas raízes são os filhos da raiz e
só em seguida visita a raiz.
Algoritmo posOrdem(T, v)
para cada filho w de v faça
caminhe recursivamente a sub-árvore de raiz w
pela chamada de posOrdem(T, w)
realize a ação de "visita" para o nó v
24
Deslocamento pos-ordem
25
Formas de representação - Lista Ligada
Cada nó da árvore de grau arbitrário pode ser especificado
pelos seguintes componentes:
•
•
•
Object elemento;
Arv_No filhos; /* lista de descendentes / filhos */
Arv_No irmaos; /* lista de irmãos */
a sce n d e n te
tm p
A inserção será
feita na lista ligada
contendo os seus
irmãos. Isto implica
o conhecimento
prévio do
ascendente.
n o vo
A
n u ll
C
n u ll
G
D
n u ll
n u ll n u ll
H
n u ll
I
n u ll
J
n u ll n u ll
26