ソフトウェア開発向け
根付き木とは,根と呼ばれる特別な節点から木の枝が分かれるように,幾つか
の辺が伸び,その先の節点から更に辺が伸びるということが繰り返されてできた
構造である。根付き木の各節点 v は,それぞれ 3 種類のポインタをもつ。Parent[v]:節点 v の親を指すポインタ
FirstChild[v]:節点 v の第 1 子を指すポインタ
NextBrother[v]:節点 v の次の兄弟を指すポインタ根
○
/|\
/ | \
○ ○ ○
親:
○
/|\ \
/ |↑\ \
/ | \ \ \
/ | | \ \
/ | | \ \
/ | ノ \ \
○ … (v) ────→○ … ○
/|\ 次の兄弟
/|| \
/ || \
/ ノ | \
/ / | \
○← / … ○ … ○
第 1子ポインタが指す相手がいないときには,NIL という記号で表される値がポイン
┌─┐
タに設定される。節点 v も含めて,その兄弟をすべて出力するとき,└─┘の
部分に入れる手続はどれか。ここで,節点 v は根ではなく,report x は節点 x
を出力する手続である。┌───┐
└───┘
While x ≠ NIL do
report x
x ← NextBrother[x]
ア x ← FirstChild[v]
イ x ← FirstChild[Parent[v]]
ウ x ← NextBrother[v]
エ x ← NextBrother[Parent[v]]
注意:桁がずれて表示されているときは以下のサイトを参考にして下さい。
http://www.mag2.com/faq/mua.htm【実習課題】実際にプログラムを作成してみよう。
【私の解答】
ア…第2子、第3子が表示される→不正解
イ…正解
ウ…vから次の兄弟が表示される。→不正解
エ…親の兄弟が表示される→不正解
【正解】
> ア:v の第 1 子をスタートとしているので、v の子供が全て出力される。
>
> イ:正解。
> v の親の第 1 子をスタートとしているので、長男(というべきか、
> v の左側)も含め、v の兄弟が全て出力される。
>
> ウ:v の次の兄弟をスタートとしているので、v より右側(弟たち)は
> 全て出力されるが、左側(お兄さん)は出力されない。
> v が含まれていない上に、v は第 1 子とは限らないので間違い。
>
> エ:v の親の次の兄弟をスタートとしているので、親の右側の兄弟
> (おじさんたち)が全て出力される。