Construa uma árvore enraizada ordenada correspondente à seguinte expressão aritmética:
(a) Escreva a expressão na notação pré-ordem
Passo 1
Beleza, o problema pede pra gente construir a árvore enraizada e ordenada da expressão
e, em seguida, escrever essa mesma expressão na notação pré-ordem (prefixa).
Conteúdo: árvore de expressão aritmética e percurso pré-ordem.
O que vamos precisar:
Conteúdo: árvore de expressão aritmética e percurso pré-ordem.
O que vamos precisar:
- Saber identificar o operador “raiz” (o que está por último na prioridade, ou seja, o “+”).
- Montar recursivamente subárvores para cada operação.
- Fazer o percurso pré-ordem (raiz, depois subárvore esquerda, depois subárvore direita).
Passo 2
Primeiro, identificamos o operador principal da expressão toda. Como a soma “+” é a última a ser feita, ela vira o nó raiz da nossa árvore:
+
/ \
? ?
Na esquerda vai todo o “(9-3)↑2” e na direita vai “(x·4)÷(3+y)”.
Passo 3
Montando a subárvore da esquerda, ou seja, “(9-3)↑2”:
- O operador principal aqui é o “↑” (expoente), pois a subtração acontece antes, e o resultado é elevado a 2.
- Então “↑” é o nó, com dois filhos: a subárvore “9-3” e o número “2”.
- A subárvore “9-3” tem o “-” como nó, com folhas “9” e “3”.
Fica assim:
↑
/ \
- 2
/ \
9 3
Passo 4
Agora a subárvore da direita: “(x·4)÷(3+y)”
- Aqui o operador principal é “÷” (divisão).
- Ele tem duas subárvores: à esquerda “x·4” e à direita “3+y”.
- “x·4” vira um nó “·” com filhos “x” e “4”.
- “3+y” vira um nó “+” com filhos “3” e “y”.
Fica assim:
÷
/ \
· +
/ \ / \
x 4 3 y
Passo 5
Juntando tudo, nossa árvore completa é:
+
/ \
↑ ÷
/ \ / \
- 2 · +
/ \ / \ / \
9 3 x 4 3 y
Agora fazemos o percurso pré-ordem:
- Visito a raiz “+”.
- Vou inteiro na subárvore esquerda (pré-ordem dela).
- Depois vou inteiro na subárvore direita (pré-ordem dela).
Passo 6
Percurso pré-ordem da esquerda “↑”:
- ↑
-
- 9
- 3
- 2
Percurso pré-ordem da direita “÷”:
- ÷
- ·
- x
- 4
-
- 3
- y
Juntando tudo numa sequência só:
Resposta
A expressão em notação pré-ordem é: