2分木 【binary tree】

2分木とは、データ構造の一種である木構造のうち、親ノードの持つ子ノードの数が2つ以下であるもの。子ノードを3つ以上取れる木構造は多分木、N分木などと呼ばれる。

　木構造を構成する要素は、節(node、ノード)と呼ばれ、ノード同士は親子関係を持ち、親のないノードを根(root node)、子のないノードを葉(leaf)と呼ぶ。あるノードが持つ子の数が2つ以下であるものを2分木と呼び、通常、図示する際には、最も根っこにあたる(現実の木とは逆に)ルートノードを一番上に描き、その下に子を配置する。また、親子関係のあるノード同士は線で結ぶ。

　通常はノードに付加的な情報を持たせて2分木を構成し、たとえば数式の構造を表現するのに用いられる。この場合、ノードには＋、－、×、÷などの演算子や数値を持たせる。1＋2という式であれば、＋を持つノードの子に、葉である1と2が来ることになる。1＋2×3という式には二通りの表現が考えられ、＋を持つルートノードの子が1のノードと(2×3)の木であるものと、×を持つルートノードの子が(1＋2)の木と3のノードであるものになるが、数式の場合には＋や－よりも×と÷を先に計算する、という条件があるため、ルートノードに×を持たせる場合を採用する。そして、この木構造で表現した数式を計算する場合には、ルートノードから辿りながら計算を行なうことで、＋や－よりも×と÷を先に計算するという条件を満たすことができる。

　他にも、様々な条件の元で木を構成することにより、探索を効率良く行なうなどの応用ができる。また、プログラミング言語を処理する場合にも、言語の構造を表現するのに木構造が用いられる。