問題プレビューID: e904ee23基本情報技術者試験 午前免除試験 2018年1月28日

問 5
基本情報技術者試験 午前免除試験 2018年1月28日

2分探索木になっている2分木はどれか。

解説

正解は「イ」です。

2分探索木とは,「ある節点の左の子(およびその子孫)に含まれる値はすべてその節点よりも小さく,右の子(およびその子孫)に含まれる値はすべてその節点よりも大きい」という規則がすべての節点で成り立つ2分木です。

  • ア: 根 16 の左部分木にある節点 15 の右の子が 14 になっています。右の子は親より大きい必要がありますが,14 < 15 なので規則に反します。
  • イ: 根 17 に対し,左部分木は {14, 10, 16} で全て 17 より小さく,右部分木は {19, 18} で全て 17 より大きいです。節点 14 は左の子 10 と右の子 16 をもち 10 < 14 < 16 を満たし,節点 19 は左の子 18 をもち 18 < 19 を満たします。すべての節点で規則が成り立っています。
  • ウ: 根 18 の左部分木にある節点 16 の右の子が 14 になっています。14 < 16 なので規則に反します。
  • エ: 根 20 の右の子が 19 になっています。右の子は親より大きい必要がありますが,19 < 20 なので規則に反します。

したがって,2分探索木になっているのは「イ」です。

関連問題

本文が同じ・似ている問題を表示しています