aula03

Prévia do material em texto

3ºAula
INTRODUÇÃO ÀS ÁRVORES
Objetivos de aprendizagem
Ao término desta aula, vocês serão capazes de: 
• conhecer o que são árvores;
• entender algumas terminologias aplicadas a uma árvore;
• saber o que são árvores binárias.
Olá,
Nesta aula, vamos começar o estudo de uma estrutura de 
dados muito importante: as Árvores. Aqui, aprenderemos o 
que são as árvores, e conheceremos a nomenclatura de alguns 
aspectos de uma árvore. Além disso, veremos o que são árvores 
binárias, conteúdo muito importante para as próximas aulas.
Leiam atentamente esta aula e façam os exercícios. Se 
enfrentarem alguma dúvida, estaremos a sua disposição na área 
do aluno.
Bons estudos!
21
Estrutura de Dados II 20
1. 
Seções de estudo
Entendendo as árvores
2. Terminologia de uma árvore
3. Árvores Binárias
1 - Entendendo as árvores
Até o presente momento, vocês viram duas estruturas 
de dados importantes: as Listas e as Tabelas Hash. Ambas 
são métodos excelentes para armazenar um conjunto de 
dados, como uma lista de valores. Mas, os dados que 
podemos armazenar podem ter uma relação de hierarquia. 
A propósito, as hierarquias são uma das coisas que vemos 
muito em nosso cotidiano. Um exemplo de hierarquia são 
os organogramas, que definem uma estrutura 
organizacional:
Figura 1 - Exemplo de Organograma. Fonte: Disponível em: < https://static.
Outro exemplo de hierarquia em nosso cotidiano 
são as árvores genealógicas. Quem nunca fez uma árvore 
mostrando os antepassados? É também um outro grande 
exemplo de hierarquia.
Figura 2 - Exemplo de Árvore Genealógica Fonte: Disponível em: <https://i.
pinimg.com/originals/6d/a4/1e/6da41ec938f87bbe839141b47b63a249.png>. 
Acesso em: 13 set. 2018.
Outro exemplo que podemos citar é o mapa mental. 
Um mapa mental é uma forma de estruturar um conjunto 
de ideias, de maneira hierárquica. Podemos entender esse 
conjunto de ideias como sendo qualquer coisa, como, por 
exemplo, os conteúdos da nossa aula:
Figura 3 - Exemplo de Mapa Mental. Fonte: Acervo Pessoal.
Bem, como podemos ver, a hierarquia é algo presente 
em nosso cotidiano, e precisamos de estruturas de dados que 
representem essa abstração. Porém, as estruturas de dados que 
nós vimos anteriormente, não são boas para representar isso. 
Assim, os estudiosos da área da Computação desenvolveram 
uma estrutura de dados capaz de representar isso: As árvores.
Szwarcfiter e Markenzon (1994) definem árvore como:
Uma árvore enraizada T, ou simplesmente árvore, 
é um conjunto nito de elementos denominados 
nós ou vértices tais que:
• T = 0, e a árvore é dita vazia, ou;
• Existe um nó especial, r, chamado raiz de T; 
os restantes constituem um único conjunto vazio 
ou são divididos em m >= 1 conjuntos disjuntos 
não vazios, as subárvores de r, ou simplesmente 
subárvores, cada qual por sua vez uma árvore 
(SZWARCFITER, MARKENZON; 1994, p. 
62).
Assim, uma árvore, no campo das estruturas de 
dados, pode ser entendida como uma representação que 
demonstra uma hierarquia entre os dados armazenados, 
onde um dado contido nesse conjunto é subordinado a 
outro.
Cada dado na árvore é chamado de nó. E a árvore é um 
conjunto finito de nós. Como na hierarquia, a árvore deve 
ter um dado que fique subordinado a todos os demais. Ele se 
chama raiz da árvore. É da raiz da árvore que partem todos os 
demais nós da árvore. A raiz pode ter vários nós na condição de 
subordinados dessa árvore. A esses nós chamamos de filhos. 
E esses filhos podem seus subordinados, gerando novos 
descendentes. Além disso, esses filhos geram subárvores.
Antes de prosseguirmos em nossos estudos, vamos 
mostrar uma ilustração de um conjunto de dados armazenados 
em forma de árvore:
Figura 4 - Exemplo de Árvore. Fonte: Acervo Pessoal.
22
21
 A imagem a seguir mostra uma árvore. Na próxima 
