二分木
二分木の中でも、全てのノードが「葉であるか、二つの子を持っている(次数が2であるという)」ものを、全二分木 (full binary tree) と呼ぶ。完全二分木 (perfect binary tree, complete binary tree) は全ての葉が同じ「深さ」を持つ二分木を指す。
Complete binary treeには他の定義もあり、ある n について、全ての葉が n または n-1 の「深さ」を持ち、全ての葉をできるだけ左に寄せた二分木を指すこともある。この場合、一番「下」のレベルは左側から全て連続的に埋まっていなければならない。
「ほとんど完全な二分木」(almost complete binary tree) は右である子がいれば必ず左である子がいるが、逆は必ずしも真でないものをいう。
しばしば、ある二分木に属する各々のノードを調べる必要が出てくる。ノードを訪れる順番には定番的なものがあり、それぞれ利点がある。
簡潔データ構造は情報理論で求められる最小の領域のみを消費するデータ構造である。 n {\displaystyle n} 個のノードを持つ異なった二分木の個数は C n {\displaystyle \mathrm {C} _{n}} 、即ち n {\displaystyle n} 番目のカタラン数である(構造が同じ木は同一のものと見なす)。 n {\displaystyle n} が十分大きくなると、これは 4 n {\displaystyle 4^{n}} 程度になる。従って、それらを符号化するには少なくとも log 2  4 n = 2 n {\displaystyle \log _{2}4^{n}=2n} bit 程度が必要となる。よって、簡潔二分木はノードあたり 2bit だけを消費するものでなければならない。