アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 201101 実施分 問5
2分木を入力するためのテキスト表現を，次のように規定した。図のように節に番号をつけたとき，テキスト表現として適切なものはどれか。
〔テキスト表現〕
(1)（左部分木の節番号又はテキスト表現，節番号，右部分木の節番号又はテキスト表現）と表す。
(2) 部分木が空のときはxを書く。
2分木。根は節3。節3の左の子は節2，右の子は節5。節2の左の子は節1（節2の右の子は無し）。節5の左の子は節4，右の子は節6。
- ア ((1, 2), 3, (4, 5, 6))
- イ ((1, 2, 3), x, (4, 5, 6))
- ウ ((1, 2, x), 3, (4, 5, 6))
- エ ((1, 2, x), 3, (6, 5, 4))
出典：基本情報技術者試験 科目A免除 修了試験 201101 実施分 問5
答えと解説を見る
正解：ウ
覚える知識
2分木の巡回順序(帰りがけ順)
2分木の表現は(左部分木,根,右部分木)の再帰構造であり、空の部分木はxで表す。
この問題で必要なこと
(左,節番号,右)の形式(中間順)で再帰的に表す。節2は右が空でx、全体は((1,2,x),3,(4,5,6))。
ひっかけ
右部分木の空を省略する、順序を入れ替える表現と混同させる。
この知識の出題：本試験系 1 回・免除試験 6 回（公開問題での観測値）