seção, com base nessa imagem, vamos identificar os elementos 
e as suas terminologias específicas. Aprender as terminologias 
específicas é muito importante, pois com base nessas teorias 
foram desenvolvidas as variantes das árvores. Antes de 
prosseguir, vamos ver algumas formas de representação 
gráfica de árvores.
o mas de ep esenta a camente o es
E istem várias formas de representar gra camente as árvores. A 
mais utilizada é esta que usamos para a Figura 4, denominada de 
Representação Hierárquica, ela mostra uma relação de hierarquia 
entre os nós da árvore. Porém, alguns autores utilizam outras 
notações, como o Diagrama de Inclusão, que é uma outra maneira 
de mostrar a hierarquia entre os elementos. A raiz é o elemento que 
engloba todos os demais nós da árvore.
Figura 5 - Exemplo de Árvore, representada na forma de Diagrama de Inclusão. 
Fonte: (SOUZA, 2009).
Outra forma de representação é a notação de Parênteses Aninhados, 
que descreve te tualmente a hierarquia entre os elementos da 
árvore. A raiz da árvore é o elemento que engloba os demais, da 
mesma forma que foi e presso no Diagrama de Inclusão. A seguir 
veremos um e emplo de árvore e pressa nessa notação
( A (B) ( C (D (G) (H)) (E) (F (I)) ) )
Saibam que nesses dois e emplos, a mesma árvore da Figura 4 foi 
representada. Isso foi feito para mostrar as diferentes formas de 
representar uma árvore.
Por uma questão de facilidade, nós vamos mostrar as árvores na 
Representação Hierárquica, devido a sua facilidade de compreensão.
1 - Terminologia de uma árvore
Na seção anterior, vimos que uma árvore é um conjunto 
de N nós que são representados de forma hierárquica. O nó 
que inicia essa hierarquia é denominado de raiz da árvore. No 
exemplo da Figura 4, o nó A pode ser considerado a raiz da 
árvore.
Analisando a árvore, o nó A possui dois nós como 
herdeiros (B e C). Esses nós são chamados de filhos do nó A. 
E o nó A é considerado o pai dos nós B e C. Como Szwarcfiter 
e Markenzon analisaram anteriormente, cada nó descendente 
é considerado uma raiz de uma subárvore. Assim, podemos 
entender que B e C são raízes de subárvores internas. 
Pessoal.
Pessoal.
Falando sobre o parentesco de nós, vamos introduzir um 
novo conceito: o grau de um nó. O grau é o número de nós 
descendentes (ou subárvores) que um nó possui. Assim, 
podemos dizer que o nó A do exemplo tem grau 2, pois ele 
tem dois nós como filhos. O nó C tem grau 3, pois tem três 
filhos (D, E e F). Enquanto que o nó B tem grau zero, pois 
não tem nós descendentes.
Figura 8 - Ilustração mostrando o grau de um nó. Fonte: Acervo Pessoal.
Nós que têm grau zero possuem uma terminologia 
específica. São chamados de folhas. Assim, os nós B, E, G, H 
e I são considerados folhas.
23
Estrutura de Dados II 22
Acervo Pessoal.
Outra terminologia que é adotada nas árvores é a altura 
(ou profundidade). Essa altura é calculada através do número 
de nós a ser percorridos entre o nó raiz e o nó folha de maior 
profundidade na árvore. Para calcular isso, devemos dividir os 
nós em níveis. O nó raiz fica no primeiro nível, os filhos da 
raiz ficam no segundo nível, os netos da raiz no terceiro nível, 
e assim em diante. O número do maior nível será a altura da 
árvore. 
No exemplo, começamos a contagem de níveis com 1, 
e atribuímos os níveis correspondentes aos descendentes. 
Assim, chegamos à altura da árvore no valor 4.
Figura 10 - Árvore dividida em níveis. Fonte: Acervo Pessoal.
Cormem et. al. (2013) a rma que a contagem de n veis deve começar 
com zero. Outros autores divergem dessa ideia, a rmando que a 
contagem deve começar com um.
Além disso, quando temos duas ou mais árvores 
desconectadas em um mesmo programa, denominamos esse 
conjunto de árvores de floresta.
E com isso, finalizamos o nosso estudo sobre os termos 
usados para as árvores. Mas antes de encerrarmos, vejamos 
uma pequena recapitulação:
• Um nó é um dado contido na árvore.
• Uma árvore é um conjunto de nós.
• O nó de maior hierarquia, que não possui um pai, é 
denominado raiz.
• Os descendentes de um nó são chamados de filhos, 
enquanto que o superior de um nó é chamado de pai.
• Um grau é a quantidade de descendentes de um nó.
• Um nó é chamadode folha quando não tem 
descendentes.
• Quando temos duas ou mais árvores desconectadas, 
temos uma floresta.
Na próxima seção, vamos ver o que são as árvores 
binárias.
3 - Árvores Binárias
Uma árvore é chamada de binária quando todos os nós 
possuem grau menor ou igual a dois (ou seja, cada nó deve ter 
no máximo dois filhos). 
A implementação de uma árvore binária consiste em um 
mecanismo similar a uma lista dinâmica. Criamos um tipo que 
abriga um nó da árvore, onde consiste de três campos:
Um campo para armazenar o dado, que chamaremos de 
dado;
Um campo para armazenar um ponteiro para a subárvore 
esquerda, denominado de esq;
E um campo para armazenar um ponteiro para a 
subárvore direita, denominada de dir.
A seguir mostraremos a implementação de um tipo de 
uma árvore binária em pseudocódigo:
Tipo
 registro TArvore:
 dado: inteiro
 no_esq: *TArvore
 no_dir: *TArvore
