ポーランド記法で先行順巡回を使う
式木 (expression tree) は、算術式を表す 二分木 の一種です。
式木に 中間順 (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* になります。
この式木の前置記法を得られるように、先行順 巡回を実装してください。
この演習はコースの一部です
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)