2分木とは全てのノードがもつ子の数が2つ以下で構成されているものをいいます。この構造を考えるとあるノードについてその左側と右側はそれぞれの子を頂点とする木構造になっています。この子をを利用することによって再帰による処理が可能になります。またあるノードの左側と右側の木をそれぞれ左部分木と右部分木といいます。データとして整数値をもつノードを考えると次のように定義できます。

typedef struct node_tag{
　int data;
　struct node_tag *left;
　struct node_tag *right;
} node_t;

　このノードによって2分木を構成するときには例えばデータの大小関係によって構成して行きます。ここでは、子が自分の整数値よりも小さい値を持つ場合はleftに自分の整数値以上の値を持つ場合はrightに連結するものとします。このような規則によって構成された2分木をとくに2分探索木と呼びます。整数列"5, 1, 6, 3, 7, 4, 9, 2"を2分探索木で構成すると次のようになります。



　2分探索木ではノードの挿入は2分木を構成したときに行ったノードの追加と同じ手順で行うことができます。ノードを追加（挿入）するときには新しいノードは必ず子を持たないノードになります。つまり木構造の底辺の部分に追加されることになります。