Pre-Order Traversal mit polnischer Notation verwenden

Ausdrucksbäume sind eine Art Binärbaum, der arithmetische Ausdrücke darstellt:

Grafische Darstellung eines Binärbaums, der arithmetische Ausdrücke enthält.

Wenn du einen Ausdrucksbaum in Reihenfolge durchläufst, erhältst du die Infix-Notation. Diese Schreibweise für den gegebenen Baum lautet (10-5)*3.

Wenn du einen Ausdrucksbaum vor der Reihenfolge durchläufst, erhältst du die Präfix-Notation, auch bekannt als polnische Notation, bei der der Operator vor seinen Operanden erscheint. Diese Schreibweise für den gegebenen Baum lautet *-10 5 3.

Wenn du einen Ausdrucksbaum nach der Reihenfolge durchläufst, erhältst du die Postfix-Notation, auch bekannt als umgekehrte polnische Notation, bei der der Operator nach seinen Operanden erscheint. Diese Schreibweise für den gegebenen Baum lautet 10 5- 3*.

Kodiere das Pre-Order-Traversal so, dass du die Präfix-Notation dieses Ausdrucksbaums erhalten kannst.

Diese Übung ist Teil des Kurses

Datenstrukturen und Algorithmen in Python

Kurs anzeigen

Anleitung zur Übung

Prüfe, ob current_node existiert.
Drucke den Wert der current_node.
Rufe die Funktion pre_order() rekursiv für die entsprechenden Hälften des Baums auf.

Interaktive Übung

Versuche dich an dieser Übung, indem du diesen Beispielcode vervollständigst.

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 bearbeiten und ausführen