木構造

データが親子関係を持つ階層的なデータ構造。最上位のノードを根（ルート）、末端のノードを葉（リーフ）と呼ぶ。ファイルシステムのディレクトリ構造が代表例である。

要素（節、ノード）を親子関係で階層的につないだデータ構造。最上位の節を根、子を持たない節を葉という。2分木、2分探索木、B木などの種類があり、データの探索や、ディレクトリのような階層データの表現に使う。

データを、根（ルート）から枝分かれする親子関係で階層的に表すデータ構造で、子を持たない節を葉という。ファイルシステムのディレクトリやデータベースの索引などに使われ、子が最大2つの2分木やB木など多くの種類がある。

各節点の子の並び順に意味がある木。2分木の左の子と右の子のように、子を第1子、第2子と区別して扱う。子の順序が決まっているので、先行順・中間順・後行順といった節点の訪問順（走査）が定まり、構文木や2分探索木はこの性質を前提としている。

1つの節点が3つ以上の子を持てる木で、m個までの子を持つものをm分木という。1つの節点に多くのキーと子を持たせると木の高さが低くなり、根から葉までにたどる節点が少なくて済む。この性質を使ったB木やB+木は、ディスクの1回の読込みで多くのキーを比較できるので、データベースの索引に使われる。

出現頻度の高い記号には短いビット列を、低い記号には長いビット列を割り当てる可変長の符号化方式。出現頻度を基に2分木を作って符号を決め、どの符号も他の符号の先頭部分にならないため、区切りなしで一意に復号できる。可逆圧縮の基本的な手法で、JPEGやZIPの中でも使われる。

根から最下層の一つ上の層まですべての節が埋まり、最下層の節は左から詰めて配置された2分木。節の数nに対して高さがおよそlog₂nに抑えられ、配列で効率よく表せるため、ヒープの実現に使われる。