第2種情報処理技術者試験 1994年度 = 平成6年度・秋期 午前 問31

 二分木を入力するためのテキスト表現として、
(左部分木の節番号又はテキスト表現、節番号、右部分木の節番号又はテキスト表現)
と記述する方法を採用した。部分木が空のときは x を書く。図のように節に番号をつけたとき、テキスト表現として正しいものはどれか。

     3           ●          / \       2●   ●5     /   / \   1●  4●   ●6


 ア ((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))

解答

 エ

解説

 まず、根とその子に着目しましょう。

    3    / \   L   R

 入力形式は、
  (左部分木の節番号又はテキスト表現、節番号、右部分木の節番号又はテキスト表現)
ですから、
  (L, 3, R)
となります。ここで、Lは、

    2    /   1

であり、右の子は空ですから、入力テキストは(1, 2, x)です。したがって、
  ((1, 2, x), 3, R)
となります。また、Rは、

    5    / \   4   6

であり、入力テキストは(4, 5, 6)です。したがって、全体の入力形式は
  (1, 2, x), 3, (4, 5, 6)
となります。


BohYoh.comトップページへ