การใช้ pre-order traversal กับ Polish notation

Expression tree คือ binary tree ประเภทหนึ่งที่ใช้แทนนิพจน์ทางคณิตศาสตร์:

Graphical representation of a binary tree that has arithmetic expressions.

การใช้ in-order traversal กับ expression tree จะได้ infix notation ซึ่งสำหรับต้นไม้นี้คือ (10-5)*3

การใช้ pre-order traversal จะได้ prefix notation หรือที่เรียกว่า Polish notation ซึ่ง operator จะอยู่ก่อน operand สำหรับต้นไม้นี้คือ *-10 5 3

การใช้ post-order traversal จะได้ postfix notation หรือที่เรียกว่า reverse Polish notation ซึ่ง operator จะอยู่หลัง operand สำหรับต้นไม้นี้คือ 10 5- 3*

เขียนโค้ด pre-order traversal เพื่อให้ได้ prefix notation ของ expression tree นี้

แบบฝึกหัดนี้เป็นส่วนหนึ่งของหลักสูตร

โครงสร้างข้อมูลและอัลกอริทึมใน Python

ดูคอร์ส

คำแนะนำการฝึกหัด

ตรวจสอบว่า current_node มีอยู่หรือไม่
แสดงค่าของ current_node
เรียกฟังก์ชัน pre_order() แบบ recursive บนแต่ละส่วนของต้นไม้ที่เหมาะสม

แบบฝึกหัดเชิงโต้ตอบแบบลงมือทำ

ลองทำแบบฝึกหัดนี้โดยเติมโค้ดตัวอย่างนี้ให้สมบูรณ์

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)

แก้ไขและรันโค้ด