Existe caminhamento em árvores binárias da seguinte forma:
PRÉ-ORDEM, EM-ORDEM e PÓS-ORDEM.
Em árvores binárias temos os nós filhos, os pais e a raiz.
Tipo, na árvore abaixo a raiz é a letra (nó) A e os nós B e C são filhos de A, beleza?
Então o caminhamento em árvore binária segue as seguintes ordens, OU SEJA, FAZ PRIMEIRO:
1ª REGRA – PRÉ-ORDEM -> RAIZ, ESQUERDA e DIREITA;
2ª REGRA – EM-ORDEM -> ESQUERDA, RAÍZ e DIREITA; E
3ª REGRA – PÓS-ORDEM -> ESQUERDA, DIREIRA e RAIZ.
Vamos criar um memento para o que a questão quer e eu vou fazer de uma forma prática de compreensão.
Vamos à questão: 09 de 2008
Assinale a alternativa que representa uma ordem de caminhamento do tipo EM ORDEM para a árvore abaixo.
(A) D – B – A – E – G – C – H – F – I
(B) A – B – C – D – E – F – G – H – I
(C) A – B – D – C – E – G – F – H – I
(D) D – B – G – E – H – I – F – C – A
(E) D – B – A – G – E – C – H – F – I
Ela quer caminhamento em árvore binária EM-ORDEM, então usaremos a 2ª REGRA, OU SEJA:
ESQUERDA, RAÍZ e DIREITA.
Montando a historinha, LEMBRE-SE SÓ LEMOS DADOS QUANDO FALARMOS RAIZ.
Começando da raiz da árvore, olhe para o nó “A” ele tem algo na ESQUERDA? SIM. ENTÃO VAMOS PARA LÁ.
Olhe para o nó “B”, ele tem algo na ESQUERDA? SIM. ENTÃO VAMOS PARA LÁ.
Olhe para o o nó “D” ele tem algo na ESQUERDA? NÃO. ENTÃO VAMOS PARA A RAÍZ. QUEM É A RAIZ? O NÓ “D”, ENTÃO O GUARDAMOS:
Olhemos agora para a DIREITA DO “D”, TEM ALGO? NÃO. ENTÃO VAMOS PARA O NÓ SUPERIOR, do qual JÁ VIEMOS DA ESQUERDA, ENTÃO QUANDO VOLTARMOS PARA ELE ESTAMOS FAZENDO A LEITURA DA RAÍZ ENTÃO O GUARDAMOS:
Olhe para a DIREITA DE “B” TEM ALGO LÁ? NÃO. ENTÃO VAMOS PARA O NÓ “A”, DA QUAL JÁ VIEMOS DA ESQUERDA, ENTÃO ESTEREMOS LENDO O NÓ RAIZ, ENTÃO O GUADAMOS:
Agora olhe para a DIREITA DE “A”, TEM ALGO, SIM. ENTÃO VAMOS. CHEGAMOS EM “C”, TEM ALGO NA ESQUERDA DE “C”? SIM. ENTÃO VAMOS PARA LÁ.CHEGANDO EM “E”, TEM ALGO A ESQUERDA DE “E”? NÃO. ENTÃO DEVEREMOS, DE ACORDO COM A 2ª REGRA LER A RAIZ E GUARDA-LA:
JÁ SABEMOS QUE A RESPOSTA CERTA É A LETRA A, MAS VAMOS ATÉ ACABAR A ÁRVORE.
DEPOIS DE LER A RAIZ “E”, TEM ALGO À SUA DIREITA? SIM. ENTÃO VAMOS PÁRA LÁ. CHEGANDO EM “G” TEM ALGO À ESQUERDA DE “G”? NÃO. ENTÃO VAMOS LER E GUARDAR A RAÍZ:
TEM ALGO À DIREITA DE “G”? NÃO. ENTÃO VOLTEMOS A RAÍZ. A RAIZ JÁ FOI LIDA? SIM PASSAMOS PARA A RAIZ SUPERIOR. A RAIZ “C”, DEVEMOS GUARDA-LA:
HÁ ALGO À DIREITA DE “C’? SIM. ENTÃO VAMOS PARA LÁ.
CHEGANDO EM “F”. HÁ ALGO À ESUQRDA DE “F’? SIM. ENTÃO VAMOS PARA LÁ.
CHEGANDO EM “H”, TEM ALGO À ESQUERDA DE “H’? NÃO. ENTÃO VOLTAMOS À RAIZ QUE É O “H” E O GUARDAMOS:
D – B – A – E – G – C – H
HÁ ALHO À DIREITA DE “H”? NÃO. ENTÃO VAMOS PARA A RAIZ “F”, QUE DEVERÁ SER GUARDADA:
D – B – A – E – G – C – H – F
E FINALMENTE VAMOS PARA O NÓ “I” QUE NÃO TEM NADA NA SUA ESQUERDA E IRÁ LER “I” FICANDO O CAMINHAMENTO ASSIM:
D – B – A – E – G – C – H – F – I
ALTERNATIVA CORRETA – > LETRA A.
ESPERO TER AJUDADO A TODOS. VAMOS À LUTA.
