什么是二叉树

二叉树是n(n>=0)个结点的有限集合，由一个根结点及两棵互不相交的、分别称作左子树和右子树的二叉树组成。二叉树也是树的一种，只是在二叉树中，每个结点最多只能有两个孩子结点，如图1所示。

图1 二叉树

图1就是一棵二叉树，因为每个结点最多只能有两个分支，因此称之为二叉。二叉树有两个基本特征：

(1) 每个结点最多只能有两个孩子结点（不存在度大于2的结点）；

(2) 二叉树是有序树，左子树和右子树次序不能颠倒，即使树中某个结点只有一棵子树，也要区别是左子树还是右子树。

如图2中的(a)(b)，就是两棵不同的二叉树。

图2 两棵不同的二叉树

二叉树也是递归定义的，二叉树中的子树还是二叉树。

二叉树的基本形态有五种：

(1) 空二叉树

(2) 仅有根结点的二叉树

(3) 仅有一棵左子树的二叉树

(4) 仅有一棵右子树的二叉树

(5) 有两棵子树的二叉树

这五种形态的二叉树如图3所示。

图3 二叉树的五种基本形态