問題
2分探索木になっている2分木はどれか。
ア：
イ：
ウ：
エ：
基本情報技術者平成28年秋期 午前問6 ※図は過去問を参考に作成したものです。
基本情報技術者試験や応用情報技術者試験で出題される2分探索木の問題、聞きなれない言葉なので難しく感じます。ただし、2分探索木を理解していれば簡単に解くことができます。
本記事では、2分探索木について図解で分かりやすく解説していきます。
本記事で学べること
- 木構造の構成要素を覚える
- 2分木と2分探索木を理解する
- 基本情報技術者試験の過去問の解き方を学ぶ
木構造
木構造（きこうぞう）とは、データ構造（※配列のように複数のデータを格納できる入れ物）の1つで木のような階層構造でデータを管理するものです。
木構造は、ハードディスクのファイルシステム（フォルダの下にフォルダやファイルがぶら下がっている）やインターネットのドメイン名などの管理で使用されています。
スポンサーリンク
木構造の構成要素
木構造の要素部分を節（ノード）といい、親のない最上位のノードを根（ルート）、子のないノードを葉（リーフ）、そして ノードとノードを繋ぐ線のことを枝（ブランチ）といいます。
2分木
2分木（にぶんぎ）とは、どの親ノードも2つ以下の子ノードで構成されている木構造のことをいいます。
以下は2分木のイメージ例です。
2分探索木
2分探索木（にぶんたんさくぎ）とは、2分木の各ノードにデータをもたせることで探索を行えるようにした木であり、木構造の左部分と右部分の関係が「左の子 < 親 < 右の子」になっているのが特徴です。
例えば、数値「1」～「6」を2分探索木にあてはめると次のように格納されます。
2分探索木の探索
2分探索木は「左の子 < 親 < 右の子」の順にデータが並んでいるので、探索を容易に行うことができます。
ルートから順に探索対象と比較していき、探索対象の方が小さければ左へ、探索対象の方が大きければ右へ移動し、目的のデータを探索していきます。
基本情報技術者試験 過去問の解説
基本情報技術者平成28年秋期 午前問6
問題
2分探索木になっている2分木はどれか。
ア： イ：
ウ： エ：
基本情報技術者平成28年秋期 午前問6
2分探索木とは、各ノードにデータをもたせることで探索を行えるようにした木であり、木構造の左部分と右部分の関係が「左の子 < 親 < 右の子」になっている2分木です。
解答のア～エが2分探索木の条件に一致しているか1つずつ確認していきます。
解答ア
左から順に「10，15，14，16，19」となり、昇順に並んでいないので不正解です。
解答イ
左から順に「10，14，16，17，18、19」となり、昇順に並んでいるので正解です。
解答ウ
左から順に「15，16，14，18，19，20」となり、昇順に並んでいないので不正解です。
解答エ
左から順に「10，18，14，20，15，19，16」となり、昇順に並んでいないので不正解です。