木構造（きこうぞう）

木構造（きこうぞう / ツリー構造）は、1つの「根（ね）」から枝分かれするようにデータを配置したデータ構造です。

木構造の仕組みとイメージ

木構造は、植物の木を「上下逆さま」にした形、あるいは会社の「組織図」や家系の「家系図」をイメージすると分かりやすいです。
  • データの1つ1つをノード（節・要素）と呼びます。
  • ノード同士を結ぶ線をエッジ（枝）と呼びます。

木構造の専門用語

木構造の問題では、場所（ノードの種類）を表す専門用語が必ず出題されます。
  • 根（ルート：Root）
    • 木の一番上にある、スタート地点のノードです。親はいません。

  • 葉（リーフ：Leaf）
    • 木の一番末端にあるノードです。ここから先の子はいません。

  • 親ノード / 子ノード
    • 上下でつながっている関係です。上にあるのが「親」、下にあるのが「子」です。

  • 部分木（ぶぶんき）
    • 大きな木構造の中から、一部のノードとそこから下のつながりだけを切り出した小さな木のことです。

二分探索木（にぶんたんさくぎ）

試験で最も狙われるのが、二分探索木（にぶんたんさくぎ）という特別なルールを持った木構造です。
💡 二分探索木のルール
すべてのノードにおいて、子ノードが以下のルールで並んでいます。
  • 親より小さいデータは、すべて左側の子へつなぐ
  • 親より大きいデータは、すべて右側の子へつなぐ
前次