木構造
親と子の関係を表現するのに適したデータ構造である。親は複数の子をもてる一方で、子はただひとつの親のみを持つ。 関連する用語と図は、以下の通りである。
| 用語 | 説明 |
|---|---|
| 木 | 節(根と葉を含む) と枝で構成するデータ構造。 |
| 枝 | 節と節とをつなげる線。 値は格納しない。 |
| 節 | 節の中に値を格納する。 ノードともいう。 |
| 根 | 節のうち、 親をもたないもの。木に1つのみ存在する。 |
| 葉 | 節のうち、子をもたないもの。 |
木構造には様々な種類がある。 重要なものと、それらの包含関係は、以下の通りである。
二分木
子の数が最大でも2である木構造である。 つまり、子をもたない (つまり0)、 1つの子をもつ、 2つの子をもつ、のうちのどれかである。
完全二分木
二分木のうち、2つの子をもつ木構造である。 二分木との違いは、 同じ段がすべて埋まるまで、下の段を埋められない点である。
ヒープ
完全二分木のうち、次のどちらか一方の特性をもつ木構造である。なお、同じ段における値の大小関係は問わない。
親の値は子の値よりも常に大きいか等しい。 最大ヒープという。
または
親の値は子の値よりも常に小さいか等しい。 最小ヒープという。
（参考）
情報処理教科書 出るとこだけ！基本情報技術者［科目B］第4版 橋本 祐史 (著) 翔泳社
コメント