1. 学ぶ
    2. /
  2. コース
    3. /
  3. Pythonで学ぶデータ構造とアルゴリズム
Connected

演習

ポーランド記法で先行順巡回を使う

式木 (expression tree) は、算術式を表す 二分木 の一種です。

Graphical representation of a binary tree that has arithmetic expressions.

式木に 中間順 (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* になります。

この式木の前置記法を得られるように、先行順 巡回を実装してください。

指示

100 XP
  • current_node が存在するかを確認します。
  • current_node の値を出力します。
  • 木のそれぞれ適切な部分に対して、pre_order() 関数を再帰的に呼び出します。