平成23年春目次 前の問題 次の問題
問５
空の2分探索木に，8，12，5，3，10, 7，6の順にデータを与えたときにできる2分探索木はどれか。
解説
2分探索木とは 左の子≦親≦右の子 の条件を満たすようにした2分木である。そのため、与えられたデータを、ルートからすでにある各ノードと比較し、小さければ左、大きければ右に格納していく。
8，12，5，3，10, 7，6 の順にデータを格納するには次のようになる。
正解はエとなるので、エの図を見ながら確認
8 ：まだデータが入っていないので、ルートになる。
12：まずルートと比較する。８より大きいので、右に進む。そこにはまだ子がないので、そこに登録。
5 ：ルートより小さいので左に進む。そこにはまだ子がないので、そこに登録。
3 ：ルートより小さいので左に進む。そこに、5が登録されているので、それと比較。5より小さいのでさらに左に進み、そこに登録。
10：ルートより大きいので右に進む。そこに、12が登録されているので、それと比較。12より小さいので左に進み、そこに登録。
7 ：ルートより小さいので左に進む。そこに、5が登録されているので、それと比較。5より大きいので右に進み、そこに登録。
6 ：ルートより小さいので左に進む。そこに、5が登録されているので、それと比較。5より大きいので右に進むがそこにまだ7があるのでそれと比較。7より小さいので、左に進みそこに登録。
0 件のコメント:
コメントを投稿