Pre-order traverseren met Poolse notatie

Expressiebomen zijn een soort binaire boom die rekenkundige expressies voorstellen:

Graphical representation of a binary tree that has arithmetic expressions.

Door in-order te traverseren over een expressieboom krijg je de infixnotatie. Voor de gegeven boom is die notatie (10-5)*3.

Door pre-order te traverseren over een expressieboom krijg je de prefixnotatie, ook wel Poolse notatie, waarbij de operator vóór zijn operanden staat. Voor de gegeven boom is die notatie *-10 5 3.

Door post-order te traverseren over een expressieboom krijg je de postfixnotatie, ook wel omgekeerde Poolse notatie, waarbij de operator ná zijn operanden staat. Voor de gegeven boom is die notatie 10 5- 3*.

Codeer de pre-order traversie zodat je de prefixnotatie van deze expressieboom kunt verkrijgen.

Deze oefening maakt deel uit van de cursus

Datastructuren en algoritmen in Python

Cursus bekijken

Oefeninstructies

Controleer of current_node bestaat.
Print de waarde van current_node.
Roep de functie pre_order() recursief aan op de juiste takken van de boom.

Praktische interactieve oefening

Probeer deze oefening eens door deze voorbeeldcode in te vullen.

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)

Code bewerken en uitvoeren