A sequência de nós visitados no caminhamento pré-fixado à esquerda (Raiz, Esq, Dir) para uma Árvore Binária de Busca é
. 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):
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:
- A raiz é
. - Os elementos seguintes menores que
formam a subárvore esquerda:
Dela, a raiz é
; os menores que
são
(raiz
, só tem subárvore direita com
); os maiores que
mas menores que
são
(raiz
, só tem subárvore esquerda com
).
3. Os elementos maiores que formam a subárvore direita:
3. Os elementos maiores que
Dela, a raiz é
; os menores que
mas maiores que
são
(raiz
, só tem subárvore esquerda com
); o único maior que
é
(subárvore direita).
Assim a árvore fica:
Passo 3
Agora fazemos o caminhamento pré-fixado à direita (Raiz, Dir, Esq) nesta árvore:
- Visito a raiz
. - Vou para a subárvore direita de
:
- Visito
. - Subárvore direita de
: visito . - Subárvore esquerda de
: visito , depois sua subárvore direita (vazia) e depois sua subárvore esquerda: .
- Agora a subárvore esquerda de
:
- Visito
. - Subárvore direita de
: visito , depois direita (vazia) e depois esquerda: . - Subárvore esquerda de
: visito , depois direita: , depois esquerda (vazia).
Juntando tudo, obtemos: