木構造 (データ構造)
出典: フリー百科事典『ウィキペディア（Wikipedia）』
木構造（きこうぞう）とは、グラフ理論の木の構造をしたデータ構造のこと。
枝でつながった二つの節点のうち、根(root)に近い方を親、葉(leaf)に近い方を子といい、同じ親を持つ節点同士を兄弟という。
目次 |
[編集] 実装方法
コンピュータで利用する場合にはいくつかの実装方法がある。
- 各ノードが子ノードへのポインタのリストを持つ
- 各ノードが親ノードへのポインタを持つ
- 各ノードが親ノードへのポインタと子ノードへのポインタのリストを持つ
- 各ノードが長男ノードへのポインタと弟ノードへのポインタを持つ
[編集] 走査法
木の各節点を一つずつ走査する方法には、以下の三つがある。（いずれの方法も、根から探索を始める。）
- 前順・先行順・前置順 (pre order)
- 自身の節点を調査し、子節点を順に前順走査する
- 間順・中間順 (in order)
- 長男の節点を間順走査し、自身の節点を調査し、残りの子節点を順に間順走査する
- 後順・後行順・後置順 (post order)
- 子節点を順に後順走査し、自身の節点を調査する
[編集] 木構造の種類
- 部分木 - 木のある節点から先の枝と節点
- 順序木 - 節点がもつ複数の子節点に、順序関係がついている木
- 二分木 - 各節点が子節点を最大2つしかもたない木
- 多分木 - 子節点を3つ以上持つ節点を含む木。二分木でない木。
- 2分探索木
- ヒープ
- 平衡木 - すべての葉について、深さがほぼ等しい木
- デジタル木 - 主に文字列の格納のためにつかわれる木
- トライ木
- パトリシア木
- その他
- 領域探索木 (range tree)
- 区分木 (segment tree)
- 区間木 (interval tree)
- R木（Rectangle tree）
