Tópicos Avançados em Estrutura de Dados
6º Período – Ciência da Computação
Prof. Jean Carlos Hennrichs
Árvores (revisão)
Uma das mais importantes classes de estruturas de dados em computação são as árvores. Aproveitandose de sua organização hierárquica, muitas aplicações são realizadas usando-se algoritmos relativamente
simples, recursivos e de eficiência bastante razoável.
Definições e representações básicas
Uma árvore é uma estrutura de dados que se caracteriza por uma relação de hierarquia entre os
elementos que a compõem. Exemplos de estruturas em forma de árvores são:
 O organograma de uma empresa (figura 1);
 A divisão de um livro em capítulos, seções, tópicos, etc;
 A árvore genealógica de uma pessoa.
 A estrutura de diretórios de um Sistema Operacional (figura 1).
 Entre outros
Figura 1
De um modo um pouco mais formal, podemos dizer que uma árvore é um conjunto finito de um ou mais
nodos (nós ou vértices), tais que:
1. existe um nodo denominado raiz;
2. os demais nodos formam m>= 0 conjuntos disjuntos s1, s2, ... , sm, tais que cada um desses
conjuntos também é uma árvore cuja denominação é sub-árvore (figura 2).
Figura 2
A
B
E
C
F
D
G
H
L
I
M
J
N
A
B
C
D
A
Floresta
Figura 3
Uma floresta é um conjunto de árvores (figura 3). Se v é um nodo de A, a notação Av indica a sub-árvore
de v com raiz A.
Figura 4
Para visualizar esse conceito, pode-se representá-lo graficamente. Há formas diferentes de
representações gráficas de uma árvore. Em todas elas, cada nodo poderá ser associado a um
identificador, denominado rótulo.
a) Representação hierárquica
Figura 5
b) Representação por conjuntos (diagrama de inclusão)
Figura 6
c) Representação por expressão parentetizada (parênteses aninhados)
Cada conjunto de parênteses correspondentes contém um nodo e seus filhos. Se um nodo não
tem filhos, ele é seguido por um par de parênteses sem conteúdo.
(A(B(D()E()))(C(F())))
d) Representação por expressão não parentetizada
Cada nó é seguido por um número que indica a quantidade de filhos desse nodo, e em seguida
por esses filhos, representados do mesmo modo.
A2B2D0E0C1F0
Outro exemplo
a) Representação Hierárquica
Figura 7
b) Representação por conjuntos (diagrama de inclusão)
Figura 8
c) Representação por parênteses aninhados
( A (B) ( C (D (G) (H)) (E) (F (I)) ) )
Pode-se representar uma árvore de muitos outros modos, mas é interessante notar que, dentre os
exemplos apresentados, a representação a) é a que permite uma melhor visualização, e que será utilizada
a partir deste ponto. As representações c) e d) não permitem boa visualização da estrutura, mas podem
ser úteis para guardar em arquivos os dados de uma árvore.
Como, por definição, os subconjuntos s1, s2,...,sm são disjuntos, cada nó só pode ter um pai. Assim, a
figura 5, por exemplo, não representa uma árvore:
Figura 9
Definições Gerais:
Dada uma árvore qualquer:
1) A linha que liga dois nodos da árvore denomina-se aresta.
2) Diz-se que existe caminho entre dois nodos V e W da árvore, se a partir do nodo V puder-se
chegar ao nodo W percorrendo-se as arestas que ligam os nodos intermediários entre V e W.
Observa-se que existe sempre um caminho entre a raiz e qualquer nodo da árvore.
3) Se houver um caminho entre V e W, começando em V diz-se que V é um nodo ancestral de
W e W é um nodo descendente de V. Se este caminho contiver uma única aresta, diz-se que V é
o nodo pai de W e que W é um nodo filho de V. Dois nodos que são nodos filhos do mesmo
nodo pai são denominados nodos irmãos. Uma característica inerente a árvores é que qualquer
nodo, exceto a raiz, tem um único nodo pai.
4) Se um nodo não possui nodos descendentes, ele é chamado de folha ou nodo terminal da
árvore.
5) Grau de um nodo ou Grau de saída é o número de nodos filhos do mesmo. Obviamente que
um nodo folha tem grau zero.
6) Nodo interior ou nó interno é um nodo que não é folha, ou seja, seu Grau de saída é diferente
de zero.
7) Nível de um nodo ou Profundidade de um nó é o número de nodos existentes no caminho
entre a raiz e o próprio nodo. A raiz tem nível 0.
8) O grau da árvore é igual ao grau do nodo de maior grau da árvore. É o máximo entre os graus
de seus nós.
9) O nível da árvore ou altura da árvore é igual ao nível do nodo de maior nível da árvore. É o
comprimento do caminho mais longo da raiz até uma das folhas. A altura de uma árvore que
possui somente um nodo é zero.
Altura
Figura 10
Exercício:
Figura 11
1) A partir da árvore representada na figura 11, responda:
a) Qual é a raiz da árvore?
b) Quais são os nodos terminais?
c) Qual o grau da árvore?
d) Qual o nível da árvore?
e) Quais são os nodos descendentes do nodo D ?
f) Quais são os nodos ancestrais do nodo # ?
g) Os nodos 4 e 5 são nodos irmãos? Por que?
h) Há caminho entre os nodos C e S?
i) Qual o nível do nodo 5?
j) Qual o grau do nodo A?
k) Faça a construção da representação por conjuntos da árvore
l) Faça a construção da representação por parênteses aninhados da árvore
m) Faça a construção da representação por expressão não parentetizada da árvore
2) A partir da árvore representada na figura 12, abaixo, responda:
A
B
C
D
E
F
G
H
I
Figura 12
a) Quantos nós possui a árvore?
b) Quais são os nodos terminais?
c) Qual o grau da árvore?
d) Qual o nível da árvore?
3) A partir da árvore representada na figura 13, abaixo, responda:
T
1
2
3
4
#
5
%
C
&
A
6
M
@
B
Figura 13
a) Qual é a raiz da árvore?
b) Quais são os nós folhas?
c) Qual o grau da árvore?
d) Qual o nível da árvore?
e) Quais são os nodos descendentes do nodo A ?
f) Quais são os nodos ancestrais do nodo @ ?
g) Os nodos # e % são nodos irmãos? Por que?
h) Há caminho entre os nodos # e @?
i) Qual o nível do nodo %?
j) Qual o grau do nodo M?
k) Faça a construção da representação por conjuntos da árvore
l) Faça a construção da representação por parênteses aninhados da árvore
m) Faça a construção da representação por expressão não parentetizada da árvore
n) Quantos nós possui a árvore?
Árvores Binárias
Definição:
É um conjunto finito de elementos que está vazio ou é particionado em três subconjuntos disjuntos. O
primeiro subconjunto contém um único elemento, denominado de raiz da árvore. Os outros dois
subconjuntos são árvores binárias, chamados de sub-árvore esquerda (sae), e sub-árvore direita
(sad), da árvore original. É possível quem ambas as sub-árvores estejam vazias. Cada elemento que
constitui uma árvore binária é definido por nó da árvore.
Figura 14
A Figura 15 representa uma árvore binária. A raiz desta árvore é o nó A. A sub-árvore da esquerda está
enraizada em B e a da direita em C. A sub-árvore esquerda da árvore binária enraizada em C e a subárvore direita da árvore binária enraizada em E, estão ambas vazias. As árvores binárias enraizadas em
D, G, H e I tem sub-árvores direita e esquerda vazias. Um exemplo de utilização de árvores binárias é a
tabela de jogos de um campeonato de futebol, onde a cada disputa entre 2 times sobra apenas 1, que joga
com o ganhador de outro confronto de mesmo nível, até achar o campeão geral da competição.
A
B
D
C
E
F
G
H
I
Figura 15
Se A é a raiz da árvore binária e B é a raiz da sub-árvore direita ou esquerda, então diz-se que A é o pai
de B e que B é filho direito ou esquerdo de A.
Um nó sem filhos (D, G, H e I) são denominados de folhas. O nó n1 é um ancestral do nó n2 (e n2 é
um descendente de n1), se n1 for o pai de n2 ou o pai de algum ancestral de n2. Por exemplo na figura
15, A é um ancestral de G, e H é um descendente de C, mas E não é nem ancestral nem descendente de
C.
Um nó n2 é um descendente esquerdo do nó n1 se n2 for o filho esquerdo de n1 ou um descendente do
filho esquerdo de n1. Um descendente direito pode ser definido de modo semelhante. Dois nós são
irmãos se forem filhos esquerdo e direito do mesmo pai.
A
A
B
D
C
E
A
B
F
D
C
E
F
G
G
B
(A)
D
H
C
E
G
(B)
Figura 16
F
H
(C)
A figura 16 demonstra algumas estruturas que não são árvores binárias. Tente entender por que cada
uma delas não é uma árvore binária.
Diferente das árvores naturais os cientistas da computação sempre representaram as árvores binárias
com a raiz apontando para o céu e as folhas para a terra. Desta forma diz que quando você percorre a
árvore no sentido das folhas para a raiz, diz-se que está subindo a árvore e quando percorre da raiz para
as folhas diz-se que está descendo a árvore.
Uma árvore é dita como estritamente binária se todo o nó que não é folha, tiver sub-árvores esquerda e
direita não-vazias. Ou seja, uma árvore estritamente binária é uma árvore binária em que cada nó tem 0
ou 2 filhos. Teorema: Uma árvore estritamente binária com n folhas, contém sempre 2n-1 nós. A figura
17 ilustra uma árvore estritamente binária.
A
B
C
D
E
F
G
Figura 17
Exercícios:
1) Construa 3 árvores binárias com no mínimo 6 nós em cada uma delas.
2) Descreva textualmente por que as arvores A, B e C na figura 16 não são consideradas árvores
binárias.
3) Por que a árvore da figura 15, não é uma árvore estritamente binária?
4) Prove através da elaboração de árvores binárias o teorema que prova quando uma árvore é
estritamente binária.
O nível de um nó em uma árvore binária é definido como segue: A raiz possui sempre nível 0. O nível
de qualquer outro nó da árvore é um nível a mais que o nível de seu pai. Na figura 15 o nó G possui
nível 3, o nó D tem nível 2 e os nós B e C nível 1.
A profundidade de uma árvore binária é dada pelo nível máximo de qualquer folha da árvore. Ou seja,
equivale ao percurso mais distante da raiz até qualquer folha. A profundidade da árvore da figura 15 é 3.
Uma árvore binária completa é uma árvore estritamente binária, em se n é um nó com algumas de
sub-árvores vazias, então n se localiza no penúltimo ou no último nível.
Uma árvore binária cheia de profundidade d é uma árvore completa e estritamente binária em que
todas as folhas estejam no nível d.
Figura 18
Exercícios:
5) Construa 3 árvores binárias completas e 3 não completas, com no mínimo 6 nós cada uma delas.
6) Construa 2 árvores binárias cheias com no mínimo 7 nós cada uma delas.
7) Por que a árvore binária da Figura 15 não é uma árvore binária cheia?
Definição da Estrutura de Dados de Árvores Binárias
Figura 19
Operações associadas a árvores binárias padrão:







