IT Master

問題プレビューID: aee76ba9

問 6

2 分木の各ノードがもつ記号を出力する再帰的なプログラム Proc(nn) の定義は，次のとおりである。このプログラムを，図の 2 分木の根（最上位のノード）に適用したときの出力はどれか。

Proc(n) {
  nに左の子lがあればProc(l)を呼び出す。
  nに右の子rがあればProc(r)を呼び出す。
  nの記号を出力して終了する。
}
解説

Proc(nn) は「左の子を処理 → 右の子を処理 → 自分の記号を出力」の順に実行する，後行順（post-order）のたどり方である。

与えられた 2 分木をたどると，

  1. 根 + の左の子 a：子がないので a を出力。
  2. 根 + の右の子 *：
    • その左の子 −：左の子 b を出力，右の子 c を出力，− を出力 → bc−
    • その右の子 d を出力 → d
    • * を出力 → *
  3. 最後に根 + を出力。

出力を並べると a b c − d * +，すなわち abc−d*+ となる。正解は「ウ」である。