二分木
二分木においてはあるノードとその子孫もまた二分木を構成する。これを部分木と呼ぶ。 従って二分木を部分木に分け、再帰を用いて探索する方法は自然である。根を調べてからそれにぶらさがる部分木を調べるのが行きがけ順 (preorder)、部分木を調べてからその根を調べるのが帰りがけ順 (postorder) 、片方の部分木を調べ、根を調べ、次いで反対の部分木を調べるのが通りがけ順 (in-order) である。二分探索木では通りがけ順探索はノードを大きさ順(あるいは大きさの逆順)に調べることになる。
二分木はプログラミング言語の基本的な要素を用いて構築することができる。データ型としてレコード型とポインタ型(参照型)をもったプログラミング言語では、典型的な方法では、何らかのデータと左右の子へのポインタからなるノードを組み合わせて木を構成する。場合によっては親へのポインタを用意することもある。参照する相手がない(左右どちらかあるいは両方の子がない)場合は、「何も参照していない」ことを示す特別な値 nil(nullのこと) にしておくか、事前に決めたあるノード(番兵と呼ぶ)を指すようにする。親への参照付きのデータ構築例をPascalによって示す。
明示的な方法ではないが、配列に二分木を格納する方法もある。完全二分木ならば、この方法でもスペースを無駄にすることはない。根の添字を0とすると、この場合、添字 i のノードの子は添字 2i + 1 と 2i + 2 に格納され、そのノード自体の親は(あれば)添字 floor((i-1)/2) にある。配列を用いると記憶容量の節約になり、行きがけ順(先行順、preorder traversal)でデータを舐める場合特に参照の局所性が向上する。しかし、連続したメモリ空間を必要とし、木が大きくなる際に大きな処理時間を必要とする。また n 個のノードを持つ高さ h の木に対し、2 - n に比例したメモリを消費する。
MLのようなタグ付き共有体を備えた言語では、しばしばタグ付き共有体として二分木は構築される。それには二種類のノードが用いられ、一つはデータ、左の子、右の子を持った3-tupleのノードで、もう一つはデータも関数ももたない「葉」である(上記PascalやCのようなポインタ型をもった言語の nil に当たる)