2分木の各ノードがもつ記号を出力する再帰的なプログラムProc(ノードn )は、次のように定義される。
このプログラムを、図の2分木の根(最上位のノード)に適用したときの出力はどれか。
Proc(ノードn ) { n に左の子l があればProc(l )を呼び出す。 n に右の子r があればProc(r )を呼び出す。 n に書かれた記号を出力する } |
ア | + a * - b c d |
イ | a + b - c * d |
ウ | a b c - d * + |
エ | b - c * d + a |
答え ウ
【解説】
まず、問題の2分木の根であるノード『+』に対しプログラムProc( )を適用します。
@ | ノード『+』は左の子『a』があるので、『a』に対しプログラムProc( )を適用します。 |
A | ノード『a』は子がないので、『a』を出力します。 |
B | ノード『+』の左の子の処理が終わったので、右の子の処理を行います。 ノード『+』は右の子『*』があるので、『*』に対しプログラムProc( )を適用します。 |
C | ノード『*』は左の子『-』があるので、『-』に対しプログラムProc( )を適用します。 |
D | ノード『-』は左の子『b』があるので、『b』に対しプログラムProc( )を適用します。 |
E | ノード『b』は子がないので、『b』を出力します。 |
F | ノード『-』の左の子の処理が終わったので、右の子の処理を行います。 ノード『-』は右の子『c』があるので、『c』に対しプログラムProc( )を適用します。 |
G | ノード『c』は子がないので、『c』を出力します。 |
H | ノード『-』の左右の子の処理が終わったので、『-』を出力します。 |
I | ノード『*』の左の子の処理が終わったので、右の子の処理を行います。 ノード『*』は右の子『d』があるので、『d』に対しプログラムProc( )を適用します。 |
J | ノード『d』は子がないので、『d』を出力します。 |
K | ノード『*』の左右の子の処理が終わったので、『*』を出力します。 |
L | ノード『+』の左右の子の処理が終わったので、『+』を出力します。 |
【キーワード】
・2分木