2 分探索木として適切なものはどれか。ここで,1〜9 の数字は,各ノード(節)の値を表す。
根を 1 とし,1 の左の子を 2,右の子を 3 とする。2 の子を 4 と 5,3 の子を 6 と 7 とし,6 の子を 8 と 9 とする木。
根を 4 とし,4 の左の子を 2,右の子を 8 とする。2 の子を 1 と 3,8 の子を 6 と 9 とし,6 の子を 5 と 7 とする木。
根を 7 とし,7 の左の子を 6,右の子を 8 とする。6 の子を 4 と 5,8 の子を 3 と 9 とし,3 の子を 1 と 2 とする木。
根を 9 とし,9 の左の子を 7,右の子を 8 とする。7 の子を 1 と 2,8 の子を 5 と 6 とし,5 の子を 3 と 4 とする木。
正解は「イ」です。
2 分探索木では,すべてのノードについて「左の子およびその子孫の値 < 親の値 < 右の子およびその子孫の値」が成り立ちます。
「イ」は,根 4 の左部分木に {1,2,3}\{1, 2, 3\}{1,2,3},右部分木に {5,6,7,8,9}\{5, 6, 7, 8, 9\}{5,6,7,8,9} が配置され,各ノードでも同じ関係が成り立っています(2 の左 1・右 3,8 の左 6・右 9,6 の左 5・右 7)。よって 2 分探索木になっています。
本文が同じ・似ている問題を表示しています