# 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