Algorítmos e estrutura de
dados III
Carlos Oberdan Rolim
Ciência da Computação
Percurso em árvores binárias
Percurso
Percurso é uma visita sistemática a cada um dos nós da
árvore
É necessário ter métodos para percorrer os elementos
da árvore
O que significa “visitar” um nó?
é uma abstração
pode ser: imprimir, alterar dados, gravar em arquivo ... ...
Percurso (cont...)
Objetivo: visitar os nós da árvore exatamente uma vez
muitas vezes será necessário passar pelos nós sem visitá-los
Passos no percurso:
visitar a raíz
fazer um percurso na sub-árvore esquerda
fazer um percurso na sub-árvore direita
Percurso (cont...)
Os três passos compõem um algoritmo recursivo
resta saber qual a ordem de execução dos mesmos
Tipos de percurso
pre-ordem
in-ordem
pos-ordem
Percurso pre-ordem / Préfixa
Ordem dos passos
Visitar a raíz
percorrer sub-árvore esquerda, em pre-ordem
percorrer sub-árvore direita, em pre-ordem
Algoritmo:
Procedimento pre ( p )
visita ( p )
Se ( p→esq != NULL ) então
pre ( p →esq )
Se ( p→dir != NULL ) então
pre( p →dir )
Percurso pre-ordem (cont...)
A–B–D–G–C– E–H–I–F
Percurso in-ordem / Infixa
Ordem dos passos
percorrer sub-árvore esquerda, em in-ordem
Visitar a raíz
percorrer sub-árvore direita, em in-ordem
Algoritmo:
Procedimento in ( p )
Se ( p→esq != NULL ) então
in ( p →esq )
visita ( p )
Se ( p→dir != NULL ) então
in ( p →dir )
Percurso in-ordem (cont...)
D–G–B–A–H–E–I–C–F
Percurso pos-ordem / Pósfixa
Ordem dos passos
percorrer sub-árvore esquerda, em pos-ordem
percorrer sub-árvore direita, em pos-ordem
Visitar a raíz
Algoritmo:
Procedimento pos ( p )
Se ( p→esq != NULL ) então
pos ( p →esq )
Se ( p→dir != NULL ) então
pos ( p →dir )
visita ( p )
Percurso pos-ordem (cont...)
G–D–B–H–I–E–F–C–A
Resultados
A
B
C
Formas de passeio
Saídas
Em-ordem / Infixa
BA C
Pré-ordem / Préfixa
A BC
Pós-ordem / Pósfixa
BCA