fimregistro
Isso seria similar ao seguinte código em C/
C++:
typedef struct No{
 int dado
 struct No *esq
 struct No *dir
}
24
23
E com isso, finalizamos a nossa terceira aula. Não se 
esqueçam de fazer os exercícios e interagir com os seus colegas 
no seu painel do aluno. Na próxima aula, vamos fazer uma 
imersão maior nas árvores binárias. Até lá!
Retomando a aula
Chegamos ao nal da nossa terceira aula. Vamos 
relembrar?
1 - Entendendo as árvores
Nesta seção, vimos a necessidade de termos uma estrutura 
de dados que represente hierarquias. Assim, uma árvore, no 
campo das estruturas de dados, pode ser entendida como 
uma representação que demonstra uma hierarquia entre os 
dados armazenados, onde um dado contido nesse conjunto é 
subordinado a outro.
2 - Terminologia de uma árvore
Nesta seção, vimos que um nó é um dado contido na 
árvore. Uma árvore é um conjunto de nós. O nó de maior 
hierarquia, que não possui um pai, é denominado raiz. Os 
descendentes de um nó são chamados de filhos, enquanto que 
o superior de um nó é chamado de pai. Vimos também que um 
grau é a quantidade de descendentes de um nó, e que um nó 
é chamado de folha quando não tem descendentes. Por fim, 
vimos que, quando temos duas ou mais árvores desconectadas, 
temos uma floresta.
3 - Árvores Binárias
Nesta seção, vimos que uma árvore é chamada de binária 
quando todos os nós possuem grau menor ou igual a dois (ou 
seja, cada nó deve ter no máximo dois filhos). A implementação 
de uma árvore binária consiste em um mecanismo similar 
a uma lista dinâmica, com ponteiros que apontam para as 
subárvores direita e esquerda do nó.
CORMEN, Thomas H.; et. al.. Algoritmos: teoria e 
prática. Rio de Janeiro: Campus, 2012.
KNUTH, Donald Ervin. The art of computer 
programming. 3. ed. Amsterdam: Addison-Wesley, 1998.
SZWARCFITER, Jayme Luiz; MARKENZON, 
Vale a pena ler
SOUZA, Jairo Francisco de. Árvores. UFJF, 2009. 
Disponível em: <http://www.ufjf.br/jairo_souza/
files/2009/12/EDI-06.ED_.Arvores.pdf >. Acesso em: 14 
set. 2018.
Vale a pena acessar
Estrutura de Dados - Aula 15 - Árvores - Conceitos 
básicos. UNIVESP, 2016. Disponível em: < https://www.
youtube.com/watch?v=eiMMtyRBYCE>. Acesso em: 14 
set. 2018.
Vale a pena assistir
Vale a pena
Lilian. Estruturas de dados e seus algoritmos. 2. ed. Rio de 
Janeiro: LTC, 1994.
TENENBAUM, Aaron M.; AUGENSTEIN, Moshe 
J.; LANGSAN, Yedidyah. et al. Estruturas de dados usando 
C. São Paulo: Pearson Makron Books; São Paulo: Makron 
Books do Brasil; São Paulo: McGraw-Hill, 2013.
ZIVIANI, Nivio. Projeto de algoritmos: com 
implementação em PASCAL e C. 3. ed. São Paulo: Cengage 
Learning, 2011.
Minhas anotações
25