Construa uma árvore enraizada ordenada correspondente à seguinte expressão aritmética:
(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
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:
Para resolver isso vamos precisar:
- Saber que cada operação vira um nó da árvore, com os operandos como filhos, na ordem esquerda→direita.
- 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.
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 =
:
- O topo dessa subárvore é o operador “
” (expoente). - Ele tem dois filhos, em ordem:
– filho esquerdo: a subárvore de
– filho direito: o valor - 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 =
:
- O nó raiz é “
”. - Filho esquerdo: subárvore de
.
– Isso é “” com filhos “x” e “4”. - 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
+
/ \
↑ ÷
/ \ / \
− 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 é:
- desço o filho esquerdo até o fim, escrevo tudo dele;
- depois faço o mesmo para o filho direito;
- só então escrevo o nó atual.
Passo 7
Aplicando isso na árvore inteira:
- Subárvore de A =
→ em pós-ordem:
–dá “9 3 −”
– depois o “2”
– e finalmente o “”
→ “9 3 − 2 ↑” - Subárvore de B =
→
–é “x 4 *”
–é “3 y +”
– depois o “”
→ “x 4 * 3 y + ÷” - 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
+
/ \
↑ ÷
/ \ / \
− 2 * +
/ \ / \
9 3 x 4 3 y
Em notação pós-ordem:
9 3 − 2 ↑ x 4 * 3 y + ÷ +
9 3 − 2 ↑ x 4 * 3 y + ÷ +