木構造 (データ構造)

木構造（きこうぞう）とは、グラフ理論の木の構造をしたデータ構造のこと。

枝でつながった二つの節点のうち、根(root)に近い方を親、葉(leaf)に近い方を子といい、同じレベルの節点同士を兄弟という。

親子構造

実装方法

コンピュータで利用する場合にはいくつかの実装方法がある。

• 各ノードが子ノードへのポインタのリストを持つ
• 各ノードが親ノードへのポインタを持つ
• 各ノードが親ノードへのポインタと子ノードへのポインタのリストを持つ
• 各ノードが長男ノードへのポインタと弟ノードへのポインタを持つ

走査法

木の各節点を一つずつ走査する方法には、以下の三つがある。（いずれの方法も、根から探索を始める。）

• 前順・先行順・前置順 (pre order)

自身の節点を調査し、子節点を順に前順走査する

• 間順・中間順 (in order)

長男の節点を間順走査し、自身の節点を調査し、残りの子節点を順に間順走査する

• 後順・後行順・後置順 (post order)

子節点を順に後順走査し、自身の節点を調査する

木構造の種類

• 部分木 - 木のある節点から先の枝と節点
• 順序木 - 節点がもつ複数の子節点に、順序関係がついている木
• 2分木 - 各節点が子節点を最大二つしかもたない木
• 多分木 - 子節点を三つ以上持つ節点を含む木。2分木でない木。
• 2分探索木
• ヒープ
• 平衡木 - すべての葉について、深さがほぼ等しい木
  • B木 (B-tree)
  • AVL木（平衡2分木）
  • 2-3木
  • 2-3-4木
  • 赤黒木（2色木）
  • スプレー木 (splay tree)
• デジタル木 - 主に文字列の格納のためにつかわれる木
  • トライ木
  • パトリシア木
• その他
  • R木（Rectangle tree）

コンピュータにみる木構造

• ディレクトリツリー
• ドメイン名
• 構文解析木
• 制御構造
• 決定木
• データベースのインデックス
• XML DOMツリー