Pre-order-traversering med polsk notation

Uttrycksträd är en typ av binärt träd som representerar aritmetiska uttryck:

Graphical representation of a binary tree that has arithmetic expressions.

Genom att använda in-order-traversering på ett uttrycksträd får du infixnotation. För det givna trädet blir notationen (10-5)*3.

Genom att använda pre-order-traversering på ett uttrycksträd får du prefixnotation, även kallad polsk notation, där operatorn placeras före sina operander. För det givna trädet blir notationen *-10 5 3.

Genom att använda post-order-traversering på ett uttrycksträd får du postfixnotation, även kallad omvänd polsk notation, där operatorn placeras efter sina operander. För det givna trädet blir notationen 10 5- 3*.

Implementera pre-order-traversering så att du kan få fram prefixnotationen för det här uttrycksträdet.

Den här övningen är en del av kursen

Datastrukturer och algoritmer i Python

Visa kurs

Övningsinstruktioner

Kontrollera om current_node finns.
Skriv ut värdet för current_node.
Anropa funktionen pre_order() rekursivt på lämpliga delar av trädet.

Interaktiv övning med praktiskt arbete

Testa den här övningen genom att slutföra den här exempelkoden.

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)

Redigera och kör kod