テクノロジ系
春期
基本情報技術者 2014年 春期 問6
6 / 80
分木の各ノードがもつ記号を出力する再帰的なプログラム Proc(2)の定義は、次 のとおりである。このブログラムを、図の2分木の根(最上位のノード)に適用した ときの出力はどれか。 Proc(n) { れに左の子があればProc(のを呼び出す。 nに右の子ィがあればProc(水)を呼び出す。 nの記号を出力して終了する。 }
正解と解説
表示する
正解 ウ
abc-d*+
Proc(n)は、左の子→右の子→自ノードの順(左部分木、右部分木を先に処理し最後にノードを出力)で、後行順(帰りがけ順)の走査です。2分木の根に適用すると、葉から順にたどって最後に根を出力するので、逆ポーランド記法にあたる『abc-d*+』が出力されます。