Definir uma árvore vazia
Criar um nó raiz
Verificar se árvore vazia ou não
Criar um filho à direita de um dado nó
Criar um filho à esquerda de um dado nó
Verificar qual o nível de um dado nó
Retornar o pai de um dado nó
Alocação seqüencial de Árvore Binária Completa
Uma árvore desse tipo pode ser alocada sobre um vetor de forma simples e compacta. A tabela abaixo
mostra uma árvore completa de 11 nós. Os números indicam o respectivo índice do vetor onde o dado
do nó irá cair. Observe que a árvore completa tem uma configuração padrão: a raiz da árvore sempre
ocupará a posição inicial do vetor; o filho esquerdo da raiz cairá sempre na segunda posição do vetor; o
filho direito, na posição 3, e assim por diante, considerando um array que inicia na posição 1.
A
A
B
C
D
H
E
I
J
F
B
G
D
L
H
C
E
I
F
J
G
L
Figura 20
A tabela abaixo estabelece uma série de relações entre os índices do vetor e os nós da árvore:
Nó / índice
Info
Pai
Filho esquerdo
Filho direito
Irmão esquerdo
Irmão direito
1
A
-1
2
3
-1
-1
2
B
1
4
5
-1
3
3
C
1
6
7
2
-1
4
D
2
8
9
-1
5
5
E
2
10
11
4
-1
6
F
3
-1
-1
-1
7
7
G
3
-1
-1
6
-1
8
H
4
-1
-1
-1
9
9
I
4
-1
-1
8
-1
10
J
5
-1
-1
-1
11
11
L
5
-1
-1
10
-1
Da tabela derivamos, facilmente, fórmulas para calcular a posição de um nó da árvore em relação a
outro:
Pai(i) = i div 2, se 1 < i <= n
Filho Esquerdo(i) = 2i, se 2i <= n
Filho Direito(i) = 2i + 1, se 2i + 1 <= n
Irmão Esquerdo(i) = i - 1, se i é ímpar e 2 < i <= n
Irmão Direito(i) = i + 1, se i é par e 1 < i + 1 <= n
onde n é o total de nós e i é o índice do vetor que armazena o nó em exame.
A vantagem deste método de alocação em relação à encadeada é que ele não consome espaço para
armazenar a estrutura. A desvantagem é sua aplicação restrita às árvores binárias completas que
contenham folhas somente a direita da árvore (figura 20 esquerda), ou seja, a partir do momento que
surgir folhas, a direita desta só poderá conter folhas. Na figura 20 direita não funcionará as fórmulas.
Percurso em Árvores Binárias
Percorrer uma árvore visitando cada nó uma única vez gera uma seqüência linear de nós, e
então passa a ter sentido falar em sucessor e predecessor de um nó segundo um determinado percurso.
Há três maneiras recursivas de se percorrer árvores binárias.
Travessia em Pré-Ordem ou em Travesia em Profundidade
1. se árvore vazia; fim
2. visitar o nó raiz
3. percorrer em pré-ordem a sub-árvore esquerda
4. percorrer em pré-ordem a sub-árvore direita
Figura 21
Percurso em Pré-ordem da árvore da figura 21:
 ABDCEGFHI
 visita o nó quando passar a sua esquerda
 notação pré-fix
