Construa uma árvore enraizada ordenada correspondente à seguinte expressão aritmética:
((9-3) uparrow 2)+((x cdot 4) div(3+y))
(b) Escreva a expressão na notação pós-ordem

Passo 1

Beleza, aqui o que a gente tem é uma expressão aritmética
((9-3)uparrow 2);+;((x cdot 4)div(3+y))
O assunto é “árvore sintática de expressão” (uma árvore enraizada ordenada) e também “notação pós-ordem” (post-order).
Para resolver isso vamos precisar:
  1. Saber que cada operação vira um nó da árvore, com os operandos como filhos, na ordem esquerda→direita.
  2. Entender como percorrer a árvore em pós-ordem: a gente visita primeiro todo o lado esquerdo, depois o direito, e só depois o nó raiz.

Passo 2

Bora dividir a expressão em duas partes ligadas pelo “+”:
A =
B =
Isso significa que na raiz da árvore vai ter o símbolo “+”, com a subárvore de A à esquerda e a de B à direita.

Passo 3

Vamos fazer a subárvore de A = :
  1. O topo dessa subárvore é o operador “ ” (expoente).
  2. Ele tem dois filhos, em ordem:
    – filho esquerdo: a subárvore de
    – filho direito: o valor
  3. A subárvore de é simples: nó “ ” com filhos “9” e “3”.
Então a árvore de A fica assim (usando notação de parênteses):

Passo 4

Agora a subárvore de B = :
  1. O nó raiz é “ ”.
  2. Filho esquerdo: subárvore de .
    – Isso é “ ” com filhos “x” e “4”.
  3. Filho direito: subárvore de .
    – Isso é “ ” com filhos “3” e “y”.
Em notação:

Passo 5

Juntando tudo, a árvore enraizada ordenada para a expressão completa é:
+
/ \
↑ ÷
/ \ / \
− 2 * +
/ \ / \ / \
9 3 x 4 3 y
Ou em notação textual de parênteses:

Passo 6

Agora vamos escrever a expressão em notação pós-ordem (post-order). A regra é:
  1. desço o filho esquerdo até o fim, escrevo tudo dele;
  2. depois faço o mesmo para o filho direito;
  3. só então escrevo o nó atual.

Passo 7

Aplicando isso na árvore inteira:
  1. Subárvore de A = → em pós-ordem:
    dá “9 3 −”
    – depois o “2”
    – e finalmente o “
    → “9 3 − 2 ↑”
  2. Subárvore de B =
    é “x 4 *”
    é “3 y +”
    – depois o “
    → “x 4 * 3 y + ÷”
  3. Por fim, junta A e B e coloca o “+”:
    “9 3 − 2 ↑ x 4 * 3 y + ÷ +”

Resposta

Árvore enraizada ordenada:
+
/ \
↑ ÷
/ \ / \
− 2 * +
/ \ / \
9 3 x 4 3 y
Em notação pós-ordem:
9 3 − 2 ↑ x 4 * 3 y + ÷ +

Exercícios relacionados