日本百科事典

home | メインページ

木構造 (データ構造)

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

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

実装方法

コンピュータで利用する場合にはいくつかの実装方法がある。 • 各ノードが子ノードへのポインタのリストを持つ • 各ノードが親ノードへのポインタを持つ • 各ノードが親ノードへのポインタと子ノードへのポインタのリストを持つ • 各ノードが長男ノードへのポインタと弟ノードへのポインタを持つ

走査法

木の各節点を一つずつ走査する方法には、以下の三つがある。（いずれの方法も、根から探索を始める。） • 前順・先行順 (pre order)

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

• 間順・中間順 (in order)

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

• 後順・後行順 (post order)

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

木構造の種類

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

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

• ディレクトリツリー • ドメイン名 • 構文解析木 • 制御構造