Caminhamento em árvore

Prévia do material em texto

Caminhamento em árvore
APRESENTAÇÃO
As árvores são estruturas de dados que podem armazenar informações importantes, como, por e
xemplo, o resultado de uma busca em um banco de dados. Em posse dessas informações, pode-s
e escolher realizar alguma operação com esses dados, percorrendo cada um dos nós.
Nesta Unidade de Aprendizagem, você vai estudar as formas de percorrer as árvores, també
m conhecidas como caminhamento em uma árvore.
Bons estudos.
Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:
Reconhecer o caminhamento pós-ordem.•
Aplicar o caminhamento em pré-ordem.•
Utilizar o caminhamento in-ordem.•
DESAFIO
Imagine a seguinte situação:
A partir disso, responda: Qual estrutura você poderia utilizar para representar a conexão en
tre as portas do labirinto? E que algoritmo de caminhamento poderia ser utilizado para qu
e ao final do percurso ficasse clara a conexão entre cada porta?
INFOGRÁFICO
Neste Infográfico, você vai visualizar um breve resumo de como são feitos os três tipos de c
aminhamento.
Lembrando que o caminhamento é a maneira como se percorre uma árvore. Assim, os três 
métodos mostrados aqui diferem-se pela ordem em que os nós são visitados.
Confira:
CONTEÚDO DO LIVRO
O caminhamento em uma árvore é o ato de percorrer essa árvore de tal forma que todos os nós s
ejam visitados uma única vez. Por visitar, entende-se realizar alguma operação sobre o nó: impri
mir, realizar operações sobre as informações, etc.
No capítulo Caminhamento em árvore, do livro Estrutura de dados, você vai avaliar três form
as possíveis de realizar esse caminhamento: LNR (pós-ordem), NLR (pré-ordem) e LNR (in-ord
em).
Boa leitura.
ESTRUTURA 
DE DADOS
Marcela Santos
 
Caminhamento em árvore
Objetivos de aprendizagem
Ao final deste texto, você deve apresentar os seguintes aprendizados:
  Aplicar conceitos de LRN (pós-ordem).
  Reconhecer conceitos de NLR (pré-ordem).
  Definir conceitos de LNR (in-ordem).
Introdução
As árvores são estruturas de dados que podem armazenar informações 
importantes, como, por exemplo, o resultado de uma busca em um banco 
de dados. De posse dessas informações, pode-se escolher realizar alguma 
operação com esses dados, percorrendo cada um dos nós.
Neste capítulo, você estudará as formas de percorrer as árvores, tam-
bém conhecidas como caminhamento em uma árvore.
Conceitos de LRN (pós-ordem)
Para percorrer uma árvore binária em pós-ordem, deve-se:
  percorrer a subárvore esquerda em pós-ordem;
  percorrer a subárvore direita em pós-ordem;
  visitar a raiz.
Observe a árvore da Figura 1.
Figura 1. Exemplo de árvore.
6
2
4
3 5
1
8
A seguir você verá como podemos fazer o percurso em pós-ordem: 
1. Começamos na raiz 6 e percorremos a subárvore à esquerda.
2. Agora podemos pensar na subárvore à esquerda como uma árvore 
binária, cuja raiz é o nó 2.
3. Precisamos percorrer, nesse momento, a subárvore à esquerda do nó 2.
4. Agora a subárvore à esquerda com nó com 1 como elemento será nossa 
árvore, enquanto o nó raiz será o nó 1.
5. Pronto, essa árvore não tem subárvores, podemos visitar o nó raiz: o nó 1.
6. Voltamos para a árvore cujo nó raiz é 2. Vamos para a sua subárvore 
à direita.
7. Temos então uma subárvore cujo nó raiz é 4. Vamos percorrer sua 
subárvore à esquerda.
8. Agora a árvore tem como raiz o nó 3, que não possui subárvores.
9. Visitamos o nó 3.
10. Voltamos para a raiz 4 e percorremos a subárvore à direita.
11. Visitamos o nó 5.
12. Visitamos o nó 4.
13. Voltamos para o nó 2.
Caminhamento em árvore2
14. Visitamos o nó 2.
15. Voltamos ao nó 6. Vamos percorrer sua subárvore à direita.
16. Visitamos o nó 8.
17. E, por fim, visitamos o nó 6.
Assim, o percurso em pós-ordem (1 3 5 4 2 8 6) tem uso prático quando 
temos uma expressão aritmética representada por meio de uma árvore binária. 
Veja a seguinte expressão aritmética: 
[(a+b)÷(c-d)]∙(e-f)
Uma árvore binária que representa essa expressão pode ser vista a seguir: 
O percurso em pós-ordem dessa árvore é:
a∙b + c∙d − / e∙f + 
Essa representação de uma expressão aritmética é conhecida como notação reversa 
ou polonesa, em que o operador fica no final dos operandos.
Usando a representação de lista encadeada para construção da árvore, podemos 
implementar uma função em linguagem C, como se segue:
3Caminhamento em árvore
A representação de árvore binária, bem como as implementações das funções utilizadas 
aqui, são exemplos de como podemos implementar computacionalmente uma árvore 
binária, não sendo esta a única forma existente.
Conceitos de NLR (pré-ordem)
Para percorrermos uma árvore binária em pré-ordem, realizamos a seguinte 
ordem de operações:
  visitar a raiz;
  percorrer a sua subárvore à esquerda em pré-ordem;
  percorrer a sua subárvore à direita em pré-ordem.
