6-4.データ構造
④木構造
木構造(ツリー構造)はデータ構造の一つで、一つの要素が複数の子要素を持ち、一つの子要素が複数の孫要素を持ち、という形で階層が深くなるほど枝分かれしていく構造のこと
★根
親のないノードのこと
★葉
子ノードを持たないノードのこと
★枝
ノードとノード間を結ぶエッジのこと
★2分木
寝付き木構造の中で、あるノードが持つ子の数が高々2であるもののこと
★完全2分木
二分木の中でもすべてのノードが葉であるか二つの子を持っているもののこと
★バランス木
すべての葉について、深さがほぼ等しい木のこと
★順序木
親から子供にその親の子同士について順序が保証されている木のこと
★多分木
一つの節点に二つを超える子接点をもつ木構造のこと
★探索木
挿入、検索、削除などの操作が行えるデータ構造で、辞書あるいは優先度付きキューとして用いることができる木構造のこと
★2分探索木
各節点にキーを持っている探索木のこと
★深さ優先探索
木やグラフを探索するためのアルゴリズムのこと。
アルゴリズムは根から始まり、バックトラックするまで可能な限り探索を行う。
★幅優先探索
グラフ理論において木構造やグラフの探索に用いられるアルゴリズムのこと
★先行順
深さ優先探索の探索順序の一つ
1.根ノードを調査
2.左の部分木を前順走査する
3.右の部分木を前順走査する
★後行順
深さ優先探索の探索順序の一つ
1.左の部分木を前順走査する
2.根ノードを調査
3.右の部分木を前順走査する
★中間順
深さ優先探索の探索順序の一つ
1.左の部分木を前順走査する
2.右の部分木を前順走査する
3.根ノードを調査
【前へ】6-3.データ構造 【次へ】7-1.アルゴリズム
- 最終更新:2017-09-10 15:43:29