Usare la visita in pre-ordine con la notazione polacca

Gli expression tree sono un tipo di albero binario che rappresenta espressioni aritmetiche:

Graphical representation of a binary tree that has arithmetic expressions.

Applicando la visita in-order a un expression tree, puoi ottenere la notazione infissa. La notazione per l’albero dato sarà (10-5)*3.

Applicando la visita pre-order a un expression tree, puoi ottenere la notazione prefissa, detta anche notazione polacca, in cui l’operatore compare prima dei suoi operandi. La notazione per l’albero dato sarà *-10 5 3.

Applicando la visita post-order a un expression tree, puoi ottenere la notazione postfissa, detta anche notazione polacca inversa, in cui l’operatore compare dopo i suoi operandi. La notazione per l’albero dato sarà 10 5- 3*.

Scrivi il codice della visita pre-order in modo da ottenere la notazione prefissa di questo expression tree.

Questo esercizio fa parte del corso

Strutture dati e algoritmi in Python

Visualizza il corso

Istruzioni dell'esercizio

Verifica che current_node esista.
Stampa il valore di current_node.
Chiama ricorsivamente la funzione pre_order() sulle parti appropriate dell’albero.

Esercizio pratico interattivo

Prova a risolvere questo esercizio completando il codice di esempio.

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)

Modifica ed esegui il codice