課題９　「二分探索木となぞり」

内容

　　今週の課題は以下の２つである。

	課題①：課題８にて作成した二分木を前順、中順、後順のなぞりで表示せよ。

	課題②：二分探索木に要素を挿入する手続きを作成し、作成した木を中順なぞりで表示せよ。
		ただし、二分探索木の要素の型は「整数型(integer)」とする。


　　※ プログラムは、ひとつにまとめても、それぞれ作成してもどちらでも構わない。

　　※ 二分探索木に同じ要素を挿入する場合は、以下のどちらかを選択すること。

	(ⅰ) 要素の重複を許さず、入力を無視する。
	(ⅱ) 要素の重複を許し、同じ要素の右の子孫(左の子孫でもよい。ただし、どちらかに統一すること)に挿入する。

　　　 以下に、(ⅱ)を選択した場合の二分探索木の例をあげる。

　　

入力

　　課題①：入力は必要ない。

　　課題②：入力は以下の２つとする。

	(ⅰ) 二分探索木に挿入する要素の数
	(ⅱ) 二分探索木に挿入する要素 (整数)

出力

　　課題①：課題８で作成した二分木の前順、中順、後順なぞりの結果。

　　課題②：作成した二分探索木の中順なぞりの結果。

実行

　　課題①：特に入力は無いので、プログラムを実行して各なぞりの出力結果を得なさい。

　　課題②：以下の手順で出力結果を得なさい。

	(1) 二分探索木に挿入する要素の数 ＝ 5
	(2) 挿入する要素 ＝ 4, 5, 2, 1, 3 （順番通りに入力）

ヒント

二分探索木

　　二分探索木とは、図2のようにあるノードＡの要素と、その左右の子孫の要素が

	ノードＡの左の子孫の要素 ＜ ノードＡの要素 ＜ ノードＡの右の子孫の要素		式(1)

　　となるような二分木のことである。

　　

木のなぞり

　　木のなぞりとは、木のノードの要素をある規則性にしたがって出力することである。
　　講義では、深さ優先探索のアルゴリズムを適用した、前順(preorder)、中順(inorder)、後順(postorder)のなぞりを学習したと思う。
　　インフルエンザ等で講義に出席できなかった学生や、まだ十分に理解できていない学生向けに、簡単になぞりについて説明する。

　　はじめに、基本となる木のなぞり方についてだが、教科書P.41 図2.26に示されているように、
　　木の根からなぞり始め、木の外周を反時計回りになぞっていく。(注意：これは二分木でも二分探索木でもない)
　　前順、中順、後順の違いは、このなぞりにおいてどのタイミングで要素を出力するかである。

　　

　　次に、説明をより簡略化するために二分木のとあるノードに注目し、各なぞりがどのタイミングで要素を出力するのかを説明する。
　　図3に、今回注目するノード（何らかのノードの左の子）を示す。

　　

　　このノード“n”は左右の子を所持しているため、木全体をなぞる間に

	(1) 初めて通過する（行きがけ）
	(2) 左の子孫をなぞり終えて通過する（通りがけ）
	(3) 右の子孫をなぞり終えて通過する（帰りがけ）

　　の計３回通ることになる。
　　この時、(1)のタイミングで要素を出力するのが前順、(2)のタイミングで要素を出力するのが中順、(3)のタイミングで要素を出力するのが後順である。

　　仮に、注目しているノードが左右の子を所持していなかった場合は(1)(2)(3)は同様のタイミングになり、
　　左の子を所持し、右の子を所持していなかった場合は(2)と(3)が同様のタイミングとなる。

　　また、二分探索木は式(1)のような大小関係があるため、
　　二分探索木に中順なぞりを適用すると要素がソートされるという性質がある。

出力例

　　今回は出力例を示すことで、逆に混乱を招きそうなので示さない。
　　課題①に関しては、課題８の二分木を各自なぞれば答を確認できる。
　　課題②に関しては、入力された要素がソートされるはずである。