使用前序走訪搭配波蘭式（Polish notation）
「運算式樹」（expression trees）是一種用來表示算術運算式的「二元樹」。
對運算式樹執行「中序」（in-order）走訪，可以得到「中綴表示法」（infix notation）。針對上圖的樹，此表示法為 (10-5)*3。
對運算式樹執行「前序」（pre-order）走訪，可以得到「前綴表示法」（prefix notation），也就是「波蘭式」（Polish notation），運算子會出現在運算元之前。針對上圖的樹，此表示法為 *-10 5 3。
對運算式樹執行「後序」（post-order）走訪，可以得到「後綴表示法」（postfix notation），也就是「逆波蘭式」（reverse Polish notation），運算子會出現在運算元之後。針對上圖的樹，此表示法為 10 5- 3*。
請撰寫「前序」走訪的程式碼，讓你可以取得此運算式樹的前綴表示法。
本練習屬於課程
Data Structures and Algorithms in Python
練習說明
- 檢查
current_node是否存在。 - 印出
current_node的值。 - 在樹的適當子樹上，遞迴呼叫
pre_order()函式。
動手互動練習
試著完成這個範例程式碼，體驗一下這個練習。
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)