二叉树

二叉树是一种应用广泛的树形结构，它的特点是每个节点最多只能有两个孩子。在二叉树中，必须严格区分左右孩子，次序不能颠倒。

二叉树的定义

二叉树是树形结构的一种，只要对树结构加以限制就得到二叉树的定义。

首先二叉树是n（n≥0）个节点的有限集合，并且满足下面的任意一个条件：

①为空二叉树，即n＝0。

②由一个根节点和两棵互不相交的被称为根的左子树和右子树所组成。左子树和右子树分别为一棵二叉树。

所以，二叉树是每个节点最多有两个子树的有序树，通常子树被称做“左子树”和“右子树”，“左子树”和“右子树”的顺序不能任意颠倒。例如，图1-8中的（a）和（b）就是两个完全不同的二叉树。

两个完全不同的二叉树

树和二叉树的区别

从树和二叉树的定义中可以看出它们有三个主要差别：

①树的节点个数至少为1，而二叉树的节点个数可以为0；

②树中节点的最大度数没有限制，而二叉树节点的最大度数为2；

③树的节点无左、右之分，而二叉树的节点有左、右之分。

二叉树的基本形态

从二叉树的定义中可以得到二叉树的5种基本形态：

①空二叉树，其结构如图1-9所示。

图1-9　空二叉树

②仅有根节点的二叉树，其结构如图1-10所示。

图1-10　仅有根节点的二叉树

③右子树为空的二叉树，其结构如图1-11所示。

右子树为空的二叉树

④左子树为空的二叉树，其结构如图1-12所示。

左子树为空的二叉树

⑤左、右子树均为非空的二叉树，其结构如图1-13所示。

左、右子树均为非空的二叉树

二叉树的类型

①满二叉树。满二叉树是指除了叶节点外每一个节点都有左右子女且叶节点都处在最底层的二叉树（见图1-14）。

满二叉树

②完全二叉树。除最后一层外，每一层上的节点数均达到最大值，并且在最后一层上只缺少右边的若干节点，这样的二叉树称为完全二叉树（见图1-15）。

完全二叉树