「B木」とは異なります。
簡単な二分木。大きさ9、深さ3、根は値2を持つ

二分木（にぶんぎ）は、データ構造の1つである。二進木（にしんぎ）やバイナリツリー（英: binary tree）とも呼ばれ、根付き木構造の中で、全てのノード（節点 node）が持つ子の数が高々2であるものをいう。典型的には2つの子はそれぞれ「左」「右」と呼ばれる。

たとえば、二分探索や二分ヒープを実装するために使われる。

以後、括弧の中は英語表記。
用語

親から子へ有向線分（辺、エッジ edge）が引かれる。子を持たないノードを葉（リーフ leaf）ないし外部ノード (external node) と呼ぶ。葉でないノードを内部ノード (internal node) と呼ぶ。あるノードの「深さ」(depth) はルート（root 「根」にあたるノード）からそのノードまでにたどる経路（パス path）の長さ（経路の種類ではなく、ノード-ノードを1と数えた数）である。特定の「深さ」のノードを総称して木の中での「レベル」(level) と称することがある。あるノードの「高さ」 (height) はそのノードから最も遠い葉までの経路の長さである。同じ親を持つノード同志を兄弟 (siblings) であると呼ぶ。ノードpからノードqまでの経路がある場合、pはqの「先祖」(ancestor)、qはpの「子孫」(descendant) である。ノードの「大きさ」(size) は（自分自身を含んだ）そのノードの子孫の数である。
種類

二分木の中でも、全てのノードが「葉であるか、二つの子を持っている（次数が2であるという）」ものを、全二分木 (full binary tree) と呼ぶ。完全二分木 (perfect binary tree, complete binary tree) は全ての葉が同じ「深さ」を持つ二分木を指す。

Complete binary treeには他の定義もあり、ある n について、全ての葉が n または n-1 の「深さ」を持ち、全ての葉をできるだけ左に寄せた二分木を指すこともある。この場合、一番「下」のレベルは左側から全て連続的に埋まっていなければならない。

「ほとんど完全な二分木」(almost complete binary tree) は右である子がいれば必ず左である子がいるが、逆は必ずしも真でないものをいう。
グラフ理論での定義

典型的には次のような定義が用いられる。「二分木は連結された (connected) 閉路をもたない (acyclic) グラフで、各頂点 (vertex) の次数 (degree) （各頂点に出入りする辺の数）が3を超えないもの。」　次のことが証明可能である。いかなる二分木でも、次数1のノードの数（葉にあたる）は次数3であるノードの数よりちょうど2だけ多く、次数2であるノードはいかなる数にもなりうる。根付き二分木は、「根にあたる頂点が一つだけ決められており、各頂点の次数が2を超えないもの」をいう。

そのような根を一つ選ぶと、全ての頂点が各々ユニークな親と2つ以下の子を持つことになる。だがこれだけでは子供の左右を決めることができない。連結条件をはずしたもの（閉路をもたない無向グラフ）を森 (forest) と呼ぶ。森は木と異なり、互いに連結している要素が複数あってもよい。

もう一つの定義は有向グラフ上での再帰的定義である。二分木は次のいずれかを指す:

単一の頂点

二つの二分木 a, b と一つの頂点vを用意し、頂点vから二つの二分木a, bそれぞれの根に対して辺を引いたもの。

この定義では左右は決まらないが、唯一の根を決定することはできる。
データの二分木への格納法 Pascalコードで定義されたデータ型の利用イメージ

二分木はプログラミング言語の基本的な要素を用いて構築することができる。データ型としてレコード型とポインタ型（参照型）をもったプログラミング言語では、典型的な方法では、何らかのデータと左右の子へのポインタからなるノードを組み合わせて木を構成する。場合によっては親へのポインタを用意することもある。参照する相手がない（左右どちらかあるいは両方の子がない）場合は、「何も参照していない」ことを示す特別な値 nil（nullのこと） にしておくか、事前に決めたあるノード（番兵と呼ぶ）を指すようにする。親への参照付きのデータ構築例をPascalによって示す。type pNode = ^Node; {ノード型へのポインタ} Node = record data : (* 必要なデータをためる部分 *) left, parent, right : pNode {左の子、親、右の子へのポインタ} end;...var root, newnode : pNode;...begin new(root); root^.parent := nil; {根を植える。根には親がいない} new(newnode); {新しいノードをつくる} with newnode^ do begin left := nil; right := nil; {子はいない} parent := root {rootが親} end; root^.left := newnode; {左側の子に} new(newnode); {新しいノードをつくる} with newnode^ do begin left := nil; right := nil; {子はいない} parent := root {rootが親} end; root^.right := newnode {右側の子に}...

明示的な方法ではないが、配列に二分木を格納する方法もある。完全二分木ならば、この方法でもスペースを無駄にすることはない。根の添字を0とすると、この場合、添字 i のノードの子は添字 2i + 1 と 2i + 2 に格納され、そのノード自体の親は（あれば）添字 floor((i-1)/2) にある。配列を用いると記憶容量の節約になり、行きがけ順（先行順、preorder traversal）でデータを舐める場合特に参照の局所性が向上する。しかし、連続したメモリ空間を必要とし、木が大きくなる際に大きな処理時間を必要とする。また n 個のノードを持つ高さ h の木に対し、2h - n に比例したメモリを消費する。

MLのようなタグ付き共有体を備えた言語では、しばしばタグ付き共有体として二分木は構築される。それには二種類のノードが用いられ、一つはデータ、左の子、右の子を持った3-tupleのノードで、もう一つはデータも関数ももたない「葉」である（上記PascalやCのようなポインタ型をもった言語の nil に当たる）
二分木を巡回する方法

しばしば、ある二分木に属する各々のノードを調べる必要が出てくる。ノードを訪れる順番には定番的なものがあり、それぞれ利点がある。
行きがけ順、通りがけ順、帰りがけ順探索

二分木においてはあるノードとその子孫もまた二分木を構成する。これを部分木と呼ぶ。従って二分木を部分木に分け、再帰を用いて探索する方法は自然である。根を調べてからそれにぶらさがる部分木を調べるのが行きがけ順 (preorder)、部分木を調べてからその根を調べるのが帰りがけ順 (postorder) 、片方の部分木を調べ、根を調べ、次いで反対の部分木を調べるのが通りがけ順 (in-order) である。二分探索木では通りがけ順探索はノードを大きさ順（あるいは大きさの逆順）に調べることになる。
深さ優先探索

奥優先探索ともいう。根からできるだけ遠く、しかも、既に調べたノードの子であるノードから調べていく方法である。一般のグラフと異なりこれまでに訪れたノードを全て記憶しておく必要はない。というのも木には閉路がないからである。行きがけ順、通りがけ順、帰りがけ順探索はすべてこれの特殊な例である。
幅優先探索

深さ優先探索と対照的に、未だに訪れていないノードを、根に近い方から探索する。
二分木の応用 二分探索木（左上）、平衡木（下）、ヒープ（右上）
二分探索木

ノードごとに値が割り振られているとする。あるノードの左の子およびその全ての子孫ノードの持つ値はそのノードの値より小さく、右の子及びその全ての子孫ノードの持つ値はそのノードの値より大きくなるように構成した二分木を二分探索木 (binary search tree) という。