Przechodzenie pre-order i notacja polska

Drzewa wyrażeń to rodzaj drzewa binarnego reprezentującego wyrażenia arytmetyczne:

Graphical representation of a binary tree that has arithmetic expressions.

Stosując przechodzenie in-order do drzewa wyrażeń, otrzymasz notację infiksową. Dla przedstawionego drzewa będzie to (10-5)*3.

Stosując przechodzenie pre-order do drzewa wyrażeń, otrzymasz notację prefiksową, zwaną też notacją polską, w której operator poprzedza swoje operandy. Dla tego drzewa wynik to *-10 5 3.

Stosując przechodzenie post-order do drzewa wyrażeń, otrzymasz notację postfiksową, zwaną też odwrotną notacją polską, w której operator pojawia się po operandach. Dla tego drzewa wynik to 10 5- 3*.

Zaimplementuj przechodzenie pre-order, aby uzyskać notację prefiksową tego drzewa wyrażeń.

To ćwiczenie jest częścią kursu

Struktury danych i algorytmy w Pythonie

Zobacz kurs

Instrukcje do ćwiczenia

Sprawdź, czy current_node istnieje.
Wypisz wartość current_node.
Wywołaj funkcję pre_order() rekurencyjnie na odpowiednich częściach drzewa.

Interaktywne ćwiczenie praktyczne

Spróbuj tego ćwiczenia, uzupełniając ten przykładowy kod.

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)

Edytuj i uruchom kod