データ構造

データ構造 †

データ構造の種類 †

リスト構造 †

• データの要素をチェーン状に繋ぐ
• 要素の構成：
  • データ部
  • ポインタ部　※次の要素の位置情報を保持する

スタック †

• 「スタック」参照

キュー †

• 「キュー」参照

ツリー構造 (木構造) †

• 親子関係で階層構造を表す
  • 親は複数の子を持つことができる
  • 子は1つの親しか持つことができない
• 構成要素
  • 根（ルート）
  • 節（ノード）
  • 枝（ブランチ）
  • 葉（リーフ）

2分木 (二分木) †

• 完全2分木
  • 葉以外の節は全て2つの子を持つ
  • 根から葉までの深さが全て等しい

• 2分探索木
  • 節の関係が下記の関係を持つ
    • 左の子 < 親
    • 右の子 > 親
  • 根から葉に向かってデータを探索するのに向いている

• ヒープ木
  • 節の関係が下記のいずれかの関係を保つ
    • 子 < 親　※根が最大値
    • 子 > 親　※根が最小値

関連用語 †

• 逆ポーランド記法