árvore (1)

Prévia do material em texto

ÁRVORE 
 
Introdução 
 
Anteriormente vimos a organização dos dados de uma maneira linear, onde a propriedade 
básica é a relação sequencial mantida entre os seus elementos . 
 Agora, veremos outra forma de organizar os dados chamados genericamente de 
não linear. Essa forma permite que outros tipos de relação entre dados possam ser 
representados como por ex. a relação de hierarquia uma árvore pode ser definida como 
sendo um conjunto finito de um ou mais nós da esquerda 
1º existe um nó denominado raiz da árvore 
2º os demais nós tornam subconjuntos (separados) onde cada um desses subconjuntos é 
uma árvore. 
A
B C D
F G H
I J K
folhas
folhas/nó terminal
nó terminal
filhos de C
raiz
nó da raiz da sub
árvore
filho de D
filhos de H
figura 1
 
 
Podemos generalizar a estrutura de uma árvore como sendo: 
 
1º cada nó tem somente um nó ascendente imediato ( denominado pai ) 
2º Cada nó pode mais de nó descendente imediato ( denominado filho ). 
3º Nós filhos de mesmo pai são denominados irmãos 
4º O grau de um nó é o número de subárvores de um nó, ou seja, é o n.º de nós filhos 
ligados imediatamente ao nó. 
5º O grau de uma árvore é o maior dos graus de seus nós 
6º Nós de grau 0 (zero ) isto é sem descendentes são chamadas de folhas ou nós terminais. 
7º Os antepassados de um nó são todos ao longo do caminho da raiz até o respectivo nó. 
8º O nível de um nó é o comprimento do que vai da raiz ao nó, isto é, o nº de linhas que 
liga à raiz. 
9º O maior dos níveis dos nós de uma árvore é altura (ou profundidade) da árvore. 
10º Floresta é um conjunto de árvores disjuntas (separadas) exemplos de estruturas que 
não são árvores. 
A
B
C D
A
B C
D
E F
A
B C
H
D
E F
G
 
 
 
 
 
 
 
 
 
 
 
 
 
2 
 
Representação das Árvores 
 A árvore da figura 1 pode ser representada por: 
 
A) DIAGRAMA DE VENN 
A B
C
F
H
G I J J
D
 
 
 
B) REPRESENTAÇÃO LINEAR 
 (A (B,C (F,G), D (H (I,J,K)))) 
 
C) REPRESENTAÇÃO DECIMAL DE DEWEY 
 
A 
 B 
 C 
 F 
 G 
 D 
 H 
 I 
 J 
 K 
 
D) REPRESENTAÇÃO ITEMIZADA 
1A; 1.1B; 
 1.2.C; 1.2.1.F; 
 1.2.2.G; 
 1.3.D;1.3.1.H; 1.3.1.I; 
 1.3.1.2.J; 
 1.3.1.3.K; 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3 
ÁRVORES BINÁRIAS 
 
DEFINIÇÃO: 
 
 Uma árvore binária se caracteriza pelo fato de todos os seus nós terem no máximo 
duas subárvores, ou seja, é uma árvore de graus dois. As duas subárvores de cada nó são 
denominadas subárvore esquerda e subárvore direita. 
 Como forma de representação física de uma árvore binária utilizaremos a alocação 
sequencial. 
O primeiro passo ser adotado será a alocação de espaço em memória suficiente 
para a estrutura. Esse espaço é dimensionado de tal forma que seja possível representar 
uma árvore completa. Uma árvore binária completa de altura K tem ( 2 ( K+1) ) - 1 nós, 
ou seja, todos os nós possuem dois filhos, exceto as folhas, que necessariamente estão no 
nível K. 
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
Figura 1 - ÁRVORE BINÁRIA COMPLETA 
 
 Na figura 1, representação uma árvore binária completa de altura 3 e numeramos 
sequencialmente os nós a partir do nível 0 (zero), da esquerda para direita. 
 Dessa forma, os nós agora podem ser armazenados em uma lista sequencial, onde 
