MO417 - Questão para a prova oral

Número: 2010-069

Enunciado: Percursos em árvores binárias podem ser implementados utilizando-se a ideia de busca em profundidade em grafos. Existem basicamente três tipos de percursos:

• pré-ordem: Primeiro se visita a raiz, depois a subárvore esquerda e então a subárvore direita
• in-ordem: Primeiro se visita a subárvore esquerda, depois a raiz e então a subárvore direita
• pós-ordem: Primeiro se visita a subárvore esquerda, depois a subárvore direita, e então a raiz

Um percurso em pré-ordem em uma árvore binária A visitou os vértices na sequência:
h, o, x, r, j, s, p, t, z, k, i.
Um outro percurso in-ordem na mesma árvore binária A visitou os vértices na sequência:
r, x, j, o, s, h, z, t, k, p, i.
Das alternativas abaixo, qual é um possível percurso pós-ordem para a árvore A?

1. i, p, t, z, k, h, o, s, x, j, r
2. r, j, s, x, o, z, k, i, t, p, h
3. i, z, k, t, p, s, j, r, x, o, h
4. r, j, x, s, o, z, k, t, i, p, h
5. NDA

Ideia original de: Leonardo de Paula Rosa Piga