行きがけ順走査とポーランド記法
式木は、数式をツリー構造で表す二分木の一種です。
式木に通りがけ順走査を適用すると、中置記法が取得できます。このツリーにおける中置記法は(10-5)*3です。
式木に行きがけ順走査を適用すると、前置記法（ポーランド記法とも呼ばれます）が取得できます。この記法では、演算子がオペランドの前に置かれます。このツリーにおける前置記法は*-10 5 3です。
式木に帰りがけ順走査を適用すると、後置記法（逆ポーランド記法とも呼ばれます）が取得できます。この記法では、演算子がオペランドの後に置かれます。このツリーにおける後置記法は10 5- 3*です。
この式木の前置記法を取得できるよう、行きがけ順走査をコーディングしましょう。
この演習はコースの一部です
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)