二分木
典型的には次のような定義が用いられる。「二分木は連結された (connected) 閉路をもたない (acyclic) グラフで、各頂点 (vertex) の次数 (degree) (各頂点に出入りする辺の数)が3を超えないもの。」 次のことが証明可能である。いかなる二分木でも、次数1のノードの数(葉にあたる)は次数3であるノードの数よりちょうど2だけ多く、次数2であるノードはいかなる数にもなりうる。根付き二分木は、「根にあたる頂点が一つだけ決められており、各頂点の次数が2を超えないもの」をいう。
そのような根を一つ選ぶと、全ての頂点が各々ユニークな親と2つ以下の子を持つことになる。だがこれだけでは子供の左右を決めることができない。連結条件をはずしたもの(閉路をもたない無向グラフ)を森 (forest) と呼ぶ。森は木と異なり、互いに連結している要素が複数あってもよい。
もう一つの定義は有向グラフ上での再帰的定義である。二分木は次のいずれかを指す:
単一の頂点
二つの二分木 a, b と一つの頂点vを用意し、頂点vから二つの二分木a, bそれぞれの根に対して辺を引いたもの。
この定義では左右は決まらないが、唯一の根を決定することはできる。
ノードごとに値が割り振られているとする。あるノードの左の子およびその全ての子孫ノードの持つ値はそのノードの値より小さく、右の子及びその全ての子孫ノードの持つ値はそのノードの値より大きくなるように構成した二分木を二分探索木 (binary search tree) という。二分探索木を通りがけ順に探索すると、各ノードの値を大きさ順(あるいは逆順)に得ることができる。
このような木を用いると二分探索は容易になる。目的とする値を x とすると、根から始めて、
ノードの値 n を調べる x = n → あたり x < n → 左の部分木を同様に調べる x > n → 右の部分木を同様に調べる
という再帰的コーディングが可能である。