Usando a passagem de pré-ordem com notação polonesa

As árvores de expressão são um tipo de árvore binária que representa expressões aritméticas:

Representação gráfica de uma árvore binária que possui expressões aritméticas.

Ao aplicar a passagem em ordem a uma árvore de expressão, você pode obter a notação infixa. Essa notação para a árvore em questão será (10-5)*3.

Ao aplicar a passagem de pré-ordem a uma árvore de expressão, você pode obter a notação de prefixo, também conhecida como notação polonesa, em que o operador aparece antes de seus operandos. Essa notação para a árvore em questão será *-10 5 3.

Ao aplicar a passagem pós-ordem a uma árvore de expressão, você pode obter a notação pós-fixa, também conhecida como notação polonesa reversa, em que o operador aparece depois de seus operandos. Essa notação para a árvore em questão será 10 5- 3*.

Codifique a travessia de pré-ordem para que você possa obter a notação de prefixo dessa árvore de expressão.

Este exercício faz parte do curso

Estruturas de dados e algoritmos em Python

Ver curso

Instruções do exercício

Verifique se o site current_node existe.
Imprima o valor do site current_node.
Chame a função pre_order() recursivamente nas metades apropriadas da árvore.

Exercício interativo prático

Experimente este exercício completando este código de exemplo.

import queue

class ExpressionTree:
  def __init__(self):
    self.root = None

  def pre_order(self, current_node):
    # Check if current_node exists
    ____:
      # Print the value of the current_node
      ____
      # Call pre_order recursively on the appropriate half of the tree
      ____
      ____
          
et = CreateExpressionTree()
et.pre_order(et.root)

Editar e executar o código