cada nó i da árvore ocupa o i-ésimo nó da lista. A partir da numeração também 
conseguimos a posição de qualquer nó relacionado diretamente ao nó de uma árvore 
binária de n nós: 
1- O pai de i está em [i/2], sendo i <=1. Se i = 1, i é a raiz e não possui pai. 
2- O filho à esquerda de i está em 2i, se 2i <=n. Se 2i > n, então i não tem à esquerda. 
3- O filho à direita de i está em 2i + 1 <= n. Se 2i + 1 > n, então i não tem filho à direita. 
A
B C
D E F G
Figura 2 - ÁRVORE BINÁRIA COM ALOCAÇÃO SEQUENCIAL
A B C D E F G
 
 
 Esse tipo de alocação é muito interessante para árvore binárias completas, em uma 
árvore binária qualquer (incompleta), porém, haverá desperdício de espaço. Essa situação 
é facilmente observada analisando a alocação de uma árvore binária assimétrica com 
assimetria à esquerda, isto é, uma árvore binária em que nenhum de seus nós possui 
subárvore à direita. 
 
 
 
 
 
 
 
 
 
 
 
 
 
4 
Para este tipo de árvore binária com altura K, embora (2 (k+1))- 1 nós sejam alocados, 
apenas k+1 são 
A
B
C
Figura 3 - ÁRVORE BINÁRIA ALOCADA SEQUENCIALMENTE
A B - C - - -
 
 
 Outra forma de representação física de uma árvore binária por alocação sequencial 
consiste em subdividir o espaço de um nó em 3 campos: 
 
NÓ POSIÇÃO SUBÁRV.ESQ. POSIÇÃO SUBÁRV.DIR.
 
 
 Figura 4 - FORMATO DE UMNÓ DA ÁRVORE BINÁRIA SEQUENCIAL 
 
A árvore da figura 3 , ficaria representada por : 
A 2 0 B 0 0 C 0 0 
Podemos ver, porém que duas representações mostradas, os problemas inerentes à 
alocação sequencial persistem, isto é, a necessidade de alocarmos todo o espaço necessário 
para a estrutura e a dificuldade de manipulação dessa estrutura. 
 Para evitarmos tais problemas, utilizaremos a alocação encadeada, onde cada nó 
possui o seguinte formato: 
LINKESQ INFO LINKDIR 
 Onde LINKESQ. É o link do nó que contém o endereço da subárvore à esquerda e 
LINKDIR. Contém o endereço da subárvore à direita. 
 
 
 
 
 
 
 
 
 
5 
PERCURSO 
 
O percurso em uma árvore binária consiste em processar de forma sistemática e ordenada 
cada nó da árvore apenas uma vez, obtendo assim uma sequência linear dos nós. Nessa 
sequência, cada nó passa a ter um antecessor e um sucessor. 
A
B C
D FE G
 PTRAIZ
FIG.5 - ÁRVORE BINÁRIA ENCADEADA
 
 
PRÉ-ORDEM 
 Utiliza a raiz; 
 Percorre a subárvore esquerda em pré-ordem; 
 Percorre a subárvore direita em pré-ordem; 
 
ORDEM 
 Percorre a subárvore esquerda em ordem simétrica; 
 Utiliza a raiz; 
 Percorre a subárvore direita em ordem simétrica 
 
PÓS-ORDEM 
 Percorre a subárvore esquerda em pós-ordem; 
 Percorre a subárvore direita em pós-ordem; 
 Utiliza a raiz; 
 
Ex. 
A
B C
D E F G
 
 
PRÉ-ORDEM = A B D E C F G 
ORDEM = D B E A F C G 
PÓS-ORDEM = D E B F G C A 
 
 É interessante notar que, analisando os percursos definidos anteriormente, a 
simples troca de sentido 
( esquerda  direita ). Define três novas sequências lineares. A essa maneira “inversa” 
de percorrer uma árvore binária chamamos de “percurso inverso”. As seguintes sequências 
são obtidas utilizando esses novos percursos na árvore.