Assim, o percurso em pré-ordem dessa árvore (ver Figura 1) é: 6 2 1 4 3 
5 8. O caminhamento em pré-ordem também é conhecido por percurso em 
profundidade (depth-first). Note que esse tipo de percurso segue os nós mais 
profundos das subárvores à esquerda e depois à direita.
O código-fonte desse percurso, usando recursão, pode ser visto na Figura 2.
Figura 2. Código-fonte do percurso.
Caminhamento em árvore4
A memória de um computador é o meio físico para armazenar dados de forma tem-
porária ou permanente. Para saber mais consulte o livro “Redes de computadores” 
(TANENBAUM, 1997).
Conceitos de LNR (in-ordem)
Este é o último tipo de caminhamento a percorrer uma árvore binária in-ordem. 
Esse caminhamento é feito da seguinte forma: 
  percorrer a sua subárvore à esquerda em in-ordem;
  visitar a raiz;
  percorrer a sua subárvore à direita em in-ordem.
Como exemplo, vamos usar a mesma árvore usada nos caminhamentos 
anteriores (Figura 1).
Assim o percurso em in-ordem dessa árvore é 1 2 3 4 5 6 8, ou seja, esse 
percurso nos dá os elementos em ordem e esse caminhamento também é co-
nhecido como caminhamento simétrico. O código-fonte para o caminhamento 
in-ordem pode ser visto na Figura 3.
Figura 3. Código-fonte para o caminhamento in-ordem.
5Caminhamento em árvore
Analisando os três métodos, é possível observar que a diferença entre as 
três técnicas é somente a ordem que visitamos a raiz. Outro detalhe é que 
sempre são visitados os descendentes do lado esquerdo para depois os do 
lado direito (Quadro 1).
 Tipo de caminhamento Ordem 
Pós-ordem
  Percorrer a subárvore à esquerda em 
pós-ordem
  Percorrer a subárvore à direita em 
pós-ordem
  Visitar a raiz
Pré-ordem
  Visitar a raiz
  Percorrer a sua subárvore à esquerda em 
pré-ordem
  Percorrer a sua subárvore à direita em 
pré-ordem
In-ordem
  Percorrer a sua subárvore à esquerda em 
in-ordem
  Visitar a raiz
  Percorrer a sua subárvore à direita em 
in-ordem
 Quadro 1. Caminhamento e ordens. 
Para saber mais sobre árvores binárias, acesse o link ou 
código a seguir.
https://goo.gl/nLTsk9
Caminhamento em árvore6
GRONER, L. Estruturas de dados e algoritmos em JavaScript. São Paulo: Novatec, 2017.
SZWARCFITER, J. L.; MARKENZON, L. Estruturas de dados e seus algoritmos. 3. ed. Rio 
de Janeiro: LTC, 2010. 
TANENBAUM, A. S. Redes de computadores. Rio de Janeiro: Campus, 1997.
Leituras recomendadas
7Caminhamento em árvore
 
