第２種情報処理技術者試験
2000年度 ＝ 平成12年度・春期
午前
問14
２分木を入力するためのテキスト表現を、次のように規定した。図のように節に番号をつけたとき、テキスト表現として正しいものはどれか。
〔テキスト表現〕
(1)
（左部分木の節番号又はテキスト表現，節番号，右部分木の節番号又はテキスト表現）と表す。
(2)
部分木が空のときはxを書く。
３ ● ２／ ＼５ ● ● １／ ４／ ＼６ ● ● ●
ア ((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))
解答
ウ
解説
まず、根とその子に着目しましょう。
３ ／ ＼ Ｌ Ｒ
入力形式は、
(左部分木の節番号又はテキスト表現，節番号，右部分木の節番号又はテキスト表現)
ですから、
(L, 3, R)
となります。ここで、Ｌは、
２ ／ １
であり、右の子は空ですから、入力テキストは(1, 2, x)です。したがって、
((1, 2, x), 3, R)
となります。また、Ｒは、
５ ／ ＼ ４ ６
であり、入力テキストは(4, 5, 6)です。したがって、全体の入力形式は
(1, 2, x), 3, (4, 5, 6)
となります。
