木構造は主に以下のような用途で使われる

階層構造のあるデータを操作する。ディレクトリツリー、ドメイン名、構文木、制御構造、決定木、XML DOMツリーなど。

情報を探索しやすくする。データベースのインデックス など。この用途の木構造を探索木とも呼ぶ。

データのソートのために使用する。ヒープソートなど。

脚注[脚注の使い方]
注釈^ 一般に無向木は、それに含まれる任意のノードを根として解釈可能な非根付き木である。有向木は、エッジが、葉から根に向かう向きの場合と、根から葉に向う向きの場合があるが、いずれにしても根となるノードが決められた根付き木となる。

出典^ Morris, Joseph M. (December 1979). “Traversing binary trees simply and cheaply”. Information Processing Letters 9 (5): 197-200. doi:10.1016/0020-0190(79)90068-1. 

関連項目

バイナリ空間分割 (BSP)

木 (数学)

二分木

DSWアルゴリズム

参考文献

Donald Knuth. The Art of Computer Programming: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Section 2.3: Trees, pp.308–423.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7 . Section 10.4: Representing rooted trees, pp.214–217. Chapters 12–14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), pp.253–320.

Dale, Nell. Lilly, Susan D. "Pascal Plus Data Structures". D. C. Heath and Company. Lexington, MA. 1995. Fourth Edition.

Drozdek, Adam. "Data Structures and Algorithms in C++". Brook/Cole. Pacific Grove, CA. 2001. Second edition.

外部リンク.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:#f9f9f9;display:flow-root}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}ウィキメディア・コモンズには、木構造 (データ構造)に関連するカテゴリがあります。

⇒Description from the Dictionary of Algorithms and Data Structures

⇒List of data structures from LEDA

⇒Storing Hierarchical Data in a Database PHP による走査コード例がある

⇒Working with Graphs in MySQL

⇒Animation Applet of Binary Tree Traversal

⇒discmath_dvi：8.4. Tree Transversal

表

話

編

歴
データ構造
その他

コレクション(英)

コンテナ

代数的データ型

素集合データ構造

永続データ構造

並行データ構造(英)

配列構造(英)

配列

可変長配列

ビット配列(英)

接尾辞配列

スタック

キュー

両端キュー

リングバッファ

疎行列

リンク構造(英)

連結リスト

スキップリスト

展開リスト

XOR連結リスト

優先度付きキュー

検索構造(英)

連想配列

ハッシュテーブル

ハッシュ配列木(英)

ハッシュ関数

コンシステントハッシュ法

分散ハッシュテーブル


連想リスト(英)

木構造

二分木

二分探索木

二重連鎖木

デカルト木(英)

トップ木(英)

T木(英)

平衡二分木

AA木

AVL木

赤黒木

スプレー木