二叉树是一类非常重要的树形结构，它可以递归地定义如下:
二叉树T是有限个结点的集合，它或者是空集，或者由一个根结点u以及分别称为左子树和右子树的两棵互不相交的二叉树u(1)和u(2)组成。若用n,n1和n2分别表示T，u(1)和u(2)的结点数，则有n=1+n1+n2 。u(1)和u(2)有时分别称为T的第一和第二子树。
因此，二叉树的根可以有空的左子树或空的右子树，或者左、右子树均为空。
二叉树具有以下的重要性质:
高度为h≥0的二叉树至少有h+1个结点; 高度不超过h(≥0)的二叉树至多有2h+1-1个结点; 含有n≥1个结点的二叉树的高度至多为n-1; 含有n≥1个结点的二叉树的高度至少为 logn ，因此其高度为Ω(logn)。 详见二叉树词条。
