5.3.1 二叉树的定义

二叉树是节点的有限集，可以是空集，也可以由一个根节点及两棵不相交的子树组成，通常将这两棵不相交的子树分别称作这个根节点的左子树和右子树。二叉树的主要特点如下。

（1）每个节点至多只有两棵子树，即不存在度大于2的节点。

（2）二叉树的子树有左右之分，次序不能颠倒。

（3）二叉树的第i层最多有2i−1个节点。

（4）深度为k的二叉树最多有2k−1个节点。

（5）对于任何一棵二叉树T，如果其终端节点数（即叶节点数）为n0，度为2的节点数为n2，则n0=n2+1。

二叉树有如下5种基本形态：空二叉树，只有根节点的二叉树，右子树为空的二叉树，左子树为空的二叉树，左、右子树均非空的二叉树，如图5-5（a）～（e）所示。

另外，还存在两种特殊的二叉树形态，如图5-6所示。

· 满二叉树：除叶节点外，每一个节点都有左右子叶，并且叶节点都处在最底层的二叉树中。

· 完全二叉树：只有最下面的两层节点的度小于2，并且最下面一层的节点都集中在该层最左边的若干位置的二叉树中。