[0152] 2分木,テキスト表現

平成12年度春期 (旧)第2情報処理技術者試験より
2分木を入力するためのテキスト表現を、次のように規定した。図のように節に番号をつけたとき、テキスト表現として正しいものはどれか。

[テキスト表現]

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

正解

解説

 2分木のテキスト表現に関する問題です。

 この2分木は、3つの部分木から構成されていると考えます。それぞれの部分木を下図のように、a、b、c とします。



・ aの部分木をテキスト表現すると、(b,3,c)
・ bの部分木をテキスト表現すると、(1,2,x)
・ cの部分木をテキスト表現すると、(4,5,6)

ここで、b、cの部分木を、aの部分木の節に代入すると、
    (b,3,c)= ((1,2,x),3,(4,5,6))
 となるので、ウが正解となります。
※ 解説の内容は執筆時点のものであり,含まれている情報の正確性,妥当性について保証するものではありません。ご注意ください・・・

関連する(かもしれない)問題