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