問題プレビューID: d5db795e基本情報技術者試験 午前免除試験 2010年7月

問 5
基本情報技術者試験 午前免除試験 2010年7月

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

解説

正解は「イ」です。

2分探索木とは,任意の節において「左部分木のすべての節の値はその節の値より小さく,右部分木のすべての節の値はその節の値より大きい」という条件を満たす2分木です。

  • ア: 節 15 の右の子が 14 であり,15 より小さくなっています。右部分木の値は親より大きくなければならないので不適切です。
  • イ: 根 17 に対し,左部分木 {14,10,16}\{14, 10, 16\} はすべて 17 より小さく,右部分木 {19,18}\{19, 18\} はすべて 17 より大きい。節 14 は左の子 10(14 より小)と右の子 16(14 より大),節 19 は左の子 18(19 より小)となり,すべての節で条件を満たします。
  • ウ: 節 16 の右の子が 14 であり,16 より小さくなっています。右部分木の値は親より大きくなければならないので不適切です。
  • エ: 根 20 の右の子が 19 であり,20 より小さくなっています。右部分木の値は根より大きくなければならないので不適切です。

したがって,正解は「イ」です。

関連問題

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