A sequência de nós visitados no caminhamento pré-fixado à esquerda (Raiz, Esq, Dir) para uma Árvore Binária de Busca é 44,30,12,26,36,33,92,64,46,98. Qual seria a sequência de nós no caminhamento pré-fixado à direita (Raiz, Dir, Esq) para a mesma árvore?

Passo 1

Temos uma Árvore Binária de Busca e conhecemos o caminhamento pré-fixado à esquerda (Raiz, Esq, Dir):
44,\,30,\,12,\,26,\,36,\,33,\,92,\,64,\,46,\,98.
O que queremos é o caminhamento pré-fixado à direita (Raiz, Dir, Esq). Para isso, primeiro vamos reconstruir a árvore a partir dessa sequência usando a propriedade de BST (valores menores que a raiz vão para a subárvore esquerda e valores maiores vão para a subárvore direita).

Passo 2

Reconstruindo recursivamente:
  1. A raiz é 44.
  2. Os elementos seguintes menores que 44 formam a subárvore esquerda:
30,\,12,\,26,\,36,\,33.
Dela, a raiz é 30; os menores que 30 são 12,26 (raiz 12, só tem subárvore direita com 26); os maiores que 30 mas menores que 44 são 36,33 (raiz 36, só tem subárvore esquerda com 33).
3. Os elementos maiores que 44 formam a subárvore direita:
92,\,64,\,46,\,98.
Dela, a raiz é 92; os menores que 92 mas maiores que 44 são 64,46 (raiz 64, só tem subárvore esquerda com 46); o único maior que 92 é 98 (subárvore direita).
Assim a árvore fica:
\begin{array}{c} \quad\;44\\\ \diagdown\quad\;\diagup\\\\ 30\quad\;92\\\ \begin{array}{c}\diagdown\;\diagup\\\ 12\quad36\\\;\diagup\;\;\diagdown\\\ 26\;33\end{array} \quad \begin{array}{c}\diagdown\;\diagup\\\ 64\quad98\\diagdown\\\ 46\end{array} \end{array}

Passo 3

Agora fazemos o caminhamento pré-fixado à direita (Raiz, Dir, Esq) nesta árvore:
  1. Visito a raiz 44.
  2. Vou para a subárvore direita de 44:
  • Visito 92.
  • Subárvore direita de 92: visito 98.
  • Subárvore esquerda de 92: visito 64, depois sua subárvore direita (vazia) e depois sua subárvore esquerda: 46.
  1. Agora a subárvore esquerda de 44:
  • Visito 30.
  • Subárvore direita de 30: visito 36, depois direita (vazia) e depois esquerda: 33.
  • Subárvore esquerda de 30: visito 12, depois direita: 26, depois esquerda (vazia).
Juntando tudo, obtemos:

Resposta

44,\,92,\,98,\,64,\,46,\,30,\,36,\,33,\,12,\,26

Exercícios relacionados