Travessia em In-Ordem ou Travessia em ordem simétrica
1. se árvore vazia, fim
2. percorrer em in-ordem a sub-árvore esquerda
3. visitar o nó raiz
4. percorrer em in-ordem a sub-árvore direita
Figura 22
Percurso em In-ordem da árvore da figura 22:
 DBAEGCHFI
 visita o nó quando passar embaixo do nó
 notação in-fix
Travessia em Pós-Ordem
1. se árvore vazia, fim
2. percorrer em Pós-Ordem a subárvore esquerda
3. percorrer em Pós-Ordem a subárvore direita
4. visitar o nó raiz
Figura 23
Percurso em Pré-ordem da árvore da figura 23:
 DBGEHIFCA
 visita o nó quando passar a sua direita
 notação pós-fix
Exercícios:
8) A partir das duas árvores binárias abaixo, descreva a travessia ou o percurso em Pré, In e Pós-ordem
de cada uma das árvores.
a)
b)
A
B
C
D
E
G
A
H
B
F
I
C
E
D
F
I
G
J
H
K
L
9) Construa árvores binárias que representem as seguintes expressões matemáticas. Considerar $ como
exponenciação. Dependendo a bibliografia a exponenciação pode ser representada por “**” ou por “^”.
a)
b)
c)
d)
A+B*C
(A + B) * C
A + (B – C) * D $ (E * F)
(A + B * C) $ ((A + B) * C)
10) A partir das árvores construídas no exercício 9, trace o percurso em Pré, In e Pós-ordem de cada
uma das árvores.
11) Prove que um nó de uma árvore binária tem no máximo um pai.
12) Quantos ancestrais tem um nó no nível n numa árvore binária? Prove sua resposta.
Referências Bibliográficas:
Algoritmos e Estruturas de Dados III – UPF:
http://www.eduardostefani.eti.br/bennett/algoritmos2/algoritmos-estrutura-dados.pdf
WALTER,Marcelo: http://www.inf.unisinos.br/~marcelow/ensino/grad/lab2/
PIMENTEL, Graça: http://www.icmc.sc.usp.br/~sce182/arvbinrb.html
CORMEN, Thomas H. et al. Algoritmos: teoria e prática . Rio de Janeiro: Campus, 2002.
TENEMBAUM, Aeron. Estruturas de Dados usando C. São Paulo: Makron Books, 1995.
Árvores Binárias – PUC PR: http://www.ppgia.pucpr.br/~laplima/aulas/materia/arvbin.html
CRUZ, Adriano. Árvores. http://equipe.nce.ufrj.br/adriano/c/apostila/arvore.htm
SILVA, Alexandre Parra Carneiro da. Árvores e Árvores Binárias.
http://www.joinville.udesc.br/portal/professores/parra/materiais/