Encerra aqui o trecho do livro disponibilizado para 
esta Unidade de Aprendizagem. Na Biblioteca Virtual 
da Instituição, você encontra a obra na íntegra.
Conteúdo:
DICA DO PROFESSOR
Uma das formas de se realizar o caminhamento em uma árvore é o caminhamento in-ordem.
Nesta Dica do Professor, você verá um exemplo com todas as etapas desse caminhamento, toma
ndo como base uma árvore binária de busca. Não deixe de assistir!
Aponte a câmera para o código e acesse o link do vídeo ou clique no código para acessar.
EXERCÍCIOS
1) Assinale a ordem de exibição se for executado o algoritmo de caminhamento em pré-o
rdem para a seguinte árvore:
A) 
ABCDEFG.
B) 
ABECDFG.
https://fast.player.liquidplatform.com/pApiv2/embed/cee29914fad5b594d8f5918df1e801fd/2317fc3ff6d6aacfce69387ebc3a4368C) 
CBDAFEG.
D) 
CDBFEGA.
E) 
É impossível gerar o percurso somente com a chave dos nós da árvore.
2) Qual a ordem de caminhamento que retorna os seus nós em ordem crescente para a ár
vore a seguir?
A) 
Caminhamento em pós-ordem.
 
 
B) 
Caminhamento pré-fixado.
C) 
Caminhamento in-ordem.
D) 
Caminhamento em largura.
E) 
Caminhamento em profundidade.
3) Qual a diferença entre os caminhamentos pré-ordem, in-ordem e pós-ordem em uma 
árvore binária, levando em consideração a implementação feita em C e usando recurs
ão?
A) 
A ordem em que os nós são visitados.
B) 
O tipo de elemento que pode ser acessado por cada tipo de caminhamento.
C) 
Não existe diferença entre esses caminhamentos, são somente formas diferentes de ter a m
esma saída quando se percorre uma árvore.
D) 
O tempo de execução do algoritmo.
E) 
A complexidade do algoritmo.
4) Qual a sequência de saída para a árvore a seguir se o algoritmo de pós-ordem for exec
utado?
A) 
3 7 6 12 24 15 8.
B) 
3 6 7 8 12 15 24.
C) 
8 6 3 7 15 12 24.
D) 
8 6 15 3 7 12 24.
E) 
Não é possível definir.
5) Indique qual o tipo de caminhamento é implementado pelo strecho de código a seguir:
A) 
Caminhamento em ordem.
B) 
Caminhamento pós-ordem.
C) 
Caminhamento pré-ordem.
D) 
Caminhamento em profundidade.
E) 
Caminhamento em largura.
NA PRÁTICA
Andrea está fazendo análise de dados de uma base gigantesca que guarda as temperaturas do mê
s de janeiro da cidade de Porto Alegre. Ela fez uma busca e obteve todas as temperaturas médias 
de todos os dias.
Após ter obtido o resultado dessa busca, Andrea excluiu os valores repetidos e, agora, procura sa
ber qual foi a maior e a menor temperatura registrada neste mês na capital do Rio Grande do Su
l.
Utilizando seus conhecimentos sobre estrutura de dados, ela procura resolver o problema da seg
uinte forma: 
SAIBA +
Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do professo
r:
[ED] Aula 73 - Percorrendo uma árvore binária
Este vídeo mostra como podemos percorrer uma árvore binária.
Aponte a câmera para o código e acesse o link do vídeo ou clique no código para acessar.
https://www.youtube.com/embed/z7XwVVYQRAA
Binary tree traversal: Preorder, Inorder, Postorder
Aprenda um pouco sobre mais sobre os percursos em árvore binária. Não esqueça de habilitar a l
egenda para acompanhar o vídeo e os exemplos.
Aponte a câmera para o código e acesse o link do vídeo ou clique no código para acessar.
Binary tree traversal - breadth-first and depth-first strategies
Que tal aprender o que é um caminhamento por profundidade e um caminhamento por largura? 
Habilite a legenda para acompanhar o vídeo e os exemplos.
Aponte a câmera para o código e acesse o link do vídeo ou clique no código para acessar.
https://www.youtube.com/embed/gm8DUJJhmY4
https://www.youtube.com/embed/9RHO6jU--GU