Chapter16-7　「木（ツリー）構造」

8/1(日)

tags:基本情報技術

さつき：

• 2分木というデータ構造
  • 根（ルート） - 枝（ブランチ） - 節（ノード）　- 葉（リーフ）
  • 節から伸びる枝が2本以下であるものを、2分木という
• 完全2分木
  • 葉以外の節が全て2つの子を持ち、根から葉までの深さが一様に等しい
• 2分探索木
  • 親の左側にある節は全て親よりも小さなデータたち
    （検索対象の方が小さければ左へ）
  • 親の右側にある節は全て親よりも大きなデータたち
    （検索対象の方が大きければ右へ）
• 過去問
  • 問１　おけ

にわ：

• 読み込み
  • ツリー構造：階層構造を持つデータでよく用いられるデータ構造。
  • 根 - 節 - 葉 と、各要素に名前がついてる。節の上下で「親」「子」という言い方もする。
  • 節から伸びる枝が2本以下のものを「2分木」という。
    • 節から伸びる部分の左が「左部分木」、右が「右部分木」となる
    • 左右の子に対するポインタをデータに付加すれば、配列構造として表すことも可能。
  • 完全2分木
    • 葉以外の節が全て2つの子を持ち、根から葉までの深さが一様に等しい2分木。
  • 2分探索木
    • 親、左部分木、右部分木の関係が「左の子（左部分木全ての節）<親<右の子（右部分木全ての節）」となる2分木。
    • 探索対象データと節のデータの大小比較を節ごとに繰り返せば目的のデータにたどり着けるので、データの探索が容易。
• 過去問
  • 問１：OK、パズルみたいで楽しい

ちさと：

• 根（ルート）- 枝（ブランチ）- 節（ノード）- 葉（リーフ）
• ２分木（にぶんぎ）：節から伸びる枝が２本以下のもの
• 過去問
  • 問１：おk

まい：

• ツリー(ノード、節を持つ)

  • 階層構造を持つデータ、データの探索、整列などに用いられる
  • 例：補助記憶装置ファイルシステム、インターネットのドメイン名
    • キーワード：root, branch, node, leaf, parent node, child node

• 2分木 binary tree: ノードから伸びる枝が2本以下

  • Subtree: ノードからぶら下がる部分。Left subtree, Light subtreeとある
  • 左右の子に対するポインタを付加

• 完全2分木　complete binary tree

• 2分探索木 binary search tree: left child < parent < right child

• 過去問

  • 問一 ok