Uma árvore binária é uma estrutura que ou está vazia ou é formada por três conjuntos disjuntos: raiz, sub-árvore esquerda e sub-árvore direita. Cada uma dessas sub-árvores também é uma árvore binária e segue as mesmas regras da árvore principal. OLIVEIRA, Pietro Martins de; LEON, Rogério de. Estrutura de Dados II. Maringá-PR, Unicesumar, 2019. Para acessar os dados de uma árvore como essa existem algoritmos de caminhamento como o que você pode ver a seguir. void bar(NO* r){ if(r){ bar(r->esq); bar(r->dir); printf("%d \t", r->dado); //visita o nó atual } } A função bar representa o algoritmo de caminhamento pós-ordem para árvores binárias. Assim sendo, observe a árvore a seguir: Considere execução da invocação da função foo(), passando como parâmetro a referência para o nó raiz com valor igual a 20, da árvore ilustrada acima. Qual alternativa representa corretamente a mensagem que seria impressa na tela do usuário? Alternativas Alternativa 1: 20, 3, 21, 1, 8, 31, 0, 7, 30, 40 Alternativa 2: 0, 1, 7, 8, 3, 30, 40, 31, 21, 20 Alternativa 3: 20, 3, 1, 0, 8, 7, 21, 31, 30, 40 Alternativa 4: 0, 1, 3, 7, 8, 20, 30, 31, 40, 21 Alternativa 5: 20, 21, 31, 40, 30, 3, 8, 7, 1, 0
Soluções para a tarefa
Resposta:
Alternativa 3: 20 - 3 - 1 - 0 - 8 - 7 - 21 - 31 - 30 - 40
Explicação:
Função foo:
void foo(struct NO* r){
if(r){
printf("%d \t", r->val); //visita o nó atual
foo(r->esquerda);
foo(r->direita);
}
}
A função foo é pré-ordem, então a ordem de visitação:
Livro Página 42
O caminhamento pré-ordem, também conhecido por caminhamento pré-fixado, marca primeiramente a raiz como visitada, e só depois visitamos as subárvores esquerda e direita, respectivamente.
A mensagem que será impressa na tela do usuário é 0, 1, 7, 8, 3, 30, 40, 31, 21, 20. O que é mostrado corretamente na alternativa 2.
Árvore binária: caminhamento pós-ordem
Na categoria de caminhamento denominada por pós-ordem, deve-se partir da raiz, de forma a visitar todos os nós da subárvore esquerda, depois os subnós da subárvore direita e, por último, o nó na raiz.
O caminhamento pós-ordem será repetido para cada nó, de forma realizando esse algoritmo obtém a seguinte mensagem na tela do usuário: 0, 1, 7, 8, 3, 30, 40, 31, 21, 20.
Saiba mais sobre árvore binária em:
https://brainly.com.br/tarefa/22409421
Bons estudos!
#SPJ2
