Gourt Home::Gourt :: 木構造 (データ構造)
木構造（きこうぞう）とは、グラフ理論の木の構造をしたデータ構造のこと。
枝でつながった二つの節点のうち、根(root)に近い方を親、葉(leaf)に近い方を子といい、同じレベルの節点同士を兄弟という。 Tree_structure(data)_01.png
実装方法
コンピュータで利用する場合にはいくつかの実装方法がある。
- 各ノードが子ノードへのポインタのリストを持つ
- 各ノードが親ノードへのポインタを持つ
- 各ノードが親ノードへのポインタと子ノードへのポインタのリストを持つ
- 各ノードが長男ノードへのポインタと弟ノードへのポインタを持つ
走査法
木の各節点を一つずつ走査する方法には、以下の三つがある。（いずれの方法も、根から探索を始める。）
- 前順・先行順・前置順 (pre order)
- 自身の節点を調査し、子節点を順に前順走査する
- 間順・中間順 (in order)
- 長男の節点を間順走査し、自身の節点を調査し、残りの子節点を順に間順走査する
- 後順・後行順・後置順 (post order)
- 子節点を順に後順走査し、自身の節点を調査する
木構造の種類
- 部分木 - 木のある節点から先の枝と節点
- 順序木 - 節点がもつ複数の子節点に、順序関係がついている木
- 2分木 - 各節点が子節点を最大二つしかもたない木
- 多分木 - 子節点を三つ以上持つ節点を含む木。2分木でない木。
- 2分探索木
- ヒープ
- 平衡木 - すべての葉について、深さがほぼ等しい木
- デジタル木 - 主に文字列の格納のためにつかわれる木
- その他
- R木（Rectangle tree）
コンピュータにみる木構造
Træ (datastruktur) | Baum (Graphentheorie) | Tree data structure | Árbol (estructura de datos) | Medis (duomenų struktūra) | Tree | Drzewo (informatyka) | Topologia em árvore | Дерево (структура даних) | 树 (数据结构)
"木構造 (データ構造)"_01.png){kind=link}