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