Resolução da Questão 9 de 2008

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:

 

D

 

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:

 

D – B

 

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:

 

D – B – A

 

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:

 

D – B – A – E

 

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:

 

D – B – A – E – G

  

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:

 

D – B – A – E – G – C

 

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.

 

 

 

 

2 opiniões sobre “Resolução da Questão 9 de 2008”

    Apenas colaboradores que estejam logados podem acessar os comentários!