二叉树是一类非常重要的树形结构，它可以递归地定义如下：

二叉树T是有限个结点的集合，它或者是空集，或者由一个根结点u以及分别称为左子树和右子树的两棵互不相交的二叉树u(1)和u(2)组成。若用n,n₁和n₂分别表示T，u(1)和u(2)的结点数，则有n=1+n₁+n₂ 。u(1)和u(2)有时分别称为T的第一和第二子树。

因此，二叉树的根可以有空的左子树或空的右子树，或者左、右子树均为空。

二叉树有5种基本形态，如图1所示。

图1 二叉树的5种基本形态(其中□表示空)

在二叉树中，每个结点至多有两个儿子，并且有左、右之分。因此任一结点的儿子不外4种情况：没有儿子；只有一个左儿子；只有一个右儿子；有一个左儿子并且有一个右儿子。

　

注意：二叉树与树和有序树的区别

二叉树与度数不超过2的树不同，与度数不超过2的有序树也不同。在有序树中，虽然一个结点的儿子之间是有左右次序的，但若该结点只有一个儿子时，就无须区分其左右次序。而在二叉树中，即使是一个儿子也有左右之分。例如图2中(a)和(b)是两棵不同的二叉树。虽然它们与图3中的普通树(作为无序树或有序树)很相似，但它们却不能等同于这棵普通的树。若将这3棵树均看作是有序树，则它们就是相同的了。

图2 两棵不同的二叉树

图3 一棵普通的树

由此可见，尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。