木構造

• 木構造
  　複数の層からなるデータ構造です。各データは親子関係を持っており、親のいないデータを根、子のいないデータを葉、親と子のつながりを枝といいます。
• 2分木
  　一つの要素に2つ以下の子要素がある木のことです。
  • 完全2分木
    　葉がすべて同じ階層にあるか、一つだけ違い、すべての葉が左に寄っている2分木のことです。
• 多分木
  　一つの要素に3つ以上の子要素があるものがある木のことです。
• バランス木
  　葉のある層がある程度等しい木です。
• 順序木
  　子要素の間に何らかの順番付けを行った木です。
• 2分探索木
  　すべての要素に対して左の子要素が親要素より小さく、右の子要素が親要素より大きいことが成り立っている木です。
• 深さ優先探索
  　縦方向の探索を優先させる方法です。2分木の探索方法は以下の3つあります。
  • 先行順
    　親→左の子→右の子の順で探索します。
  • 中間順
    　左の子→親→右の子の順で探索します。
  • 後行順
    　左の子→右の子→親の順で探索します。
• 幅優先探索
  　同じ層（横方向）の探索を優先させる方法です。