二叉树

   二叉树是一种很特别的树，这种树有个特点，每个结点最多只有两个子结点，也就是说每个父节点最多只有两个儿子，左边的叫做左儿子，右边的叫做右儿子。

   那么，关于二叉树，严谨的定义如下：

二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两个互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

        二叉树有五种基本的形态。第一种，空树，也就是说，该树一个元素的都没有。第二种，只有一个根节点。第三种，只有一个根结点和一个左子树。第四种，只有一个根结点和一个右子树。第五种，有一个根结点和一个左子树和右子树。

        那么，二叉树，都有什么特点呢？其中最显著一个特点就是，一个结点最多最多只有两个子树。然后就是，左子树和右子树是有顺序的，就好比你的左手和右手，它们是不同的，不能颠倒过来。

    还有几种特殊的二叉树。先来讲下第一种。斜树。什么是斜树呢？顾名思义，也就是说，该树斜向一方。也就是说，这个树它只有左子树或者右子树。也就是说，只有左子树或者右子树的树是一种特殊的线性表结构的一种表现形式。那么比较官方的定义如下：

所有的结点都只有左子树的二叉树叫做左斜树。所有的结点都只有右子树的二叉树叫做右斜树。这两种统称为斜树。

        第二种特殊的二叉树，满二叉树。什么是满二叉树呢？就是说，除了叶结点以外，其他的结点都有左儿子和右儿子，就是那种非常健全的，没有却胳膊少腿的树。标准定义如下：

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

        第三种比较特殊的二叉树就是完全二叉树。那么，什么是完全二叉树呢？满二叉树就是除了叶结点以外，其他结点都有左儿子和右儿子，而完全二叉树就是在满二叉树的基础上，从右向左依次缺失儿子，中间不能断开。那么，比较标准的定义如下：

对一棵具有n个结点的二叉树按层序编号，如果编号为i（1<=i<=n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。